algorithm - 为什么我的 Haskell 代码似乎没有并行运行

Question

我正在尝试解决斯坦福大学 coursera 在线类(class)的 2 和算法问题。我需要在列表中找到所有不同的 x+y 对，它们总和为 [-10000 .. 10000] 范围内的值 t .我知道有更高效的实现，但我认为现在是尝试进行一些 Haskell 并行编程的好时机。

我试图通过在两个不同的线程(我认为这称为 Spark )中循环一半的范围来实现并行化。我的代码如下:

module Main where

import Data.List
import qualified Data.Map as M
import Debug.Trace
import Control.Parallel (par,pseq)

main :: IO ()
main = interact run

range :: [Int]
range = [negate 10000..10000]

emptyMap :: M.Map Int Bool
emptyMap = M.fromList $ zip [] []

run :: String -> String
run xs = let parsedInput = map (read :: String -> Int) $ words xs
             hashMap = M.fromList $ zip parsedInput (repeat True)
             pcalc r = map (\t -> trace (show t) (countVals hashMap parsedInput t)) r
             bot = pcalc (take (div (length range) 2) range)
             top = pcalc (drop (div (length range) 2) range)
             out = top `par` bot `pseq` (sum bot + sum top)
          in show out

countVals :: M.Map Int Bool -> [Int] -> Int -> Int
countVals m ks t = foldl' go 0 ks
  where go acum x = if M.lookup y m == Just True
                            && y /= x
                            then 1
                            else acum
                              where y = t - x

你可以看到我有两个变量 top 和 bot 我试图通过并行计算

out = top `par` bot `pseq` (sum bot + sum top)

这就是我的想法other stack overflow答案是推荐。然而，当我编译并运行时，我似乎只看到了来自 bot 变量的踪迹。

% stack ghc --package parallel -- -threaded Main.hs                                           
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

% ./Main +RTS -N8 < input.txt                                                                   
-10000
-9999
-9998
-9997
-9996
...

而我期待的是:

% ./Main +RTS -N8 < input.txt                                                                    
-10000
0
-9999
1
-9998
2
-9997
-9996
...

有人可以帮助指出我到底做错了什么吗？谢谢

Answer 1

让我们关注这部分:

bot = pcalc (take (div (length range) 2) range)
top = pcalc (drop (div (length range) 2) range)
out = top `par` bot `pseq` (sum bot + sum top)

这里，bot 和top 是列表。当我们seq、pseq 或par 一个值时，我们会对其求值；由于 Haskell 是惰性的，当达到“弱头部范式”时评估停止，即直到第一个构造函数出现在结果中。对于列表值，这意味着它们被简化为 [] 或 unevaluatedHead : unevaluatedTail。

因此，top `par` bot `pseq` ... 仅并行计算列表的第一个单元格，而不是其全部内容。当我们对它们求和时，整个列表只会在 pseq 之后进行评估，但这只在一个内核上运行。

为了强制代码并行，我们可以并行化求和:

sumBot = sum bot
sumTop = sum top
out = sumBot `par` sumTop `pseq` sumBot + sumTop

由于计算 WHNF 的总和需要计算整个列表，因此应该适本地并行计算。