讓Haskell代碼更快更快

有誰知道如何讓Haskell代碼更快樂？我在做Project Euler #14。這段代碼在4.029秒運行：讓Haskell代碼更快更快

collatz :: Int -> Int64 -> Int                                     
collatz c 1 = c                 
collatz c k                  
    | even k = collatz (c+1) (k `div` 2)          
    | otherwise = collatz (c+1) (3*k + 1)          

main = do      
    print $ maximum (map (\i -> (collatz 1 i, i)) [1..1000000])

Memoizing的在Collatz功能實際上增加了運行時間，所以我沒有做任何記憶化。可比C代碼0.239秒運行：

int main(int argc, char *argv[]) 
{ 
    int maxlength = 0; 
    int maxstart = 1; 
    for (int i = 1; i <= 1000000; i++) { 
     unsigned long k = i; 
     int length = 1; 
     while (k > 1) { 
      length += 1; 
      if (k % 2 == 0) 
       k = k/2; 
      else 
       k = 3*k + 1; 
     } 
     if (length > maxlength) { 
      maxlength = length; 
      maxstart = i; 
     } 
    } 
    printf("%d, %d\n", maxlength, maxstart); 
    return 0; 
}

Haskell的代碼被編譯以GHC -O3和C代碼用gcc -std = C99 -O3編譯。

來源

2014-12-18 spacepotato

嚴格標註是'shiftR x 1'而不是'div x 2'所遵循的第一件事（是的，一些關鍵優化仍然缺失）。這讓你與C的距離很遠。 – 2014-12-18 23:57:56

這個特殊的歐拉問題在過去產生了大量類似的性能問題。看看[這個搜索]（http://stackoverflow.com/search?q= [haskell] + collatz）一堆建議。 [This one]（http://stackoverflow.com/questions/13669134/c-vs-haskell-collatz-conjecture-speed-pearison/13669277#13669277）可能特別相關。 – 2014-12-19 00:22:08

你有LLVM嗎？它在-21 -fllvm的機器上運行1.3秒。 – 2014-12-19 00:52:05

這裏是Haskell的維基的解決方案：

import Data.Array 
import Data.List 
import Data.Ord (comparing) 

syrs n = 
    a 
    where 
    a = listArray (1,n) $ 0:[1 + syr n x | x <- [2..n]] 
    syr n x = 
     if x' <= n then a ! x' else 1 + syr n x' 
     where 
     x' = if even x then x `div` 2 else 3 * x + 1 

main = 
    print $ maximumBy (comparing snd) $ assocs $ syrs 1000000

計算時間我的機器上：

haskell|master⚡ ⇒ ghc -O2 prob14_memoize.hs 
[1 of 1] Compiling Main    (prob14_memoize.hs, prob14_memoize.o) 
Linking prob14_memoize ... 
haskell|master⚡ ⇒ time ./prob14_memoize 
(837799,524) 
./prob14_memoize 0.63s user 0.03s system 99% cpu 0.664 total

相比於原來的：

haskell|master⚡ ⇒ ghc -O2 prob14_orig.hs 
[1 of 1] Compiling Main    (prob14_orig.hs, prob14_orig.o) 
Linking prob14_orig ... 
haskell|master⚡ ⇒ time ./prob14_orig 
(525,837799) 
./prob14_orig 2.77s user 0.01s system 99% cpu 2.777 total

來源

2014-12-19 01:03:15 spencerlyon2

是的，但問題的規模足夠小，以至於memoization的開銷實際上使其變慢。這段代碼在0.911秒內運行，而不是在0.420秒內運行的原始代碼。兩者都是用ghc -O2 -fllvm編譯的 – spacepotato 2014-12-19 01:12:50

它帶給我的注意這個問題主要是轉貼。請參閱here。

代碼的主要問題是ghc默認不會優化整數分割。要手動修復我的代碼，

collatz c k                  
    | k .&. 1 == 0 = collatz (c+1) (k `shiftR` 1)          
    | otherwise = collatz (c+1) (3*k + 1)

但是，如果在計算機上安裝LLVM，一個可以與

ghc -O2 -fllvm code.hs

LLVM進行必要的優化編譯原碼。這兩種解決方案都使我的代碼在大約0.420秒處運行，這更接近於可比較的C代碼。

來源

2014-12-19 01:20:51 spacepotato

讓Haskell代碼更快更快

回答

相關問題