Haskell의 이진 트리와 병렬 "삽입"

StackOverflow https://stackoverflow.com/questions/1628061

문제

N-Bit "Words"목록이 있습니다.

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 우리가 어느 시점에서 하위 트리를 추가해야한다면 "합병"(즉, BitWord 이미 트리에 있지 않았고 그렇지 않으면 거짓.

이 기능을 a에 매핑합니다 [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.

다른 팁

단어가 트리에 있었는지 여부를 반환하면 불필요하게 프로그램을 순차적으로 순차적으로 만듭니다. 이 정보가 실제로 필요한 경우 효율적으로 병렬화하기가 어려울 것입니다.

그러나 삽입의 순서와 처분이 중요하지 않도록 문제를 약간 다시 표현할 수 있다면 문제는 매우 간단합니다.

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의 스파크는 정말 저렴하므로 많은 것을 만들어도 걱정하지 마십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top