我已将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.000sPython：
lorenzo@enzo:~/erlang$ time ./euler12.py
842161320
real 1m16.632s
user 1m16.370s
sys 0m0.250s带有 PyPy 的 Python：
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.020sErlang：
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.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
842161320
real 2m37.326s
user 2m37.240s
sys 0m0.080s概括：
我认为 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在 x86_64 Core2 Duo（2.5GHz）机器上使用GHC 7.0.3 ， gcc 4.4.6 ， Linux 2.6.29 ，对于 Haskell ghc -O2 -fllvm -fforce-recomp进行编译，对于 C 使用gcc -O3 -lm
-O3 ）-O2标志）factorCount'代码未明确输入，默认为Integer （感谢 Daniel 在这里纠正了我的误诊！）。 Int给出显式类型签名（无论如何都是标准做法），时间更改为11.1 秒factorCount'您不需要调用fromIntegral 。修复不会导致任何变化（编译器很聪明，对您来说很幸运）。rem更快且足够的地方使用了mod这将时间更改为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：您能否为我提供一些提示，说明如何在不改变因素确定方式的情况下优化这些实现？以任何方式进行优化：对语言更好，更快，更 “原生”。
这就是我上面回答的。答案是
-O2rem not mod （经常被遗忘的优化）和问题 4：我的功能实现是否允许 LCO，从而避免在调用堆栈中添加不必要的帧？
是的，这不是问题。做得好，很高兴您考虑了这一点。
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.此重写（没有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 代码在上次通话优化方面是正确的。
关于 Python 优化，除了使用 PyPy（在代码零更改的情况下实现了令人印象深刻的加速）之外，您还可以使用 PyPy 的翻译工具链来编译兼容 RPython 的版本，或者使用Cython来构建扩展模块， 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 totalPyPy 1.5
% time pypy euler12.py
842161320
pypy euler12.py
16.44s user
0.01s system
99% cpu 16.449 totalRPython（使用最新的 PyPy 修订版， c2f583445aee ）
% time ./euler12-rpython-c
842161320
./euler12-rpy-c
10.54s user 0.00s
system 99%
cpu 10.540 totalCython 0.15
% time python euler12-cython.py
842161320
python euler12-cython.py
6.27s user 0.00s
system 99%
cpu 6.274 totalRPython 版本有几个关键更改。要转换为独立程序，您需要定义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, NoneCython 版本被重写为扩展模块_euler12.pyx ，我从普通的 python 文件导入并调用了该模块。 _euler12.pyx本质上与您的版本相同，但带有一些附加的静态类型声明。 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 密集型代码似乎是优化程序的一种简便方法。