Geschwindigkeitsvergleich mit Projekt Euler: C vs. Python vs. Erlang vs. Haskell

Question

Ich habe die Problem Nr. 12 de Projekt Euler als Programmierübung und zum Vergleich meiner (sicherlich nicht optimalen) Implementierungen in C, Python, Erlang und Haskell. Um eine höhere Ausführungszeit zu erreichen, suche ich nach der ersten Dreieckszahl mit mehr als 1000 Teilern statt 500, wie im ursprünglichen Problem angegeben.

Das Ergebnis ist das folgende:

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 mit 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

Zusammenfassung:

• C: 100%
• Python: 692% (118% mit PyPy)
• Erlang: 436% (135% Dank an RichardC)
• Haskell: 1421%

Ich nehme an, dass C einen großen Vorteil hat, da es für die Berechnungen lange und nicht beliebig lange ganze Zahlen verwendet, wie die anderen drei. Außerdem muss es nicht erst eine Laufzeitumgebung laden (wie die anderen?).

Frage 1: Verlieren Erlang, Python und Haskell durch die Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit, oder verlieren sie nicht, solange die Werte kleiner als MAXINT ?

Frage 2: Warum ist Haskell so langsam? Gibt es ein Compiler-Flag, das die Bremsen ausschaltet, oder liegt es an meiner Implementierung? (Letzteres ist sehr wahrscheinlich, da Haskell für mich ein Buch mit sieben Siegeln ist).

Frage 3: Können Sie mir Tipps geben, wie ich diese Implementierungen optimieren kann, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Hinsicht: schöner, schneller, "nativer" in der Sprache.

EDITAR:

Frage 4: Erlauben meine funktionalen Implementierungen LCO (Last Call Optimization, auch bekannt als Tail Recursion Elimination) und vermeiden damit das Hinzufügen unnötiger Frames auf dem Call Stack?

Ich habe wirklich versucht, denselben Algorithmus so ähnlich wie möglich in den vier Sprachen zu implementieren, obwohl ich zugeben muss, dass meine Kenntnisse in Haskell und Erlang sehr begrenzt sind.

---

Verwendete Quellcodes:

#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

Answer 1

Ich habe die "Jannich Brendle" Version auf 1000 statt 500 geändert. Und liste das Ergebnis von euler12.bin, euler12.erl, p12dist.erl auf. Beide Erl-Codes verwenden '+native' zum Kompilieren.

zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s p12dist start
The result is: 842161320.

real    0m3.879s
user    0m14.553s
sys     0m0.314s
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s euler12 solve
842161320

real    0m10.125s
user    0m10.078s
sys     0m0.046s
zhengs-MacBook-Pro:workspace zhengzhibin$ time ./euler12.bin 
842161320

real    0m5.370s
user    0m5.328s
sys     0m0.004s
zhengs-MacBook-Pro:workspace zhengzhibin$

Answer 2

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate <= n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

gcc -lm -Ofast euler.c

Zeit ./a.out

2,79s Benutzer 0,00s System 99% CPU 2,794 insgesamt