Parallel „Einfügungen“ in eine binäre Trie in Haskell

Question

Ich habe eine Liste von n-Bit "Worten"

type BitWord = [Bool]

und ein Trie, die das Wort von oben nach unten speichert:

data Tree = Bs Tree Tree  -- Bs (zero_bit) (one_bit)
          | X -- incomplete word
          | B -- final bit of word

Ich habe eine Funktion:

seenPreviously :: BitWord -> Tree -> (Tree,Bool)

Die Funktionsschritte durch die Bits in den BitWord, beim Abstieg durch die Tree bei einem Null-Bit und umgekehrt nach links gehend. Wir kehren ein neuer Baum mit diesem BitWord „in verschmolzen“, zusammen mit True, wenn wir Teilbäume an einem gewissen Punkt hinzufügen mussten (das heißt die BitWord war nicht in der Trie bereits), sonst Falsch.

ich diese Funktion über einen [BitWord] Karte, den Baum als Zustand übergeben.

Meine Frage ist : Könnte dieser Vorteil von der Parallelität von Control.Parallel angeboten? Und wenn ja, wie kann ich über Faulheit und Auswertung Vernunft nur auf schwache Kopfnormalform, etc.?

Mein Instinkt ist, dass ich sein Einsetzen kann (tatsächlich einen Teilbaum Gebäude) nach unten einem linken Zweig, während der gleiche Sache auf dem rechten Zweig zu tun, als zwei unabhängige Threads. So etwas wie:

parallelMapSt :: [ BitWords ] -> Tree -> [Bool]
parallelMapSt [] _ = []
parallelMapSt (w:ws) t = let (b,t') = seenPreviously w t
                             bs     = parralelMapSt ws t'
                          in t' `par` bs `pseq` (b:bs)

Der Faden b Auswertung auf einige zuvor entfacht Fäden abhängt (die, die zum BitWords gehören, die einige gemeinsame Präfix mit w teilen), aber nicht alle von ihnen, so scheint es, dass es Gelegenheit ist parallel arbeiten hier zu tun , aber ich bin wirklich nicht sicher.

Answer 1

Sieht aus wie ein großer Kandidat für die Verwendung von par wenn der Baum durchlaufen ... ähnlich wie der binär Bäume Benchmark. Versuchen Sie schreiben einige Programme auf diese Art und Messung der Wirkung von par.

Answer 2

Rückkehr, ob ein Wort war in der Trie Ihr Programm unnötig sequentializes. Wenn Sie wirklich diese Informationen benötigen, wird es wahrscheinlich schwierig sein, effizient zu parallelisieren.

Wenn wir jedoch das Problem ein wenig, so dass Ordnung und Anordnung von Einfügungen spielt keine Rolle, anders formulieren kann, das Problem ist ziemlich einfach:

import Control.Parallel

data Tree = Bs Bool         -- ^ is an empty word inserted here?
               (Maybe Tree) -- ^ '0' subtree
               (Maybe Tree) -- ^ '1' subtree
     deriving Show

insertMany :: [[Bool]] -> Maybe Tree
insertMany []  = Nothing
insertMany xss = hasEnd `par` fs `par` ts `pseq` Just (Bs hasEnd fs ts)
 where
    hasEnd = any null xss
    fs = insertMany [ xs | False : xs <- xss]
    ts = insertMany [ xs | True  : xs <- xss]

Ich habe nicht mehrere Kerne zur Zeit, so kann ich nicht testen, aber es sollte gut skalieren. Wir haben im Grunde eine parallele Radixsort in nur wenigen Zeilen - nicht zu schäbig

Answer 3

Warum gehst du nicht einfach versuchen und sehen? Zeit die Ausführung des Programms mit 1 Faden und mehrere, und sehen, ob es ein Unterschied. Sparks in Haskell sind wirklich sehr billig, also keine Sorge, wenn Sie eine Menge von ihnen zu schaffen.