与Project Euler的速度比较：C vs Python vs Erlang vs Has

Question

我把Project Euler中的Problem #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

Python：

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

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

pypython和pypypy:

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%（有118%的Python）
• Erlang:436%（135%感谢RichardC）
• 哈斯克尔：1421%

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

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

问题2： 为什么哈斯克尔这么慢？是否有关闭刹车的编译器标志，或者它是我的实现？（后者很有可能，因为哈斯克尔对我来说是一本七印的书。）

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

编辑：

问题4： 我的函数实现是否允许LCO（last call optimization，也就是尾部递归消除）从而避免在调用堆栈中添加不必要的帧？

虽然我不得不承认我的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

在Python优化方面，除了使用PyPy（在代码没有任何变化的情况下提高了速度）之外，还可以使用pypyy的translation toolchain来编译与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本质上与您的版本相同，并带有一些附加的静态类型声明。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密集型代码似乎是优化程序的一种非常简单的方法。