ordinamento numeri interi veloci in haskell

Question

Esiste qualche funzione nelle librerie haskell che ordina gli interi in tempo O (n) ?? [Con, O (n) intendo più veloce di ordinamento per confronti e specifico per gli interi]

Fondamentalmente trovo che il seguente codice prende un sacco di tempo con il tipo (rispetto alla somma lista senza l'ordinamento):

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 

Sommare un elenco non richiede deepseq ma quello che sto cercando di fare, ma il codice sopra è abbastanza buono per i puntatori che sto cercando.

Tempo: 6 secondi (senza ordinamento); circa 35 secondi (con ordinamento)

Memoria: circa 80 MB (senza ordinamento); circa 310 MB (con ordinamento)

Nota 1:! memoria è un problema più grande di tempo per me qui come per il compito a portata di mano io sono sempre fuori gli errori di memoria (l'uso della memoria diventa 3GB dopo 30 minuti di corsa -time)

Suppongo che gli algoritmi più veloci forniranno anche la stampa della memoria di bettore, quindi cerchiamo il tempo O (n).

Nota 2: Sto cercando algoritmi veloci per Int64, sebbene siano utili anche algoritmi veloci per altri tipi specifici.

---

soluzione utilizzata: IntroSort con vettori disimballati era abbastanza buono per il mio compito:

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

L'idea di ordinare i numeri utilizzando un array è quella giusta per ridurre l'utilizzo della memoria.

Tuttavia, l'utilizzo del limite massimo e minimo dell'elenco come limiti può causare il superamento dell'utilizzo della memoria o persino un errore di runtime quando maximum xs - minimum xs > (maxBound :: Int).

Quindi suggerisco di scrivere il contenuto dell'elenco su una matrice mutabile non condivisa, ordinando quella posizione (ad es. Con quicksort), e quindi costruendo di nuovo una lista da quella.

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 

è ragionevolmente veloce e utilizza meno memoria. Utilizza ancora molta memoria per l'elenco, 2 Int s prende 32 MB di spazio grezzo (con 64-bit Int s), con l'elenco di overhead di iirc cinque parole per elemento, che somma fino a ~ 200 MB, ma meno della metà dell'originale.

Answer 2

Questo è tratto dal libro di Richard Bird, Perle di Functional Algorithm Design, (anche se ho dovuto modificare un po ', come il codice nel libro non compilato esattamente come scritto).

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) 

Esso funziona creando un array indicizzato, interi dove i valori sono il numero di volte ogni intero verifica nell'elenco. Quindi crea un elenco degli indici, ripetendoli lo stesso numero di volte in cui si sono verificati nell'elenco originale in base ai conteggi.

Si noti che è lineare con il valore massimo nell'elenco, non la lunghezza dell'elenco, pertanto una lista come [ 2^x | x <- [0..n] ] non verrà ordinata linearmente.

Answer 3

Vorrei prendere in considerazione l'utilizzo di vettori anziché di liste per questo, poiché le liste hanno molti overhead per elemento mentre un vettore unbox è essenzialmente solo un blocco contiguo di byte. Il pacchetto vector-algorithms contiene vari algoritmi di ordinamento che è possibile utilizzare per questo, tra cui radix sort, che mi aspetto dovrebbe fare bene nel tuo caso.

Ecco un semplice esempio, anche se potrebbe essere una buona idea conservare il risultato in formato vettoriale se si pianifica di eseguire un'ulteriore elaborazione su di esso.

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 

Inoltre, ho il sospetto che una parte significativa del tempo di esecuzione del vostro esempio viene dal generatore di numeri casuali, come quella standard, non è esattamente conosciuta per le sue prestazioni. Dovresti assicurarti di sincronizzare solo la parte di ordinamento e se hai bisogno di molti numeri casuali nel tuo programma, ci sono dei generatori più veloci disponibili su Hackage.