лЗадача № 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

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% (118% с PyPy)Erlang: 436% (135% благодаря RichardC)Haskell: 1421%

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

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

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

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

РЕДАКТИРОВАТЬ:

Вопрос 4: Позволяют ли мои функциональные реализации LCO (оптимизация последнего вызова, устранение хвостовой рекурсии a.k.a) и, следовательно, избегают добавления ненужных кадров в стек вызовов?

Я действительно пытался реализовать один и тот же алгоритм, насколько это возможно, на четырех языках, хотя я должен признать, что мои знания Хаскелла и Эрланга очень ограничены.

Используемые исходные коды:

#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