並列＆＃8220;挿入＆＃8221; Haskellのバイナリトライに

Question

nビットの「単語」のリストがあります

type BitWord = [Bool]

および単語を上から下に格納するトライ：

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 ＆quot; merged in＆quot;を含む新しいツリーを返します。ある時点でサブツリーを追加する必要がある場合はTrueを返します（つまり、 BitWord はまだトライされていません） ）およびそれ以外の場合はFalse。

この関数を [BitWord] にマッピングし、ツリーを状態として渡します。

私の質問はこれです：Control.Parallelが提供する並列処理の恩恵を受けることができますか？もしそうなら、怠headと評価について弱い頭の正常な形などだけにどのように推論できますか？

本能は、2つの独立したスレッドとして、左ブランチに挿入（実際にサブツリーを構築）し、右ブランチに同じことを実行できることです。次のようなもの：

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 を評価するスレッドは、以前にスパークされたスレッド（ w と共通のプレフィックスを共有する BitWords に属するスレッド）に依存しています、すべてではないので、ここで並行して仕事をする機会があるように思えますが、私には本当にわかりません。

Answer 1

ツリーを走査するときに par を使用するための優れた候補のように見えます...バイナリツリーベンチマークによく似ています。このタイプでいくつかのプログラムを作成して、 par の効果を測定してみてください。

Answer 2

単語がトライにあったかどうかを返すと、プログラムが不必要にシーケンシャルになります。この情報が本当に必要な場合、おそらく効率的に並列化するのは難しいでしょう。

ただし、挿入の順序と処理が問題にならないように問題を少し言い換えることができる場合、問題は非常に簡単です：

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のスパークは非常に安価なので、大量に作成しても心配する必要はありません。