为了账号安全,请及时绑定邮箱和手机立即绑定

与Euler项目的速度比较:C,Python,Erlang,Haskell

/ 猿问

与Euler项目的速度比较:C,Python,Erlang,Haskell

桃花长相依 2019-12-06 16:00:32

我已经采取了问题#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

带有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.020s

Erlang:


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

Haskell:


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具有很大的优势,因为它使用long进行计算,而不使用其他任意三个整数。另外,它不需要先加载运行时(其他是否需要加载?)。


问题1: Erlang,Python和Haskell是否会由于使用任意长度的整数而失去速度,或者只要值小于,它们就不会丢失MAXINT吗?


问题2: 为什么Haskell这么慢?是否有编译器标志可以使您刹车,或者它是我的实现?(后者很有可能是因为Haskell是一本对我有七个印章的书。)


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


编辑:


问题4: 我的函数实现是否允许LCO(最后一次调用优化,又称为尾部递归消除),从而避免在调用堆栈中添加不必要的帧?


尽管我不得不承认我的Haskell和Erlang知识非常有限,但我确实尝试过用四种语言尽可能地实现相同的算法。


查看完整描述

3 回答

?
喵喔喔

使用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,从而避免在调用堆栈中添加不必要的帧?


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


查看完整回答
反对 回复 2019-12-06
?
陪伴而非守候

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代码在上次通话优化方面是正确的。


查看完整回答
反对 回复 2019-12-06
?
慕码人2483693

关于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 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密集型代码似乎是优化程序的一种简便方法。


查看完整回答
反对 回复 2019-12-06

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信