Sortierung Ganzzahlen schnell in Haskell

Question

Gibt es eine Funktion in Haskell-Bibliotheken, die ganze Zahlen in O (n) Zeit sortiert? [Von, O (n) ich meine, schneller als Vergleich zu sortieren und zu spezifisch für ganze Zahlen]

Grundsätzlich finde ich, dass der folgende Code eine Menge Zeit mit der Art nimmt (im Vergleich zu der Liste Summieren ohne Sortierung):

Summieren einer Liste erfordert nicht deepseq, aber was ich versuche, tut, aber der obige Code ist gut genug für die Zeiger, die ich suche.

Zeit: 6 Sekunden (ohne Sortierung); ca. 35 Sekunden (mit Sortierung)

Speicher: ca. 80 MB (ohne Sortierung); ca. 310 MB (mit Sortierung)

Hinweis 1: Speicher ist ein größeres Problem als Zeit für mich hier für die Aufgabe Ich bekomme aus dem Speicherfehler (Speicherverbrauch wird 3GB! nach 30 Minuten Lauf (Zeit)

Ich gehe davon aus, dass schnellere Algorithmen auch einen besseren Speicherdruck liefern und daher nach O (n) Zeit suchen.

Hinweis 2: Ich suche nach schnellen Algorithmen für Int64, obwohl schnelle Algorithmen für andere spezifische Typen auch hilfreich sein werden.

---

verwendete Lösung: Introsort mit unboxed Vektoren war gut genug für meine Aufgabe:

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

Die Idee, die Zahlen mit einem Array zu sortieren, ist die richtige, um die Speichernutzung zu reduzieren.

Wenn Sie jedoch das Maximum und Minimum der Liste als Grenzen verwenden, kann dies zu einer Überschreitung der Speicherauslastung oder sogar zu einem Laufzeitfehler führen, wenn maximum xs - minimum xs > (maxBound :: Int).

Ich schlage also vor, den Listeninhalt in ein ungepacktes veränderbares Array zu schreiben, dieses Inplace zu sortieren (z. B. mit Quicksort) und dann erneut eine Liste daraus zu erstellen.

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 

ist relativ schnell und benötigt weniger Speicher. Es verwendet immer noch viel Speicher für die Liste, 2 Int s nehmen 32MB Speicher roh (mit 64-Bit Int s), mit dem Listen-Overhead von Iirc fünf Wörter pro Element, das addiert sich auf ~ 200MB, aber weniger als die Hälfte des Originals.

Answer 2

Der von Richard Vogel Buch genommen, Pearls of Functional Algorithm Design, (obwohl ich bearbeiten musste es ein wenig, da der Code im Buch nicht genau so kompiliert wurde wie).

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) 

Es funktioniert durch ein Array von ganzen Zahlen indiziert zu schaffen, wo die Werte sind die Anzahl, wie oft jede ganze Zahl in der Liste auftritt. Dann erstellt es eine Liste der Indizes und wiederholt sie so oft, wie sie in der ursprünglichen Liste aufgetreten sind, entsprechend den Zählwerten.

Sie sollten beachten, dass es linear mit dem Maximalwert in der Liste ist, nicht die Länge der Liste, so dass eine Liste wie [ 2^x | x <- [0..n] ] nicht linear sortiert wäre.

Answer 3

Ich würde die Verwendung von Vektoren anstelle von Listen dafür in Betracht ziehen, da Listen eine Menge Overhead pro Element haben, während ein ungekoppelter Vektor im Wesentlichen nur ein zusammenhängender Block von Bytes ist. Das vector-algorithms Paket enthält verschiedene Sortieralgorithmen, die Sie dafür verwenden können, einschließlich radix sort, was meiner Meinung nach in Ihrem Fall gut sein sollte.

Hier ist ein einfaches Beispiel, obwohl es eine gute Idee sein könnte, das Ergebnis in Vektorform zu halten, wenn Sie es weiter bearbeiten wollen.

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 

Auch ich vermuten, dass ein erheblicher Teil der Laufzeit Ihres Beispiel aus dem Zufallszahlengenerator kommt, als der Standard ist für seine Leistung nicht genau bekannt. Sie sollten sicherstellen, dass Sie nur den Sortierbereich zeitlich bestimmen. Wenn Sie in Ihrem Programm viele Zufallszahlen benötigen, stehen schnellere Hacker zur Verfügung.