Haskell程序运行非常慢

Question

我编写了第一个计算素数的程序。但是它运行得很慢，我不知道为什么。我用Java编写了类似的代码，对于n = 10000，Java程序无需花费任何时间，而Haskell程序则需要2分钟。

import Data.List
main = do
    print "HowManyPrimes? - OnlyInteger"
    inputNumber <- getLine
    let x = (read inputNumber :: Int)
    print (firstNPrimes x)

-- prime - algorithm
primeNumber:: Int -> Bool
primeNumber 2 = True
primeNumber x = primNumberRec x (div x 2)

primNumberRec:: Int -> Int -> Bool
primNumberRec x y
      |y == 0 = False
      |y == 1 = True 
      |mod x y == 0 = False
      |otherwise = primNumberRec x (y-1)

-- prime numbers till n
primesTillN:: Int -> [Int]
primesTillN n = 2:[ x | x <- [3,5..n], primeNumber x ]


--firstNPrimes
firstNPrimes:: Int -> [Int]
firstNPrimes 0 = []
firstNPrimes n = 2: take (n-1) [x|x <- [3,5..], primeNumber x]

提前致谢。

类似的Java代码：

import java.util.Scanner;
public class PrimeNumbers{

static Scanner scan = new Scanner(System.in);

public boolean primeAlgorithm(int x){
    if (x < 2)
        return false;
    return primeAlgorithm(x, (int)Math.sqrt(x));
}

public boolean primeAlgorithm(int x, int divider){
    if (divider == 1)
        return true;
    if (x%divider == 0)
        return false;
    return primeAlgorithm(x, divider-1);
}

public static void main(String[] args){

    PrimeNumbers p = new PrimeNumbers();
    int howManyPrimes = scan.nextInt();
    int number = 3;
    while(howManyPrimes!=0){
        if(p.primeAlgorithm(number)){
            System.out.print(number+" ");
            howManyPrimes--;
        }
        number+=2;
    }

}

}

Answer 1

在进行时序测量时，请始终进行编译；ghci设计用于快速的change-rebuild-run循环，而不是用于快速执行所生成的代码。但是，即使遵循了此建议，您的两个摘要之间也存在巨大的时序差异。

您的Java和Haskell之间的主要区别是使用sqrt而不是除以2。您的原始文件在我的机器上：

% javac Test.java && echo 10000 | /usr/bin/time java Test >/dev/null                             
0.21user 0.02system 0:00.13elapsed 186%CPU (0avgtext+0avgdata 38584maxresident)k
0inputs+0outputs (0major+5823minor)pagefaults 0swaps
% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
8.85user 0.00system 0:08.87elapsed 99%CPU (0avgtext+0avgdata 4668maxresident)k
0inputs+0outputs (0major+430minor)pagefaults 0swaps

所以对于Java是0.2s，对于Haskell是8.9s。切换到使用平方根并进行以下更改后：

- primeNumber x = primNumberRec x (div x 2)
+ primeNumber x = primNumberRec x (ceiling (sqrt (fromIntegral x)))

我得到Haskell的以下时间安排：

% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
0.07user 0.00system 0:00.07elapsed 98%CPU (0avgtext+0avgdata 4560maxresident)k
0inputs+0outputs (0major+427minor)pagefaults 0swaps

现在比Java代码快3倍。（当然，还有更好的算法可以使它更快地运行。）

Answer 2

编译吧！

GHCi中的Haskell代码远未优化。尝试将其编译为具有ghc -o prime prime.hs甚至更好使用-O2优化的二进制文件。我曾经有一个脚本，在GHCi中花了5分钟，但是编译后仅花了几秒钟。