协慌网

登录 贡献 社区

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

我已将Project Euler 的问题#12作为编程练习,并比较了我在 C,Python,Erlang 和 Haskell 中的(肯定不是最优的)实现。为了获得更高的执行时间,我搜索的第一个三角形数的除数大于 1000,而不是原始问题中所述的 500。

结果如下:

C:

[email protected]:~/erlang$ gcc -lm -o euler12.bin euler12.c
[email protected]:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Python:

[email protected]:~/erlang$ time ./euler12.py 
842161320

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

带有 PyPy 的 Python:

[email protected]:~/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:

[email protected]:~/erlang$ erlc euler12.erl 
[email protected]:~/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:

[email protected]:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
[email protected]:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

概括:

  • C:100%
  • Python:692%(使用 PyPy 时为 118%)
  • Erlang:436%(RichardC 贡献了 135%)
  • 哈斯克尔:1421%

我认为 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.3gcc 4.4.6Linux 2.6.29 ,对于 Haskell ghc -O2 -fllvm -fforce-recomp进行编译,对于 C 使用gcc -O3 -lm

  • 您的 C 例程在 8.4 秒内运行(比您的运行速度更快,这可能是因为-O3
  • Haskell 解决方案可在 36 秒内运行(由于-O2标志)
  • 您的factorCount'代码未明确输入,默认为Integer (感谢 Daniel 在这里纠正了我的误诊!)。 Int给出显式类型签名(无论如何都是标准做法),时间更改为11.1 秒
  • factorCount'您不需要调用fromIntegral 。修复不会导致任何变化(编译器很聪明,对您来说很幸运)。
  • 您在rem更快且足够的地方使用了mod这将时间更改为8.5 秒
  • factorCount'不断应用两个永不改变的额外参数( numbersqrt )。工人 / 包装工人的转型为我们提供了:
$ 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就足够了。出于可移植性考虑,您可能应该重写我的代码以使用Int64Word64 (C 并不是唯一一个使用long语言)。

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

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

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

  • 0)通过-O2
  • 1)尽可能使用快速(特别是:不可装箱)类型
  • 2) rem not mod (经常被遗忘的优化)和
  • 3)worker / wrapper 转换(也许是最常见的优化)。

问题 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 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本质上与您的版本相同,但带有一些附加的静态类型声明。 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 密集型代码似乎是优化程序的一种简便方法。