我正在完成 Andre Loh 的确定性并行编程练习,并尝试使用策略将 N-Queens 串行代码转换为并行代码。但我注意到并行代码运行速度比串行代码慢得多,并且在执行时出现了栈空间不足的错误。
以下是并行 N-Queens 的代码:
以下是并行 N-Queens 的代码:
import Control.Monad
import System.Environment
import GHC.Conc
import Control.Parallel.Strategies
import Data.List
import Data.Function
type PartialSolution = [Int] -- per column, list the row the queen is in
type Solution = PartialSolution
type BoardSize = Int
chunk :: Int -> [a] -> [[a]]
chunk n [] = []
chunk n xs = case splitAt n xs of
(ys, zs) -> ys : chunk n zs
-- Generate all solutions for a given board size.
queens :: BoardSize -> [Solution]
--queens n = iterate (concatMap (addQueen n)) [[]] !! n
queens n = iterate (\l -> concat (map (addQueen n) l `using` parListChunk (n `div` numCapabilities) rdeepseq)) [[]] !! n
-- Given the size of the problem and a partial solution for the
-- first few columns, find all possible assignments for the next
-- column and extend the partial solution.
addQueen :: BoardSize -> PartialSolution -> [PartialSolution]
addQueen n s = [ x : s | x <- [1..n], safe x s 1 ]
-- Given a row number, a partial solution and an offset, check
-- that a queen placed at that row threatens no queen in the
-- partial solution.
safe :: Int -> PartialSolution -> Int -> Bool
safe x [] n = True
safe x (c:y) n = x /= c && x /= c + n && x /= c - n && safe x y (n + 1)
main = do
[n] <- getArgs
print $ length $ queens (read n)
这一行代码 (\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq))
是我从原始代码中更改的。我已经看过Simon Marlow的解决方案,但我想知道我的代码为什么会变慢并出错。
提前感谢。
-O2
选项,而在运行时使用了-threaded -Nn
选项(其中n
是你的CPU核心数量)? - Don Stewart-threaded
是编译时选项,而不是运行时选项。此外,唐,你什么时候回到贝利酒吧?啤酒龙头想念你。 - Thomas M. DuBuisson