Создание кода Haskell быстрее

Question

Кто-нибудь знает, как сделать этот код Haskell более быстрым? Я делаю Project Euler #14. Этого код работает в 4.029 секундах:

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 функция Коллатец фактически увеличивает время работы, так что я не делал никакого запоминания. Аналогичный код С работает в 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; 
} 

Код Хаскел собран с GHC -O3 и код C собран с GCC -std = C99 -O3.

Answer 1

Вот решение от 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 

Answer 2

Это было доведено до моего сведения что этот вопрос во многом является репостом. См. 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-коду.