الموازية "الإدراج" إلى TRIE ثنائي في هاسكل

Question

ولدي قائمة من "الكلمات" ن بت

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 "اندمجت في"، جنبا إلى جنب مع صحيح إذا كان لدينا لإضافة الأشجار الفرعية في مرحلة ما (كان أي من BitWord ليس في TRIE بالفعل) و 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

وبالعودة إذا كانت كلمة في TRIE sequentializes داع البرنامج. إذا كنت حقا بحاجة لهذه المعلومات، فإنه من المحتمل أن يكون من الصعب بشكل مواز بكفاءة.

ولكن، اذا كنا نستطيع إعادة صياغة مشكلة من هذا النوع قليلا هذا النظام والتصرف فيها الإدراج لا يهم، والمشكلة هي واضحة جدا:

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 موضوع وعدة، ومعرفة ما إذا كان هناك فرق. شرارة في هاسكل هي في الواقع رخيصة جدا، لذلك لا تقلق إذا قمت بإنشاء الكثير منهم.