Параллельные & # 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 " слитым в " вместе с True, если нам нужно было добавить поддеревья в какой-то момент (т. Е. BitWord уже не было в дереве ) и False в противном случае.

Я отображаю эту функцию через [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

Возвращение того, было ли слово в строке, излишне упорядочивает вашу программу. Если вам действительно нужна эта информация, вероятно, будет сложно эффективно распараллелить.

Однако, если мы сможем немного перефразировать проблему так, чтобы порядок и расположение вставок не имели значения, проблема довольно проста:

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 действительно очень дешевые, так что не волнуйтесь, если их много.