我从Project Euler中选取了Problem #12作为编程练习,并比较了我在C、Python、Erlang和Haskell中的实现(当然不是最优的).为了获得更高的执行时间,我搜索第一个除数超过Problem #120的三角形数,而不是原始问题中所述的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

Python with PyPy:

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

Summary:

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

我认为C有很大的优势,因为它使用long进行计算,而不像其他三个整数那样使用任意长度的整数.此外,它不需要先加载运行时(其他的呢?).

Question 1: Erlang、Python和Haskell是否会因为使用任意长度的整数而降低速度,或者只要值小于MAXINT,它们就不会?

Question 2:

Question 3:个 您能给我一些提示,如何在不改变我确定因素的方式的情况下优化这些实现吗?任何方式的优化:更好、更快、更"原生"的语言.

编辑:

Question 4:

虽然我不得不承认我的Haskell和Erlang知识非常有限,但我确实try 在这四种语言中实现尽可能相似的算法.


使用的源代码:

#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 seconds
  • factorCount'分钟内,你已经不必要地拨打了fromIntegral.但是,修复不会导致任何更改(编译器很聪明,您很幸运).
  • 你用了mod,其中rem更快,也足够了.这会将时间更改为8.5 seconds.
  • factorCount'不断地应用两个永远不会改变的额外参数(numbersqrt).worker/wrapper转换为我们提供了:
 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

没错,7.95 seconds.始终是half a second faster than the C solution.如果没有-fllvm标志,我仍然得到8.182 seconds,因此NCG后端在本例中也表现良好.

结论:哈斯克尔很棒.

Resulting Code

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是否因使用

在Haskell中,使用Integer比使用Int慢,但慢多少取决于执行的计算.幸运的是(对于64位机器)Int就足够了.出于可移植性的考虑,您可能应该重写我的代码以使用Int64Word64(C不是唯一具有long的语言).

问题2:为什么哈斯克尔这么慢?是否有编译器标志 刹车还是我的执行?(后者相当于 对我来说,"哈斯克尔"大概是一本有七个印章的书.)

问题3:你能给我一些如何优化这些的提示吗

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

  • 0)通过-O2进行优化
  • 1)尽可能使用快速(特别是:可取消装箱)类型
  • 2) rem而不是mod(一个经常被遗忘的优化)和
  • 3)工作者/包装器转换(可能是最常见的优化).

问题4:我的功能实现是否允许LCO,从而

是的,这不是问题所在.干得好,很高兴你考虑到了这一点.

Python相关问答推荐

如何在BeautifulSoup/CSS Select 器中处理regex?

跳过嵌套JSON中的级别并转换为Pandas Rame

如何获取包含`try`外部堆栈的`__traceback__`属性的异常

了解如何让库认识到我具有所需的依赖项

Pandas 身上的负数造型

在使用TO_EXCEL时如何为正数加上加号?

如何从matplotlib中的Splter()中获取 colored颜色 条或图例?

如何在JAX中训练具有多输出(向量值)损失函数的梯度下降模型?

如果属性的类型是联合并使用默认值,为什么属性不能与类同名?

TypeError:Py集群库中未调整大小的对象的Len()

如何根据预定义的模板重新排序YAML键并维护注释?

如何验证像这样添加的对象属性:MyObj.newattribute=123

为什么我不能从我的Django views.py文件中导入通用部件?

如何在Python中以一种安全的方式获取Git提交散列

如何从polars中的列表中 Select 所有列

我正在试着做一个简单的程序来判断学校的一个项目的调查数据,但它不起作用,有人能帮我吗?

如何使用Python模式匹配来匹配类类型?

Django-如何通过两个相同的字段进行筛选或排除?

Shopware 6 REST-API产品更新不起作用

如何在多维情况下检验NumPy数组切片是否为副本?