并行“插入”进入Haskell的二进制trie
-
06-07-2019 - |
题
我有一个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
" 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
共享一些公共前缀) ,但不是全部,所以似乎有机会在这里并行工作,但我真的不确定。
解决方案
在遍历树时看起来像是使用 par
的很好的候选者......就像二叉树基准测试一样。尝试编写这种类型的程序,并测量 par
的效果。
其他提示
返回一个单词是否在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]
我目前没有多个核心,所以我无法对此进行测试,但它应该可以很好地扩展。我们基本上只用了几行就得到了一个并行基数 - 不是太破旧了!
你为什么不试试看?用1个线程和几个线程执行程序的时间,看看是否存在差异。 Haskell中的Spark非常便宜,所以如果你创建了很多它们,不要担心。
不隶属于 StackOverflow