我把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有一个很大的优势,因为它使用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
Erlang实现有一些问题。作为下面的基准,我测量的未修改Erlang程序的执行时间是47.6秒,而C代码是12.7秒。
如果要运行计算密集型Erlang代码,首先应该使用本机代码。使用
erlc +native euler12
编译将时间减少到41.3秒。但是,这比在这种代码上进行本机编译的速度要慢得多(仅15%),问题是使用-compile(export_all)
。这对于实验是有用的,但是所有函数都可能从外部访问这一事实导致本机编译器非常保守。(普通的光束模拟器并没有受到太大的影响)用-export([solve/0]).
代替这个声明可以获得更好的加速:31.5秒(几乎是基线的35%)。但是代码本身有一个问题:对于factorCount循环中的每个迭代,您都要执行以下测试:
C代码不会这样做。一般来说,在同一代码的不同实现之间进行公平的比较是很困难的,特别是如果算法是数值的,因为您需要确保它们实际上在做相同的事情。在一个实现中,由于某个地方的某种类型转换而导致的轻微舍入错误可能会导致它比另一个执行的迭代次数更多,即使这两个实现最终都会达到相同的结果。
为了消除这个可能的错误源(并在每次迭代中消除额外的测试),我重新编写了factorCount函数,如下所示,它紧密地模仿了C代码:
这个重写,没有
export_all
,并且是本地编译,给了我以下运行时间:与C代码相比,这还不算太糟:
考虑到Erlang根本不适合编写数字代码,在这样的程序上只比C慢50%是非常好的。
最后,关于你的问题:
问题1:erlang、python和haskell是否由于使用任意长度的整数或 它们不是只要值小于MAXINT吗?
是的,有点。在Erlang中,没有办法说“使用32/64位带环绕的算术”,因此除非编译器能够证明整数的某些界限(而且通常不能),否则它必须检查所有计算,看它们是否可以放在单个标记字中,或者是否必须将它们转换为堆分配的bignum。即使在运行时没有实际使用bignum,也必须执行这些检查。另一方面,这意味着您知道如果您突然给它比以前更大的输入,算法将永远不会因为意外的整数而失败。
问题4:我的功能实现是否允许LCO,从而避免在调用堆栈中添加不必要的帧?
是的,您的Erlang代码在上次调用优化方面是正确的。
在Python优化方面,除了使用PyPy(在代码没有任何变化的情况下提高了速度)之外,还可以使用pypyy的translation toolchain来编译与RPython兼容的版本,或者Cython来构建扩展模块,这两个模块在我的测试中都比C版本快,使用Cython模块的速度几乎是前者的两倍。作为参考,我还包括C和PyPy基准测试结果:
C(用
gcc -O3 -lm
编译)PyPy 1.5
RPython(使用最新的PyPy版本,
c2f583445aee
)Cython 0.15
RPython版本有几个关键的变化。要转换成独立程序,需要定义
target
,在本例中是main
函数。它应该接受sys.argv
,因为它是唯一的参数,并且需要返回一个int。您可以通过使用translate.py来翻译它,% translate.py euler12-rpython.py
,它将转换为C并为您编译它。Cython版本被重写为一个扩展模块
_euler12.pyx
,我从一个普通的python文件导入并调用它。_euler12.pyx
本质上与您的版本相同,并带有一些附加的静态类型声明。py使用python setup.py build_ext --inplace
具有构建扩展的标准样板。老实说,我对RPython和Cython都没有什么经验,对结果感到惊喜。如果您使用的是CPython,那么在Cython扩展模块中编写CPU密集型代码似乎是优化程序的一种非常简单的方法。
在x86 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-O3
比您的运行速度快)-O2
标志)factorCount'
代码没有显式键入,默认为Integer
(感谢Daniel在这里纠正了我的错误!)。使用Int
给出一个显式类型签名(这是标准实践),时间变为11.1秒factorCount'
中,您不必要地调用了fromIntegral
。不过,修复不会导致任何更改(编译器很聪明,很幸运)。mod
,其中rem
更快且足够。这会将时间更改为8.5秒。factorCount'
不断地应用两个从不改变的额外参数(number
,sqrt
)。worker/wrapper转换提供了:没错,7.95秒。始终比C解决方案快半秒。如果没有
-fllvm
标志,我仍然会得到8.182 seconds
,因此NCG后端在本例中也表现良好。结论:哈斯克尔真是太棒了。
结果代码
编辑:既然我们已经探讨了这个问题,让我们来回答
在Haskell中,使用
Integer
比Int
慢,但慢多少取决于执行的计算。幸运的是(对于64位计算机)Int
已经足够了。为了便于移植,您可能应该重写我的代码以使用Int64
或Word64
(C不是唯一一种使用long
的语言)。我就是这么回答的。答案是
-O2
使用优化rem
不是mod
(一个经常被遗忘的优化)和是的,那不是问题所在。干得好,很高兴你这么想。
相关问题 更多 >
编程相关推荐