Сравнение скорости с проектом Эйлера: C vs Python vs Erlang vs Haskell

я взял #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

Python с 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

официальный сайт

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% (118% с PyPy)


• Erlang: 436% (135% спасибо RichardC)


• Haskell: 1421%

Я полагаю, что C имеет большое преимущество, поскольку он использует long для вычислений, а не произвольные целые числа длины, как остальные три. Также не нужно сначала загружать среду выполнения (делают ли другие?).

Вопрос 1:
Теряют ли Erlang, Python и Haskell скорость из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?

вопрос 2:
Почему Хаскелл такой медлительный? Есть ли флаг компилятора, который отключает тормоза или это моя реализация? (Последнее вполне вероятно, так как Хаскелл для меня книга с семью печатями.)

Вопрос 3:
Можете ли вы предложить мне несколько советов, как оптимизировать эти реализации без изменения способа определения факторов? Оптимизация в любом случае: приятнее, быстрее, более" родной язык.

EDIT:

Вопрос 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 ("%ldn", 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