与Project Euler进行速度比较：C vs Python vs Erlang vs Haskell

我将Project Euler的问题＃12作为编程练习，并比较了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

蟒蛇：

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

哈斯克尔：

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％（PyPy为118％）

Erlang：436％（135％感谢RichardC）

哈斯克尔：1421％

我认为C具有很大的优势，因为它使用很长的时间进行计算，而不是任意长度的整数作为其他三个。 也不需要首先加载运行时（其他人？）。

问题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 ("%ldn", 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

---

在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 ）。 工人/包装转换为我们提供了：

 $ 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这么慢？ 是否有编译器标志关闭刹车或者是我的实现？ （后者很可能，因为哈斯克尔是一本有七枚印章的书。）

问题3：您能否提供一些提示，告诉我如何优化这些实现而不改变我确定因素的方式？ 以任何方式优化：更好，更快，更“原生”的语言。

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

0）通过-O2使用优化

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

2） rem不是mod （经常被遗忘的优化）和

3）工人/包装转换（也许是最常见的优化）。

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

是的，那不是问题。 良好的工作，很高兴你考虑到这一点

---

Erlang的实现有一些问题。 作为以下的基准，我未测量的Erlang程序执行时间为47.6秒，而C代码为12.7秒。

如果你想运行计算密集的Erlang代码，你应该做的第一件事就是使用本地代码。 使用erlc +native euler12编译的时间缩短到41.3秒。 然而，这种代码的本机编译速度比预期的要低得多（只有15％），问题在于你使用了-compile(export_all) 。 这对实验很有用，但所有函数都可以从外部访问的事实导致本机编译器非常保守。 （普通的BEAM模拟器没有太大的影响。）用-export([solve/0]).替换这个声明-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.

这个重写，没有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位算术进行换行”，所以除非编译器能够证明整数（通常不能），否则它必须检查所有计算才能看到如果它们可以放在单个标记的单词中，或者它们必须将它们变成堆分配的bignums。 即使在运行时实际上没有使用过bignums，这些检查也必须执行。 另一方面，这意味着你知道如果突然给它比以前更大的输入，算法将永远不会失败，因为意外的整数回绕。

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

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

---

关于Python优化，除了使用PyPy（对于代码没有太大变化的相当令人印象深刻的加速），您可以使用PyPy的翻译工具链编译一个RPython兼容版本，或者使用Cython构建一个扩展模块，这比我测试中的C版快，Cython模块速度快了一倍 。 作为参考，我还包括C和PyPy基准测试结果：

C（用gcc -O3 -lm编译）

% time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

PyPy 1.5

% time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

RPython（使用最新的PyPy修订版， c2f583445aee ）

% time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

Cython 0.15

% time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

RPython版本有几个关键的变化。 要翻译成独立的程序，您需要定义您的target ，在这种情况下是main功能。 预计接受sys.argv因为它只是参数，并且需要返回一个int。 您可以使用translate.py， % translate.py euler12-rpython.py其翻译为C并将其编译为您。

# euler12-rpython.py

import math, sys

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

def main(argv):
    triangle = 1
    index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle
    return 0

if __name__ == '__main__':
    main(sys.argv)

def target(*args):
    return main, None

Cython版本被改写为扩展模块_euler12.pyx ，我从一个普通的python文件中导入和调用。 _euler12.pyx基本上与您的版本相同，并带有一些额外的静态类型声明。 setup.py使用python setup.py build_ext --inplace创建扩展的普通样板。

# _euler12.pyx
from libc.math cimport sqrt

cdef int factorCount(int n):
    cdef int candidate, isquare, count
    cdef double square
    square = 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

cpdef main():
    cdef int triangle = 1, index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle

# euler12-cython.py
import _euler12
_euler12.main()

# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("_euler12", ["_euler12.pyx"])]

setup(
  name = 'Euler12-Cython',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

我真的对RPython或Cython有很少的经验，并且对结果感到惊喜。 如果您使用的是CPython，那么在Cython扩展模块中编写CPU密集的代码位似乎是一种非常简单的优化程序的方法。

链接地址: http://www.djcxy.com/p/14117.html

上一篇: Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

下一篇: Why malloc+memset is slower than calloc?