c - 如何提高这个 Haskell 程序的性能？

Question

我正在解决 Project Euler 中的问题作为学习 Haskell 的一种方式，我发现我的程序比类似的 C 版本慢很多，即使在编译时也是如此。我可以做些什么来加速我的 Haskell 程序？

例如，我对 Problem 14 的暴力解决方案是:

import Data.Int
import Data.Ord
import Data.List

searchTo = 1000000

nextNumber :: Int64 -> Int64
nextNumber n
    | even n    = n `div` 2
    | otherwise = 3 * n + 1

sequenceLength :: Int64 -> Int
sequenceLength 1 = 1
sequenceLength n = 1 + (sequenceLength next)
    where next = nextNumber n

longestSequence = maximumBy (comparing sequenceLength) [1..searchTo]

main = putStrLn $ show $ longestSequence

这大约需要 220 秒，而“等效”的暴力 C 版本只需要 1.2 秒。

#include <stdio.h>

int main(int argc, char **argv)
{
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;

    for (i = 1; i <= 1000000; i++)
    {
        j = i;
        int this_terms = 1;

        while (j != 1)
        {
            this_terms++;

            if (this_terms > terms)
            {
                terms = this_terms;
                longest = i;
            }

            if (j % 2 == 0)
                j = j / 2;
            else
                j = 3 * j + 1;
        }
    }

    printf("%d\n", longest);
    return 0;
}

我做错了什么？还是我天真地认为 Haskell 甚至可以接近 C 的速度？

(我使用 gcc -O2 编译 C 版本，使用 ghc --make -O 编译 Haskell 版本)。

Answer 1

出于测试目的，我刚刚设置了 searchTo = 100000。所用时间为7.34s。一些修改导致一些大的改进:

1. 使用 Integer 而不是 Int64。这将时间缩短到 1.75s。

2. 使用累加器(你不需要 sequenceLength 来偷懒，对吧？)1.54s。

   seqLen2 :: Int -> Integer -> Int
   seqLen2 a 1 = a
   seqLen2 a n = seqLen2 (a+1) (nextNumber n)
   
   sequenceLength :: Integer -> Int
   sequenceLength = seqLen2 1
   

3. 使用 quotRem 重写 nextNumber，从而避免计算除法两次(一次在 even 中，一次在 div )。 1.27s。

   nextNumber :: Integer -> Integer
   nextNumber n 
       | r == 0    = q
       | otherwise = 6*q + 4
       where (q,r) = quotRem n 2 
   

4. 使用 Schwartzian transform而不是 maximumBy。 maximumBy 的问题。 comparing 是 sequenceLength 函数为每个值调用了不止一次。 0.32s。

   longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
   

---

注意:

• 我通过使用 ghc -O 编译并使用 +RTS -s 运行来检查时间)
• 我的机器运行的是 Mac OS X 10.6。 GHC 版本为 6.12.2。编译后的文件是i386架构。)
• C 问题在 0.078s 时运行并带有相应的参数。它是用 gcc -O3 -m32 编译的。