Come si ordina con Data.Vector.Generic.Mutable?

Question

Come è possibile ordinare una lunga lista di dati (stringhe, float ecc.) Letti da un grande file (ad esempio qualche milione di righe) utilizzando un oggetto Data.Vector.Generic.Mutable e un algoritmo di ordinamento da Data. Vector.Algorithms?

Answer 1

Ecco come procedere nel caso generale.

In primo luogo, è necessario un vettore mutabile. È possibile creare questo incrementale come si esegue la scansione del file; allocare un vettore che è grande quanto necessario, e aumentare le dimensioni e copiare quando si esaurisce lo spazio. Oppure puoi leggere l'intero file, contare i separatori dei record e allocare la giusta quantità di spazio tutto in una volta. Questo è più facile ma probabilmente non è accettabile nella vita reale. (La strategia di espansione necessaria è abbastanza comune, se usi mai un linguaggio come Perl e fai scorrere le righe che leggi da un file alla fine di un array, questo è ciò che sta accadendo. Perl alloca un po 'di spazio per un array , quando si riempie, aumenta la quantità di spazio , assegna nuovi spazi, e le copie.)

Comunque, io sono troppo pigro per fare questo, quindi sono solo andando a creare un vettore con un po 'a caso numeri in esso.

Abbiamo bisogno di un sacco di librerie per questo:

import Control.Monad 
import System.Random 
import qualified Data.Vector as IV 
import qualified Data.Vector.Mutable as MV 
import qualified Data.Vector.Generic as V 
import qualified Data.Vector.Algorithms.Intro as VA 

Non abbiamo bisogno di questo tutto in una volta, ma abbiamo bisogno che alla fine, così ho pensato avrei avuto fuori dal modo.

In ogni caso, il nostro vettore mutabile sarà un vettore "normale" mutabile, qui MV.MVector.

L'idea di un vettore mutabile è che lo si crea e lo si modifica in un numero di passaggi . In Haskell, ci sono alcuni modi per rendere questo aspetto puro al codice chiamante; uno è quello di fare tutto all'interno della monade ST. L'azione ST sta creando il vettore, modificandolo e "congelandolo" in in un vettore immutabile. Internamente, stai utilizzando le operazioni di modifica-questa-memoria-posizione-un-mazzo-di-tempi, esternamente, ma hai qualcosa che è puro. (Leggi il documento sulla ST se si desidera un argomento sul motivo per cui questo è sicuro.)

Un altro modo di trattare con i dati mutabile è quello di fare proprio all'interno del Tutto, ehm, IO, monade. Questo è quello che faremo qui, come è più conveniente.

(Data.Vector.Mutable ha due tipi di vettore predefiniti per voi, IOVector e STVector. Stiamo utilizzando IOVector, che mette tutte le operazioni vettoriali in IO.)

Così come 8 paragrafi fa, avremmo creare un vettore mutabile in ordinamento . Ed eccoci qui:

randVector :: IO (MV.IOVector Int) 
randVector = do 
    v <- MV.new 10 
    forM [0..9] $ \x -> do 
    r <- randomIO :: IO Int 
    MV.write v x r 
    return v 

Si tratta di un'azione IO che restituisce un nuovo vettore mutabile con 10 casuali numeri al suo interno.(Generazione di numeri casuali può anche essere comodamente sollevato nella monade IO, così abbiamo fatto anche quello, per convenienza! E ' come stiamo scrivendo C, ma con la sintassi più bello e più sicurezza tipo.)

Questo è in realtà il parte difficile. Per effettuare l'ordinamento, ho importato Data.Vector.Algorithms.Intro che è fondamentalmente un quicksort sul posto . Una funzione chiamata sort esegue l'ordinamento effettivo (in in cui è presente il vettore mutabile).

Un'azione che crea il vettore mutabile casuale e ordina al suo posto assomiglia:

sort = VA.sort =<< randVector 

Ora, per la stampa che fuori, tutto quello che dobbiamo fare è "congelare" il vettore in un immutabile vettore e stampare lo .toList. Oppure puoi semplicemente iterare su ogni elemento e stamparlo.

Ecco cosa mi è venuta come un esempio:

main = do 
    v <- randVector 
    VA.sort v 
    iv <- V.unsafeFreeze v :: IO (IV.Vector Int) 
    print . V.toList $ iv 

V.unsafeFreeze da Data.Vector.Generic (come interagire con tutti i tipi di vettore con la stessa API), come è V.toList.

In ogni caso, vale la pena notare che IO è puramente per comodità qui. Poiché si sta costruendo un vettore da dati di file, è appropriato. 99% del tempo, tuttavia, è necessario utilizzare ST. Nella tua azione ST, crea il vettore , ordinalo, bloccalo e restituisci la versione congelata.

Un esempio simile utilizzando STVector:

randVector :: ST s (Vector Int) 
randVector = do 
    vec <- new 10 
    rand <- newSTRef 17 
    forM_ [0..9] $ \index -> do 
    randN <- readSTRef rand 
    let randN' = (fst . next . mkStdGen) randN 
    writeSTRef rand randN' 
    write vec index randN' 
    unsafeFreeze vec 

Quindi eseguite con:

*Main> runST randVector 
fromList [679560,1422110406,306332632,1905242129,692062628,393451229,355476175,1240028023,873588529,1181443777] :: Data.Vector.Vector