sorting - sort - ordenar enteros rápidamente en haskell

transpose haskell

Question

¿Hay alguna función en las bibliotecas de Haskell que ordena enteros en O (n) tiempo? [Por, O (n) quiero decir más rápido que el género de comparación y específico para los enteros]

Básicamente encuentro que el siguiente código lleva mucho tiempo con el género (en comparación con sumar la lista sin ordenar):

import System.Random
import Control.DeepSeq
import Data.List (sort)

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int])

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

La suma de una lista no requiere deepseq, pero lo que intento hacer sí, pero el código anterior es lo suficientemente bueno para los punteros que estoy buscando.

Tiempo: 6 segundos (sin ordenar); aproximadamente 35 segundos (con clasificación)

Memoria: alrededor de 80 MB (sin clasificación); alrededor de 310 MB (con clasificación)

Nota 1: la memoria es un problema mayor que el tiempo para mí aquí, en cuanto a la tarea actual, estoy recibiendo errores de memoria (el uso de memoria se convierte en 3 GB después de 30 minutos de tiempo de ejecución)

Supongo que los algoritmos más rápidos también proporcionarán una mejor impresión de la memoria del apostador, por lo tanto, buscarán el tiempo O (n).

Nota 2: Estoy buscando algoritmos rápidos para Int64, aunque los algoritmos rápidos para otros tipos específicos también serán útiles.

Solución utilizada: IntroSort con vectores sin caja fue lo suficientemente bueno para mi tarea:

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I

sort :: [Int] -> [Int]
sort = V.toList . V.modify I.sort . V.fromList

Answer 1

Consideraría el uso de vectores en lugar de listas para esto, ya que las listas tienen una gran cantidad de elementos por cada sobre, mientras que un vector unboxed es esencialmente solo un bloque contiguo de bytes. El paquete de algoritmos de vectores contiene varios algoritmos de clasificación que puede usar para esto, incluido el ordenamiento de radix , que espero que le vaya bien en su caso.

Aquí hay un ejemplo simple, aunque podría ser una buena idea mantener el resultado en forma de vector si planea seguir procesándolo en él.

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Radix as R

sort :: [Int] -> [Int]
sort = V.toList . V.modify R.sort . V.fromList

Además, sospecho que una parte importante del tiempo de ejecución de su ejemplo proviene del generador de números aleatorios, ya que el estándar no se conoce exactamente por su rendimiento. Debes asegurarte de estar cronometrando solo la parte de clasificación, y si necesitas muchos números aleatorios en tu programa, hay generadores más rápidos disponibles en Hackage.

Answer 2

Esto está tomado del libro de Richard Bird, Pearls of Functional Algorithm Design (aunque tuve que editarlo un poco, ya que el código del libro no compilaba exactamente como estaba escrito).

import Data.Array(Array,accumArray,assocs)  

sort :: [Int] -> [Int]
sort xs = concat [replicate k x | (x,k) <- assocs count]
        where count :: Array Int Int 
              count = accumArray (+) 0 range (zip xs (repeat 1))
              range = (0, maximum xs)

Funciona al crear una matriz indexada por enteros donde los valores son la cantidad de veces que aparece cada entero en la lista. Luego crea una lista de los índices, repitiéndolos la misma cantidad de veces que ocurrieron en la lista original de acuerdo con los recuentos.

Debe tener en cuenta que es lineal con el valor máximo en la lista, no la longitud de la lista, por lo que una lista como [ 2^x | x <- [0..n] ] [ 2^x | x <- [0..n] ] no se ordenaría de forma lineal.

Answer 3

La idea de ordenar los números usando una matriz es la correcta para reducir el uso de memoria.

Sin embargo, usar el máximo y el mínimo de la lista como límites puede causar que se exceda el uso de la memoria o incluso un error en el tiempo de ejecución cuando maximum xs - minimum xs > (maxBound :: Int) .

Por lo tanto, sugiero que escriba los contenidos de la lista en una matriz mutable sin caja, clasificándola in situ (p. Ej., Con quicksort) y luego compilando una lista a partir de esa.

import System.Random
import Control.DeepSeq
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST

myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
   | lo < hi   = do
       let lscan p h i
               | i < h = do
                   v <- unsafeRead a i
                   if p < v then return i else lscan p h (i+1)
               | otherwise = return i
           rscan p l i
               | l < i = do
                   v <- unsafeRead a i
                   if v < p then return i else rscan p l (i-1)
               | otherwise = return i
           swap i j = do
               v <- unsafeRead a i
               unsafeRead a j >>= unsafeWrite a i
               unsafeWrite a j v
           sloop p l h
               | l < h = do
                   l1 <- lscan p h l
                   h1 <- rscan p l1 h
                   if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
               | otherwise = return l
       piv <- unsafeRead a hi
       i <- sloop piv lo hi
       swap i hi
       myqsort a lo (i-1)
       myqsort a (i+1) hi
   | otherwise = return ()


genlist gen = runST $ do
    arr <- newListArray (0,2^22-1) $ take (2^22) (randoms gen)
    myqsort arr 0 (2^22-1)
    let collect acc 0 = do
            v <- unsafeRead arr 0
            return (v:acc)
        collect acc i = do
            v <- unsafeRead arr i
            collect (v:acc) (i-1)
    collect [] (2^22-1)

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

es razonablemente rápido y usa menos memoria. Aún utiliza mucha memoria para la lista, 2 ²² Int s toman 32 MB de almacenamiento en bruto (con Int 64 bits), con una sobrecarga de lista de iirc de cinco palabras por elemento, que suma hasta 200MB, pero menos de la mitad del original.