在Haskell中進行緩存和顯式並行

Question

我目前正在試圖在Projet Euler上優化我的解決方案problem 14。 我真的很喜歡哈斯克爾，我認爲這是一個很好的適合這些類型的問題，這裏有三種不同的解決方案，我已經試過：

import Data.List (unfoldr, maximumBy) 
import Data.Maybe (fromJust, isNothing) 
import Data.Ord (comparing) 
import Control.Parallel 

next :: Integer -> Maybe (Integer) 
next 1 = Nothing 
next n 
    | even n = Just (div n 2) 
    | odd n = Just (3 * n + 1) 

get_sequence :: Integer -> [Integer] 
get_sequence n = n : unfoldr (pack . next) n 
    where pack n = if isNothing n then Nothing else Just (fromJust n, fromJust n) 

get_sequence_length :: Integer -> Integer 
get_sequence_length n 
    | isNothing (next n) = 1 
    | otherwise = 1 + (get_sequence_length $ fromJust (next n)) 

-- 8 seconds 
main1 = print $ maximumBy (comparing length) $ map get_sequence [1..1000000] 

-- 5 seconds 
main2 = print $ maximum $ map (\n -> (get_sequence_length n, n)) [1..1000000] 

-- Never finishes 
main3 = print solution 
    where 
    s1 = maximumBy (comparing length) $ map get_sequence [1..500000] 
    s2 = maximumBy (comparing length) $ map get_sequence [500001..10000000] 
    solution = (s1 `par` s2) `pseq` max s1 s2 

現在，如果你看一下實際的問題有很大的潛力緩存，因爲大多數新序列將包含之前已經計算過的子序列。

爲了便於比較，我用C寫了一個版本太多：
運行時間與緩存：0.03秒
運行時間沒有緩存：0.3秒

這只是瘋狂！當然，緩存將時間縮短了10倍，但即使沒有緩存，它仍然比我的Haskell代碼至少快17倍。

我的代碼有什麼問題？ 爲什麼Haskell不會爲我緩存函數調用？由於函數是純粹的緩存不應該緩存是微不足道的，只有可用內存的問題？

我的第三個並行版本有什麼問題？爲什麼它沒有完成？

關於Haskell作爲一種語言，編譯器是否會自動並行化一些代碼（摺疊，映射等），還是總是必須使用Control.Parallel來顯式完成？

編輯：我偶然發現了this類似的問題。他們提到他的功能不是尾遞歸的。我的get_sequence_length尾是否遞歸？如果不是我怎麼能這樣做？

EDIT2：
丹尼爾：
非常感謝您的答覆，真正真棒。 我一直在玩你的改進，我發現了一些非常糟糕的陷阱。

我正在Windws 7（64位），3.3 GHZ四核和8GB內存上運行測試。
我所做的第一件事就像你說的用INT替換所有Integer，但是每當我運行任何主電源時，我用盡內存， 即使+ RTS kSize -RTS設置得過高。

最後我終於找到this（計算器是真棒......），這意味着由於在Windows上的所有Haskell程序作爲32位運行時，INTS被溢出導致無限遞歸，只是哇...

我在Linux虛擬機（使用64位ghc）中運行測試，結果相似。

Answer 1

好的，讓我們從頂部開始。首要的是給出你用來編譯和運行的命令行;我的回答，我會用這條線對所有節目的定時：

ghc -O2 -threaded -rtsopts test && time ./test +RTS -N 

下一個：因爲時限從機差別很大的機器，我們會給我的機器和你的程序的一些基線時機。下面是uname -a我的電腦輸出：

Linux sorghum 3.4.4-2-ARCH #1 SMP PREEMPT Sun Jun 24 18:59:47 CEST 2012 x86_64 Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz GenuineIntel GNU/Linux 

的亮點是：四核，2.4GHz的64位。

使用main1：30.42s user 2.61s system 149% cpu 22.025 total
使用main2：21.42s user 1.18s system 129% cpu 17.416 total
使用main3：22.71s user 2.02s system 220% cpu 11.237 total

事實上，我以兩種方式改性main3：首先，通過消除在s2從該範圍的端部的零點之一，第二，通過將max s1 s2更改爲maximumBy (comparing length) [s1, s2]，因爲前者只是意外計算正確的答案。 =）

我現在將重點放在串行速度上。 （要回答你的一個直接問題：不，GHC不會自動並行或記憶你的程序，這些東西都有很難估計的開銷，因此很難決定什麼時候做這些都是有益的。不知道爲什麼即使在這個答案中的串行解決方案獲得> 100％的CPU利用率;也許一些垃圾收集發生在另一個線程或某種類似的東西。）我們將從main2開始，因爲它是兩個串行實現中速度較快的。得到一點刺激的最便宜的方法是將所有類型簽名更改從Integer到Int：

使用Int：11.17s user 0.50s system 129% cpu 8.986 total（約快兩倍）

下一個提升來自於內環減少分配（消除了中間值Maybe值）。

import Data.List 
import Data.Ord 

get_sequence_length :: Int -> Int 
get_sequence_length 1 = 1 
get_sequence_length n 
    | even n = 1 + get_sequence_length (n `div` 2) 
    | odd n = 1 + get_sequence_length (3 * n + 1) 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

使用此：4.84s user 0.03s system 101% cpu 4.777 total

下一個提升來自使用比even和div更快的操作：

import Data.Bits 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 

get_sequence_length :: Int -> Int 
get_sequence_length 1 = 1 
get_sequence_length n = 1 + get_sequence_length next where 
    next = if even' n then n `quot` 2 else 3 * n + 1 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

使用此：1.27s user 0.03s system 105% cpu 1.232 total

對於那些一起在家裏以下，這比我們開始的main2快17倍d - 與切換到C相比具有競爭性的改進。

對於記憶，有幾種選擇。最簡單的方法是使用預先存在的軟件包（如data-memocombinators）創建一個不可變數組並從中讀取。時間對於爲這個陣列選擇一個好的尺寸非常敏感;對於這個問題，我發現50000是一個相當不錯的上限。

import Data.Bits 
import Data.MemoCombinators 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 

pre_length :: (Int -> Int) -> (Int -> Int) 
pre_length f 1 = 1 
pre_length f n = 1 + f next where 
    next = if even' n then n `quot` 2 else 3 * n + 1 

get_sequence_length :: Int -> Int 
get_sequence_length = arrayRange (1,50000) (pre_length get_sequence_length) 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

有了這個：0.53s user 0.10s system 149% cpu 0.421 total

最快全部是使用可變的，拆箱陣列的記憶化位。它更少地道，但它是裸機速度。速度對這個數組的大小要小得多，只要這個數組的大小和你想要的最大的一樣大。

import Control.Monad 
import Control.Monad.ST 
import Data.Array.Base 
import Data.Array.ST 
import Data.Bits 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 
next n = if even' n then n `quot` 2 else 3 * n + 1 

get_sequence_length :: STUArray s Int Int -> Int -> ST s Int 
get_sequence_length arr n = do 
    bounds@(lo,hi) <- getBounds arr 
    if not (inRange bounds n) then (+1) `fmap` get_sequence_length arr (next n) else do 
     let ix = n-lo 
     v <- unsafeRead arr ix 
     if v > 0 then return v else do 
      v' <- get_sequence_length arr (next n) 
      unsafeWrite arr ix (v'+1) 
      return (v'+1) 

maxLength :: (Int,Int) 
maxLength = runST $ do 
    arr <- newArray (1,1000000) 0 
    writeArray arr 1 1 
    loop arr 1 1 1000000 
    where 
    loop arr n len 1 = return (n,len) 
    loop arr n len n' = do 
     len' <- get_sequence_length arr n' 
     if len' > len then loop arr n' len' (n'-1) else loop arr n len (n'-1) 

main = print maxLength 

有了這個：0.16s user 0.02s system 138% cpu 0.130 total（這與memoized C版的競爭）

Answer 2

GHC不會爲你自動並行化任何東西。正如你猜get_sequence_length是不是尾遞歸。見here。並考慮編譯器（除非它爲你做了一些很好的優化）不能評估所有這些遞歸添加，直到你達到目的;你是「建立thunk」，這通常不是一件好事。

嘗試改爲調用遞歸輔助函數並傳遞累加器，或嘗試根據foldr定義它。