并行＆＃8220;插入＆＃8221;进入Haskell的二进制trie

Question

我有一个n位“单词”列表

type BitWord = [Bool]

和一个从上到下存储单词的trie：

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

我有一个功能：

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

该函数逐步执行 BitWord 中的位，同时通过 Tree 下降到零位，反之亦然。如果我们必须在某个时刻添加子树（即 BitWord 已经不在trie中，我们将返回一个新的树，其中 BitWord ＆quot; merge in in“，以及True ）否则为假。

我通过 [BitWord] 映射此函数，将树作为状态传递。

我的问题是：这可以从Control.Parallel提供的并行性中受益吗？如果是这样的话，我如何才能将懒惰和评价归结为弱头正常形式等？

我的直觉是，我可以在左侧分支中插入（实际构建一个子树），同时在右侧分支中执行相同的操作，作为两个独立的线程。类似的东西：

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)

评估 b 的线程依赖于一些先前引发的线程（属于 BitWords 的线程与 w 共享一些公共前缀） ，但不是全部，所以似乎有机会在这里并行工作，但我真的不确定。

Answer 1

在遍历树时看起来像是使用 par 的很好的候选者......就像二叉树基准测试一样。尝试编写这种类型的程序，并测量 par 的效果。

Answer 2

返回一个单词是否在trie中不必要地对您的程序进行顺序化。如果您确实需要此信息，则可能难以有效并行化。

但是，如果我们可以稍微改一下这个问题，那么插入的顺序和处理无关紧要，问题非常简单：

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]

我目前没有多个核心，所以我无法对此进行测试，但它应该可以很好地扩展。我们基本上只用了几行就得到了一个并行基数 - 不是太破旧了！

Answer 3

你为什么不试试看？用1个线程和几个线程执行程序的时间，看看是否存在差异。 Haskell中的Spark非常便宜，所以如果你创建了很多它们，不要担心。