簡單的主要搜索函數中的並行性

我想了解Haskell中的併發性和並行性。我剛開始Simon Marlow的書。不是一切都很清楚。互聯網上並沒有太多（如果有的話）簡單的例子。簡單的主要搜索函數中的並行性

這只是一個簡單的主要搜索功能的學習目的。這可以並行嗎？如果是的話，有人可以用這個函數來展示一個例子。

main = mapM_ print [x | x <- [2..], isPrime x] 

isPrime :: Integer -> Bool 
isPrime n = odd n && all (\ f -> n `mod` f /= 0) [3..(ceiling $ sqrt $ fromIntegral n)]

我知道我可以使用Strategies來並行地映射一個列表。例如，我會如何在8個批次中測試列表中的因素，並行進行8個測試？我想請一個例子。

謝謝。

來源

2015-10-17 r.sendecky

這個答案也可從http://lpaste.net/143207

的基本想法.lhs文件，只要你有這樣的表達：

parMap strat f xs

：

map f xs

，你可以將其替換爲

將產生地圖計算作爲火花，以便在線程運行時中並行執行。 strat的典型選擇是rdeepseq - 有關其他選項，請參閱Basic Strategies。

問題是，產生每個呼叫f作爲火花可能不符合成本效益。要實現任何加速您可能必須組織工作，以便火花負責在列表的一系列元素上調用f。

讓我們寫isPrime是這樣的：（我故意延長因子的測試範圍，所以我們不必須使用大素數對我們的測試）

-- original version 
isPrime0 n = and $ map notfactor [2..limit] 
    where limit = div n 2 
     notfactor f = mod n f /= 0

第一想法是簡單地改變map到parMap rdeepseq：

-- spawn each call to notfactor as a spark 
isPrime1 n = and $ parMap rdeepseq notfactor [2..limit] 
    where limit = div n 2 
     notfactor f = mod n f /= 0

如果基準但是，你會發現，這比順序版本運行慢得多。

接下來思想是將範圍[2..limit]分解成少數塊這樣的：

-- evaluate the notfactor calls in ranges -- not parallized 
isPrime2 n = and $ map (\r -> all notfactor r) ranges 
    where limit = div n 2 -- ceiling $ sqrt $ fromIntegral n 
     notfactor f = mod n f /= 0 
     ranges = chunks 3 limit 10

這裏chunks a b k是其將列表[a..b]成k相等大小的範圍的函數。

要獲得parallized版本，我們改變了map呼叫到parMap rdeepseq：

-- evaluate the notfacto calls in ranges - parallelized 
isPrime3 n = and $ parMap rdeepseq (\r -> all notfactor r) ranges 
    where limit = div n 2 
     notfactor f = mod n f /= 0 
     ranges = chunks 3 limit 10

一些粗略計時（以秒爲單位）的主要15485863和 RTS選項-N1與-N2：

   -N1  -N2 
isPrime0 0.624 0.673 
isPrime1 12.--- 12.--- 
isPrime2 0.573 0.603 
isPrime3 0.563 0.365

正如你所看到的，isPrime3顯示出一些加速。 isPrime1的時機是由於它產生了數百萬個火花，而isPrime3只產生了10個火花。

爲了完整，這裏是代碼chunks和程序驅動程序。

-- divide a range into equal size chunks 
chunks :: Integer -> Integer -> Integer -> [[Integer]] 
chunks a b k = 
    let (q,r) = divMod (b - a) k 
     sizes = replicate (fromIntegral r) (q+1) ++ replicate (fromIntegral (k-r)) q 
     go x [] = [] 
     go x (y:ys) = [x..x+y-1] : go (x+y) ys 
    in go a sizes 

main :: IO() 
main = do 
    (which : ps : _) <- getArgs 
    let p = read ps 
    case which of 
    "0" -> print $ isPrime0 p 
    "1" -> print $ isPrime1 p 
    "2" -> print $ isPrime2 p 
    "3" -> print $ isPrime3 p

來源

2015-10-17 12:14:23 ErikR

簡單的主要搜索函數中的並行性

回答

相關問題