Haskell中的无限列表并行过滤器

Question

我想在Haskell中找到无限列表中的第一个匹配元素.

这段代码有效:

findPassword passwordHash = (head . filter (checkPassword passwordHash)) allStrings

checkPassword真的很长(因为它是一个SHA1哈希)

checkPassword hash string = (sha1 string) == hash

allStrings只是所有可能字符串的列表:

allStrings = [ c : s | s <- "" : allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ]

我希望这些代码并行运行,但如果我用parFilter替换过滤器:

import qualified Control.Parallel.Strategies as S
parFilter p = S.withStrategy (S.evalBuffer 1000 S.rseq) . filter p

它不起作用......你有什么想法吗？这段代码也使用了大量内存,但这是另一个问题.这里有完整的脚本https://github.com/ThibaudDauce/habreaker

Answer 1

我很确定你想用parBuffer而不是evalBuffer.

看到这个SO答案有一个很好的解释:

如何在parList和parBuffer之间进行选择？

这是一些演示代码:

import qualified Data.Map.Strict as M
import Control.Parallel.Strategies
import System.Environment
import Debug.Trace

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

fib' n | trace "calling fib" False = undefined
fib' n = fib n

theList = cycle [30,31,32]

firstN :: Int -> [Int]
firstN n = take n $ filter even $ map fib' theList

firstNpar :: Int -> Int -> [Int]
firstNpar n k = take n $ filter even $ runEval $ parBuffer k rseq $ map fib' theList

main = do
  (argn : argk : _) <- getArgs
  let n = read argn
  case argk of
    "" -> print $ firstN n
    _  -> let k = read argk in
          print $ firstNpar n k

示例运行:

prog 20 2 +RTS -N2         -- I only have two cores
prog 20 ''                 -- run single threaded