Paralelo “inserções” em um trie binário em Haskell

Question

Eu tenho uma lista de n-bit "palavras"

type BitWord = [Bool]

e uma trie que armazena a palavra de cima para baixo:

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

Eu tenho uma função:

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

A função percorre os bits na BitWord, enquanto descendente através do Tree indo para a esquerda em um bit zero e vice-versa. Voltamos uma nova árvore com este BitWord "fundiram-se em", juntamente com o Verdadeiro se tivéssemos que adicionar subárvores em algum momento (ou seja, o BitWord não estava no trie já) e False caso contrário.

I mapear essa função durante um [BitWord], passando a Árvore como estado.

Minha pergunta é esta : Poderia este benefício do paralelismo oferecido por Control.Parallel? E se assim for, como posso raciocinar sobre a preguiça e avaliação apenas para forma normal cabeça fraca, etc.?

Meu instinto é que eu posso ser inserção (na verdade, a construção de uma sub-árvore) abaixo de um ramo esquerdo ao fazer a mesma coisa para baixo o ramo direito, como duas linhas independentes. Algo como:

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)

O fio avaliar b é dependente de alguns tópicos anteriormente provocou (aqueles pertencentes ao BitWords que compartilham alguns prefixo comum com w), mas não todos eles, então parece que há uma oportunidade para fazer o trabalho em paralelo aqui , mas estou realmente não tenho certeza.

Answer 1

parece um grande candidato para o uso de par quando atravessam a árvore ... Muito parecido com o benchmark binários-árvores. Tente escrever alguns programas deste tipo, e medir o efeito de par.

Answer 2

Retornando se uma palavra estava no trie sequentializes desnecessariamente seu programa. Se você realmente precisa dessa informação, ele provavelmente vai ser difícil de paralelizar eficiente.

No entanto, se podemos reformular o problema um pouco de tal forma que a ordem e disposição das inserções não importa, o problema é bastante simples:

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]

Eu não tenho múltiplos núcleos no momento, então eu não posso testar isso, mas deve ser bem dimensionada. Nós, basicamente, tem uma raiz paralelo tipo em apenas algumas linhas - Não demasiado gasto

Answer 3

Por que você não apenas tentar e ver? Tempo a execução do programa com 1 fio e solidária, e ver se há uma diferença. Faíscas em Haskell são realmente muito barato, então não se preocupe se você criar um monte deles.