python - 与 Project Euler : C vs Python vs Erlang vs Haskell 的速度比较

Question

我已采取Problem #12来自 Project Euler作为一个编程练习，并比较我在 C、Python、Erlang 和 Haskell 中的(肯定不是最佳的)实现。为了获得更高的执行时间，我搜索了第一个具有超过 1000 个除数的三角形数，而不是原始问题中所述的 500 个。

结果如下:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Python:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

Python 与 PyPy:

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

二郎:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

Haskell:

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

总结:

• C:100%
• Python:692%(118% 使用 PyPy)
• Erlang:436%(135% 感谢 RichardC)
• haskell :1421%

我认为 C 有一个很大的优势，因为它使用 long 进行计算，而不是像其他三个那样使用任意长度的整数。它也不需要先加载运行时(其他的呢？)。

问题 1:Erlang、Python 和 Haskell 是否会因为使用任意长度的整数而失去速度，或者只要值小于 MAXINT 就不会？

问题 2:为什么 Haskell 这么慢？是否有关闭刹车的编译器标志或者是我的实现？ (后者很可能是因为 Haskell 对我来说是一本有七个印章的书。)

问题 3:你能给我一些提示，如何在不改变我确定因素的方式的情况下优化这些实现吗？以任何方式进行优化:更好、更快、更“原生”的语言。

编辑:

问题 4:我的功能实现是否允许 LCO(最后一次调用优化，也就是尾递归消除)，从而避免在调用堆栈中添加不必要的帧？

我确实尝试过在四种语言中实现尽可能相似的相同算法，尽管我不得不承认我的 Haskell 和 Erlang 知识非常有限。

---

使用的源代码:

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

---

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)

---

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

---

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

Answer 1

在 x86_64 Core2 Duo (2.5GHz) 机器上使用 GHC 7.0.3、gcc 4.4.6、Linux 2.6.29，使用 ghc -O2 -fllvm -fforce-recomp 编译 Haskell 和 gcc -O3 -lm 编译 C.

• 您的 C 例程在 8.4 秒内运行(比您的运行速度更快可能是因为 -O3)
• Haskell 解决方案在 36 秒内运行(由于 -O2 标志)
• 您的 factorCount' 代码没有显式输入，默认为 Integer(感谢 Daniel 在这里纠正了我的误诊!)。使用 Int 给出显式类型签名(无论如何都是标准做法)，时间更改为 11.1 秒
• 在 factorCount' 中你不必要地调用了 fromIntegral。修复不会导致任何变化(编译器很聪明，你很幸运)。
• 您使用了 mod，其中 rem 更快且足够。这会将时间更改为 8.5 秒。
• factorCount' 不断地应用两个永远不会改变的额外参数(number、sqrt)。 worker /包装器转换为我们提供了:

 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

没错，7.95 秒。始终比 C 解决方案快半秒。如果没有 -fllvm 标志，我仍然会得到 8.182 秒，因此 NCG 后端在这种情况下也表现良好。

结论:Haskell 很棒。

结果代码

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

编辑:既然我们已经探索过了，让我们来解决问题

Question 1: Do erlang, python and haskell lose speed due to using arbitrary length integers or don't they as long as the values are less than MAXINT?

在 Haskell 中，使用 Integer 比 Int 慢，但慢多少取决于执行的计算。幸运的是(对于 64 位机器)Int 就足够了。出于可移植性考虑，您可能应该重写我的代码以使用 Int64 或 Word64(C 不是唯一具有 long 的语言)。

Question 2: Why is haskell so slow? Is there a compiler flag that turns off the brakes or is it my implementation? (The latter is quite probable as haskell is a book with seven seals to me.)

Question 3: Can you offer me some hints how to optimize these implementations without changing the way I determine the factors? Optimization in any way: nicer, faster, more "native" to the language.

这就是我上面的回答。答案是

• 0) 通过 -O2 使用优化
• 1) 尽可能使用快速(特别是:可拆箱)类型
• 2) rem 不是 mod(一个经常被遗忘的优化)和
• 3) worker/wrapper 转换(可能是最常见的优化)。

Question 4: Do my functional implementations permit LCO and hence avoid adding unnecessary frames onto the call stack?

是的，这不是问题所在。干得好，很高兴您考虑到这一点。