parallèles « insertions » dans une structure arborescente binaire dans Haskell

Question

j'ai une liste de n bits « mots »

type BitWord = [Bool] 

et Trie qui stocke le mot du haut vers le bas:

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

I ont une fonction:

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

les étapes de fonction par l'intermédiaire des bits dans le BitWord, en descendant à travers le Tree allant à gauche à un bit zéro et vice versa. Nous retournons un nouvel arbre avec ce BitWord "fusionné", avec True si nous devions ajouter des sous-arbres à un certain point (c'est-à-dire que le BitWord n'était pas déjà dans le paquet) et Faux dans le cas contraire.

Je mappe cette fonction sur [BitWord], en passant l'arbre en tant qu'état.

Ma question est la suivante:: Cela pourrait-il bénéficier du parallélisme offert par Control.Parallel? Et si oui, comment puis-je raisonner sur la paresse et l'évaluation uniquement sur la forme normale de la tête faible, etc.? Mon instinct est que je peux insérer (construire réellement un sous-arbre) sur une branche gauche en faisant la même chose sur la branche droite, comme deux fils indépendants. Quelque chose comme:

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) 

Le fil évaluation b dépend de certains sujets avaient donné lieu à (ceux appartenant à la BitWords qui partagent un certain préfixe commun avec w), mais pas tous, donc il semblerait qu'il y ait possibilité de travailler en parallèle ici, mais je ne suis pas vraiment sûr.

Answer 1

Cela ressemble à un bon candidat pour l'utilisation de par lors de la traversée de l'arbre ... Tout comme le benchmark des arbres binaires. Essayez d'écrire des programmes sur ce type, et de mesurer l'effet de par.

Answer 2

Pourquoi ne pas simplement l'essayer et voir? Temps l'exécution du programme avec 1 thread et plusieurs, et voir s'il y a une différence. Les étincelles à Haskell sont vraiment très bon marché, alors ne vous inquiétez pas si vous en créez beaucoup.

Answer 3

Renvoyer si un mot était dans le programme inutilement séquentialiser votre programme. Si vous avez réellement besoin de cette information, il sera probablement difficile de la paralléliser efficacement.

Cependant, si nous pouvons reformuler le problème un peu de telle sorte que l'ordre et la disposition des insertions n'a pas d'importance, le problème est assez simple:

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] 

Je n'ai pas plusieurs cœurs en ce moment, donc je ne peux pas tester ça, mais ça devrait bien évoluer. Nous avons essentiellement un tri par radix en quelques lignes - pas trop mal!