Haskell parallele Liste Rechenleistung

Question

Ich plaing mit parallelen Haskell Funktionen par und pseq und ich habe etwas interessantes entdeckt.

Basis Meine Beispiele auf die Beispiele aus Real World Haskell ‚s Buch (Parallel programming in Haskell):

gemeinsamen Code:

import Control.Parallel (par, pseq) 

-- <<sorting code goes here>> 

force :: [a] ->() 
force xs = go xs `pseq`() 
    where go (_:xs) = go xs 
      go [] = 1 

main = do 
    print $ take 10 $ parSort [0..1000000] 

Sortiercode 1 (aus dem Buch):

parSort :: (Ord a) => [a] -> [a] 
parSort (x:xs) = force greater `par` (force lesser `pseq` 
             (lesser ++ x:greater)) 
    where lesser = parSort [y | y <- xs, y < x] 
      greater = parSort [y | y <- xs, y >= x] 
parSort _   = [] 

Sortiercode 2 (meine benutzerdefinierte Variante):

parSort :: (Ord a) => [a] -> [a] 
parSort (x:xs) = force greater `par` (lesser ++ x:greater) 
    where lesser = parSort [y | y <- xs, y < x] 
      greater = parSort [y | y <- xs, y >= x] 
parSort _   = [] 

Compile & Lauf mit: ghc -O2 -threaded --make Main.hs && time ./Main +RTS -N8

Was interessant ist, meine Variante ist ein wenig schneller als die Bücher ein:

sorting code 1 - avg. 16 seconds 
sorting code 2 - avg. 14 seconds 

Ich möchte frage dich, warum wir solch ein Verhalten beobachten können und ob die Lösung des Buches irgendwelche Vorteile gegenüber meinen bietet. Ich würde gerne tief verstehen, warum diese Lösung besser funktionieren könnte.

Answer 1

Ich würde sagen, es liegt daran, dass Ihre benutzerdefinierte Variante den ersten Teil der Liste nicht erzwingt. Schauen wir uns an, was auf der obersten Ebene passiert: Sie erzwingen die rechte Hälfte der Liste, aber nicht den linken Teil. Und wenn Sie die ersten 10 Elemente drucken, bewerten Sie nur die ersten 10 Elemente des linken Teils faul und der Rest wird nicht ausgewertet.

Auf der anderen Seite zwingt die Lösung aus dem Buch beide Teile, also bevor Sie die ersten 10 Elemente drucken, bewerten Sie sowohl den linken als auch den rechten Teil.

Stattdessen werden die ersten 10 Elemente zu drucken, versuchen Sie das letzte Druck, wie

print $ last $ parSort data 

dann beide Varianten des Algorithmus wird die gesamte Liste zu bewerten haben. Oder erzwinge die gesamte Liste nach dem Sortieren und vor dem Ausdrucken.

---

Hinweis dass [0..100000] mit diesem Algorithmus Sortierung wird sehr ineffizient, weil man immer die schlechtestmögliche Dreh wählen und es dauert so O (n^2) Zeit. Die Messungen werden keine sinnvollen Ergebnisse liefern. Wenn Sie mit O (n log n) Zeit schöne Ergebnisse erhalten möchten, füttern Sie den Algorithmus mit zufälligen Daten. Sie können eine einfache Methode zum Erstellen einer zufälligen Permutation here finden.

Hinweis: Anstatt time zu verwenden, empfehle ich Ihnen, criterion zu verwenden, um Ihren Code zu messen. Sie können dann nur relevante Teile Ihres Codes messen, die Initialisierung ausschließen und Ihre Eingabe- und Ausgabedaten erzwingen, so dass Sie genau den Teil messen, an dem Sie interessiert sind.