Inserimenti paralleli & # 8220; & # 8221; in un trie binario in Haskell

Question

Ho un elenco di n-bit " parole "

type BitWord = [Bool]

e un trie che memorizza la parola dall'alto verso il basso:

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

Ho una funzione:

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

La funzione attraversa i bit in BitWord , mentre scende attraverso Tree andando a sinistra a zero bit e viceversa. Restituiamo un nuovo albero con questo BitWord " unito in " ;, insieme a True se ad un certo punto dovessimo aggiungere sottotitoli (cioè BitWord non era già nel trie ) e False altrimenti.

Mappare questa funzione su un [BitWord] , passando l'albero come stato.

La mia domanda è questa : questo beneficio potrebbe trarre vantaggio dal parallelismo offerto da Control.Parallel? E se è così, come posso ragionare sulla pigrizia e sulla valutazione solo della forma normale della testa debole, ecc.?

Il mio istinto è che posso inserire (in realtà costruendo una sottostruttura) in un ramo sinistro mentre faccio la stessa cosa nel ramo destro, come due fili indipendenti. Qualcosa del tipo:

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)

Il thread che valuta b dipende da alcuni thread precedentemente attivati ??(quelli appartenenti al BitWords che condividono alcuni prefissi comuni con w ) , ma non tutti, quindi sembra che ci sia l'opportunità di lavorare in parallelo qui, ma non ne sono davvero sicuro.

Answer 1

Sembra un ottimo candidato per l'uso di par quando si attraversa l'albero ... Proprio come il benchmark degli alberi binari. Prova a scrivere alcuni programmi su questo tipo e a misurare l'effetto di par .

Answer 2

Restituire se una parola era nel trie sequenzialmente inutilmente il programma. Se hai davvero bisogno di queste informazioni, sarà probabilmente difficile parallelizzare in modo efficiente.

Tuttavia, se riusciamo a riformulare un po 'il problema in modo che l'ordine e la disposizione degli inserimenti non contino, il problema è piuttosto semplice:

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]

Al momento non ho più core, quindi non posso provarlo, ma dovrebbe ridimensionarsi bene. In pratica abbiamo un ordinamento radix parallelo in poche righe - non troppo malandato!

Answer 3

Perché non lo provi e vedi? Tempo di esecuzione del programma con 1 thread e diversi, e vedere se c'è una differenza. Le scintille a Haskell sono davvero molto economiche, quindi non preoccuparti se ne crei molte.