小编pra*_*nak的帖子

我正在研究Andre Loh在haskell练习中确定性并行编程的练习.我试图通过使用策略将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] …

我试图使用DPH实现nqueens问题,但我最终得到了无法向量化GHC.Prim.Int#错误.当我搜索错误时,我发现了一个GHC Bug,它讨论了用于模式匹配的矢量化文字(http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on -numeric-文字-td5076659.html).我不确定这是不是同一个bug.我的代码如下,

{-# LANGUAGE ParallelArrays #-}
{-# OPTIONS_GHC -fvectorise #-}
module NQueensP (nqueens_wrapper) 
where

import qualified Prelude
import Data.Array.Parallel
import Data.Array.Parallel.Prelude
import Data.Array.Parallel.Prelude.Int as I
import qualified Data.Array.Parallel.PArray as P


isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 
            where isSafeHelper i []  = True
                  isSafeHelper i (x:xs) = (i I.== Prelude.fst x) && I.abs(i I.-   
                                  (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x)) && 
                                       isSafeHelper i xs

nqueens_wrapper::Int -> PArray (PArray Int)
nqueens_wrapper …

我试图比较Haskell列表和数组的性能,并遇到一个奇怪的行为.我观察到,如果我创建一个数组然后打印它需要'x'MB的内存,但如果我使用'elems'函数将数组转换为一个列表然后打印它需要小于'x'的内存.是不是'elems'函数应该从数组中创建一个新列表？它不应该占用比不创建列表的功能更多的空间吗？我正在使用-O2和-fspec-constr优化标志.我也使用-p标志来分析函数.

这是没有中间列表的代码,

fun  n = runST $  do
      final_soln <- newArray_ ((1,1), (n, (10 ^ n))) :: ST s ((STUArray s)  (Int,Int) Int)
      U.unsafeFreeze final_soln

main = do 
    [n] <- getArgs
    {-#  SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt"  $ show $ fun (read n))

这是带有中间列表的代码,

fun :: Int -> UArray (Int,Int) Int
fun  n = runST $  do
      final_soln <- newArray_ ((1,1), (n, (10 ^ n))) :: ST s ((STUArray s)  (Int,Int) Int)
      U.unsafeFreeze final_soln

main = do 
    [n] <- getArgs …

我写了两个版本的nqueens问题,我认为它们应该具有相似的效率,但事实并非如此.我认为这是由于Haskell的懒惰评估行为.有人可以解释它如何适用于以下示例,

nqueens1 n 1 = [[i] | i <- [1..n]]
nqueens1 n k = [ i:q | i <- [1..n], q <- (nqueens1 n (k - 1)), isSafe i q k]

isSafe i q n  = isSafeHelper i (zip q [(n-1),(n-2)..1]) 
         where isSafeHelper i []  = True
               isSafeHelper i (x:xs) = (i /= fst x) && abs(i - (fst x)) /= abs(n - (snd x)) && 
                                       isSafeHelper i xs
nqueens2 n 1 = [[i] | i <- [1..n]]
nqueens2 n …

#include<boost/unordered_map.hpp>
#include<string>
#include<iostream>
#include<boost/unordered_set.hpp>
using namespace std;

typedef boost::unordered_map<string, boost::unordered_map<string,     boost::unordered_set<string>>> nfa;
const boost::unordered_map<string, boost::unordered_set<string>>&    
get_second(const std::pair<string, 
           boost::unordered_map<string, boost::unordered_set<string>>>& p)
 {return p.second;}


int main()
{
   nfa a;
   a["A"]["0"] = {"B", "C"};
   a["A"]["1"] = {"B"};
   a["B"]["0"] = {"B"};
   a["B"]["1"] =  {"C"};
   cout << "Printing using direct reference" << endl;
   for (auto tr_table : a)
   {
     for (auto tr : tr_table.second)
      cout << tr_table.first << " " << tr.first << " " <<     tr.second.size() << endl;
  }
  cout << "Printing using function …