如何改善这种哈斯克尔程序的性能？ [英] How to improve the performance of this Haskell program?

问题描述

我通过项目欧拉的作为学习Haskell的方式工作的问题，我发现我的计划是慢了很多可比的C版本，编译时也是如此。我能做些什么，以加快我的Haskell程序？

I'm working through the problems in Project Euler as a way of learning Haskell, and I find that my programs are a lot slower than a comparable C version, even when compiled. What can I do to speed up my Haskell programs?

例如，我的蛮力解决问题14 是：

For example, my brute-force solution to Problem 14 is:

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秒。

Which takes around 220 seconds, while an "equivalent" brute-force C version only takes 1.2 seconds.

#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;
}

我是什么做错了吗？还是我天真的以为哈斯克尔甚至可能接近C'S速度？

What am I doing wrong? Or am I naive to think that Haskell could even approach C's speed?

（我编译C版本用gcc -O2，而哈斯克尔版本GHC --make -O）。

(I'm compiling the C version with gcc -O2, and the Haskell version with ghc --make -O).

推荐答案

有关我刚才测试目的搜索以= 100000 。所用的时间为 7.34s 。一些修改会导致一些大的改进：

For testing purpose I have just set searchTo = 100000. The time taken is 7.34s. A few modification leads to some big improvement:

1. 使用的整数而不是中的Int64 。这提高了时间的 1.75s

1. Use an Integer instead of Int64. This improves the time to 1.75s.

使用累加器（你不需要sequenceLength偷懒吧？） 1.54s

Use an accumulator (you don't need sequenceLength to be lazy right?) 1.54s.

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


sequenceLength :: Integer -> Int
sequenceLength = seqLen2 1

重写 nextNumber 使用 quotRem ，这样就避免了（曾经在<$ C两次计算事业部$ C>甚至，一次在 DIV ）。 1.27s

Rewrite the nextNumber using quotRem, thus avoiding computing the division twice (once in even and once in div). 1.27s.

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

使用的Schwartzian变换代替 maximumBy 的。 maximumBy的问题。比较是， sequenceLength 函数被调用一次为每个值更多。 0.32s

Use Schwartzian transform instead of maximumBy. The problem of maximumBy . comparing is that the sequenceLength function is called more than once for each value. 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 。

• I check the time by compiling with ghc -O and run with +RTS -s)
• My machine is running on Mac OS X 10.6. The GHC version is 6.12.2. The compiled file is in i386 architecture.)
• The C problem runs at 0.078s with the corresponding parameter. It is compiled with gcc -O3 -m32.

这篇关于如何改善这种哈斯克尔程序的性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！