让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代码更快更快

回答

相关问题