为什么我的 Haskell 代码没有出现在并行 运行 中
Why does my Haskell code not appear to run in Parallel
我正在尝试解决斯坦福大学 coursera 在线课程的 2 和算法问题。我需要在列表中找到所有不同的对 x+y，总和为 t 范围内的值 [-10000 .. 10000]。我知道有更有效的实现，但我认为现在是尝试进行一些 Haskell 并行编程的好时机。
我试图通过在两个不同的线程（我认为称为火花）中循环一半的范围来实现并行化。我的代码如下：
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
...
有人可以帮忙指出我到底做错了什么吗？谢谢
让我们重点关注这部分：
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 的总和需要计算整个列表，这应该适当地并行计算。
我正在尝试解决斯坦福大学 coursera 在线课程的 2 和算法问题。我需要在列表中找到所有不同的对 x+y，总和为 t 范围内的值 [-10000 .. 10000]。我知道有更有效的实现，但我认为现在是尝试进行一些 Haskell 并行编程的好时机。
我试图通过在两个不同的线程（我认为称为火花）中循环一半的范围来实现并行化。我的代码如下：
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
...
有人可以帮忙指出我到底做错了什么吗？谢谢
让我们重点关注这部分：
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 的总和需要计算整个列表，这应该适当地并行计算。