与Euler项目的速度比较：C，Python，Erlang，Haskell

Question

我已经采取了问题＃12从项目欧拉作为编程锻炼和比较我的（肯定不是最优的）实现在C，Python和Erlang和Haskell的。为了获得更高的执行时间，我搜索的第一个三角形数的除数大于1000，而不是原始问题中所述的500。结果如下：C：lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.clorenzo@enzo:~/erlang$ time ./euler12.bin842161320real    0m11.074suser    0m11.070ssys 0m0.000s蟒蛇：lorenzo@enzo:~/erlang$ time ./euler12.py 842161320real    1m16.632suser    1m16.370ssys 0m0.250s带有PyPy的Python：lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 842161320real    0m13.082suser    0m13.050ssys 0m0.020sErlang：lorenzo@enzo:~/erlang$ erlc euler12.erl lorenzo@enzo:~/erlang$ time erl -s euler12 solveErlang 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> 842161320real    0m48.259suser    0m48.070ssys 0m0.020sHaskell：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 842161320real    2m37.326suser    2m37.240ssys 0m0.080s摘要：C：100％Python：692％（使用PyPy时为118％）Erlang：436％（135％感谢RichardC）哈斯克尔：1421％我认为C具有很大的优势，因为它使用long进行计算，而不使用其他任意三个整数。另外，它不需要先加载运行时（其他是否需要加载？）。问题1： Erlang，Python和Haskell是否会由于使用任意长度的整数而失去速度，或者只要值小于，它们就不会丢失MAXINT吗？问题2： 为什么Haskell这么慢？是否有编译器标志可以使您刹车，或者它是我的实现？（后者很有可能是因为Haskell是一本对我有七个印章的书。）问题3： 能否为我提供一些提示，说明如何在不改变因素确定方式的情况下优化这些实现？以任何方式进行优化：对语言更好，更快，更“原生”。编辑：问题4： 我的函数实现是否允许LCO（最后一次调用优化，又称为尾部递归消除），从而避免在调用堆栈中添加不必要的帧？尽管我不得不承认我的Haskell和Erlang知识非常有限，但我确实尝试过用四种语言尽可能地实现相同的算法。

Answer 1

使用GHC 7.0.3，gcc 4.4.6，Linux 2.6.29一个x86_64的Core2双核（2.5GHz的）机器上，编译使用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）。工人/包装工人的转型为我们提供了：

 $ time ./so

 842161320  

 real    0m7.954s  

 user    0m7.944s  

 sys     0m0.004s  

没错，7.95秒。始终比C解决方案快半秒。没有-fllvm标记，我仍然会收到消息8.182 seconds，因此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

编辑：现在我们已经探索了，让我们解决问题

问题1：erlang，python和haskell是否会由于使用任意长度的整数而失去速度，还是只要它们的值小于MAXINT，它们就不会丢失吗？

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

问题2：为什么haskell这么慢？是否有编译器标志可以使您刹车，或者它是我的实现？（后者很可能因为haskell是一本对我有七个印章的书。）

问题3：能否为我提供一些提示，说明如何在不改变因素确定方式的情况下优化这些实现？以任何方式进行优化：对语言更好，更快，更“原生”。

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

0）通过使用优化 -O2

1）尽可能使用快速（特别是：不可装箱）类型

2）rem不是mod（经常被遗忘的优化），并且

3）worker / wrapper转换（也许是最常见的优化）。

问题4：我的功能实现是否允许LCO，从而避免在调用堆栈中添加不必要的帧？

是的，这不是问题。做得好，很高兴您考虑了这一点。

Answer 2

Erlang实现存在一些问题。作为以下内容的基准，我测得的未经修改的Erlang程序的执行时间为47.6秒，而C代码为12.7秒。

如果要运行计算密集型的Erlang代码，您应该做的第一件事就是使用本机代码。使用进行编译，erlc +native euler12时间缩短至41.3秒。但是，这比这种代码的本机编译要低得多（仅15％），问题是您使用-compile(export_all)。这对于实验很有用，但是所有功能都可以从外部访问的事实导致本机编译器非常保守。（普通的BEAM仿真器不会受到太大影响。）用替换该声明可以-export([solve/0]).提供更好的加速：31.5秒（比基线快将近35％）。

但是代码本身有一个问题：对于factorCount循环中的每个迭代，您都可以执行以下测试：

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

C代码不会执行此操作。通常，在同一代码的不同实现之间进行公平的比较可能比较棘手，特别是如果算法是数字的，因为您需要确保它们实际上在做相同的事情。尽管某个实现最终会达到相同的结果，但由于某个地方的某些类型转换而导致的一种实现中的轻微舍入错误可能会导致其执行的迭代次数要多于另一个实现。

为了消除这种可能的错误源（并消除每次迭代中的额外测试），我重新编写了factorCount函数，如下所示，该函数非常类似于C代码：

factorCount (N) ->

    Sqrt = math:sqrt (N),

    ISqrt = trunc(Sqrt),

    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);

       true          -> factorCount (N, ISqrt, 1, 0)

    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;

factorCount ( N, ISqrt, Candidate, Count) ->

    case N rem Candidate of

        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);

        _ -> factorCount (N, ISqrt, Candidate + 1, Count)

    end.

此重写（no export_all）和本机编译为我提供了以下运行时间：

$ erlc +native euler12.erl

$ time erl -noshell -s euler12 solve

842161320

real    0m19.468s

user    0m19.450s

sys 0m0.010s

与C代码相比，还算不错：

$ time ./a.out 

842161320

real    0m12.755s

user    0m12.730s

sys 0m0.020s

考虑到Erlang根本不适合编写数字代码，在这样的程序上，它仅比C慢50％。

最后，关于您的问题：

问题1：erlang，python和haskell是否由于使用任意长度的整数而导致速度变慢，或者只要值小于MAXINT，它们是否会变慢？

是的，有点。在Erlang中，没有办法说“结合使用32/64位算术”，因此，除非编译器可以证明整数的某些界限（通常不能这样做），否则它必须检查所有计算以查看是否可以将它们放入单个标记的单词中，或者是否必须将它们转换为堆分配的bignum。即使在运行时实际上没有使用大数，也必须执行这些检查。另一方面，这意味着您知道，如果您突然给它比以前更大的输入，该算法将永远不会因为意外的整数环绕而失败。

问题4：我的功能实现是否允许LCO，从而避免在调用堆栈中添加不必要的帧？

是的，您的Erlang代码在上次通话优化方面是正确的。