¿Cómo se clasifica con Data.Vector.Generic.Mutable?

Question

¿Cómo se puede ordenar una larga lista de datos (cadenas, flotadores, etc.) que se lee desde un gran archivo (digamos unos pocos millones de líneas) utilizando un objeto Data.Vector.Generic.Mutable y un algoritmo de ordenación de Datos. Vector.Algorithms?

Answer 1

He aquí cómo hacerlo en el caso general.

En primer lugar, necesita un vector mutable. Puede construir esto incrementalmente como escanea el archivo; asigne un vector que sea lo más grande que necesite, y aumente el tamaño y cópielo cuando se quede sin espacio. O bien, puede leer todo el archivo, contar los separadores de registros y asignar la cantidad correcta de espacio a la vez. Esto es más fácil pero probablemente no aceptable en la vida real. (La estrategia de expandir según sea necesario es bastante común en ; si alguna vez usa un lenguaje como Perl y líneas de inserción, lee de un archivo al final de una matriz, esto es lo que está sucediendo. Perl asigna un espacio para una matriz , cuando lo llenas, que aumenta la cantidad de espacio de , asigna un nuevo espacio, y las copias.)

de todos modos, soy demasiado perezoso para hacer esto, así que sólo voy a crear un vector con un poco de azar números en ella.

necesitamos un montón de bibliotecas para esto:

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 

No necesitamos todo esto a la vez, pero vamos a lo necesitamos, finalmente, por lo que pensé que tendría que salir de la camino.

De todos modos, nuestro vector mutable va a ser un vector mutable "normal", aquí MV.MVector.

La idea de un vector mutable es que usted lo cree y lo modifique en un número de pasos . En Haskell, hay algunas maneras de hacer que esto se vea como puro al código de llamada; uno es hacerlo todo dentro de la mónada ST. Su acción ST está creando el vector, modificándolo y "congelando" el en un vector inmutable. Internamente, está utilizando operaciones rápidas modify-this-memory-location-a-bunch-of-times, pero externamente, tiene algo que es puro. (Lea el artículo sobre ST si quieres un argumento de por qué esto es seguro.)

Otra manera de tratar con los datos mutables es sólo lo hacen en el interior del Todo, erm, IO, mónada. Eso es lo que vamos a hacer aquí, como es más conveniente.

(Data.Vector.Mutable tiene dos tipos de vectores predefinidos para que, IOVector y STVector. Estamos utilizando IOVector, que pone todos los las operaciones vectoriales en IO.) Hace

Así como los párrafos 8, que íbamos a crear un vector mutable a ordenar. Y aquí estamos:

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 

Esta es una acción IO que devuelve un nuevo vector mutable con 10 números aleatorios en su interior.(Generación de números aleatorios también puede ser convenientemente levantado en el mónada IO, así que tuvimos que también, por conveniencia! Es que estamos escribiendo C, pero con más agradable sintaxis y más seguridad de tipos.)

Eso es en realidad el parte dura Para hacer la clasificación, importé Data.Vector.Algorithms.Intro, que es básicamente una ruta rápida en el lugar . Una función llamada sort hace la clasificación real (en cualquiera que sea la mónada del vector mutable).

Una acción que crea el vector mutable al azar y la ordena en su lugar parece:

sort = VA.sort =<< randVector 

Ahora, para imprimir de eso, todo lo que tenemos que hacer es "congelar" el vector en un inmutable Vector, e imprima el .toList. O puede simplemente iterar sobre cada elemento e imprimirlo.

Esto es lo que se me ocurrió como un ejemplo:

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

V.unsafeFreeze es de Data.Vector.Generic (forma de interactuar con todos los tipos de vectores con la misma API), como es V.toList.

De todos modos, vale la pena señalar que IO es puramente por conveniencia aquí. Dado que está construyendo un vector a partir de datos de archivos, es apropiado. 99% del tiempo, sin embargo, debe usar ST. En su acción ST, cree el vector, ordénelo, congélelo y devuelva la versión congelada.

Un ejemplo similar usando 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 

A continuación, ejecute con:

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