Confronto di velocità con Project Euler: C vs Python vs Erlang vs Haskell



Answers

Ci sono alcuni problemi con l'implementazione di Erlang. Come base per quanto segue, il mio tempo di esecuzione misurato per il tuo programma Erlang non modificato era di 47,6 secondi, rispetto ai 12,7 secondi del codice C.

La prima cosa che dovresti fare se vuoi eseguire un codice Erlang ad alta intensità di calcolo è usare il codice nativo. La compilazione con erlc +native euler12 ha erlc +native euler12 il tempo a 41,3 secondi. Questa è comunque una velocità molto più bassa (solo il 15%) del previsto dalla compilazione nativa su questo tipo di codice, e il problema è l'uso di -compile(export_all) . Questo è utile per la sperimentazione, ma il fatto che tutte le funzioni siano potenzialmente raggiungibili dall'esterno fa sì che il compilatore nativo sia molto conservativo. (Il normale emulatore BEAM non è molto influenzato.) Sostituzione di questa dichiarazione con -export([solve/0]). offre una velocità molto migliore: 31,5 secondi (quasi il 35% dalla linea di base).

Ma il codice stesso ha un problema: per ogni iterazione nel ciclo factorCount, si esegue questo test:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

Il codice C non lo fa. In generale, può essere complicato fare un confronto equo tra le diverse implementazioni dello stesso codice, e in particolare se l'algoritmo è numerico, perché è necessario essere sicuri che stiano facendo la stessa cosa. Un leggero errore di arrotondamento in un'implementazione a causa di qualche typecast da qualche parte può far sì che faccia molte più iterazioni rispetto all'altra, anche se entrambe alla fine raggiungono lo stesso risultato.

Per eliminare questa possibile fonte di errore (e sbarazzarmi del test aggiuntivo in ogni iterazione), ho riscritto la funzione factorCount come segue, modellata sul codice 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.

Questa riscrittura, nessun export_all e la compilazione nativa mi hanno dato il seguente tempo di esecuzione:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

che non è male rispetto al codice C:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

considerando che Erlang non è affatto orientato alla scrittura di codice numerico, essendo solo il 50% più lento di C su un programma come questo è abbastanza buono.

Infine, riguardo alle tue domande:

Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Sì, un po '. In Erlang, non c'è modo di dire "usa aritmetica a 32/64 bit con wrap-around", quindi a meno che il compilatore non provi dei limiti sui tuoi numeri interi (e di solito non può farlo), deve controllare tutti i calcoli per vedere se possono rientrare in una singola parola con tag o se devono trasformarli in bignums allocati nell'heap. Anche se in pratica non vengono mai utilizzati bignum in fase di esecuzione, questi controlli dovranno essere eseguiti. D'altra parte, ciò significa che tu sai che l'algoritmo non fallirà mai a causa di un inaspettato numero intero inaspettato se improvvisamente gli dai input più grandi di prima.

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Sì, il tuo codice Erlang è corretto rispetto all'ottimizzazione dell'ultima chiamata.

Question

Ho preso il Problema # 12 da Project Euler come esercizio di programmazione e per confrontare le mie implementazioni (sicuramente non ottimali) in C, Python, Erlang e Haskell. Per ottenere tempi di esecuzione più elevati, cerco il primo numero di triangolo con più di 1000 divisori anziché 500 come indicato nel problema originale.

Il risultato è il seguente:

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

Pitone:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

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

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

Sommario:

  • C: 100%
  • Python: 692% (118% con PyPy)
  • Erlang: 436% (135% grazie a RichardC)
  • Haskell: 1421%

Suppongo che C abbia un grande vantaggio in quanto utilizza a lungo i calcoli e non gli interi di lunghezza arbitraria come gli altri tre. Inoltre non ha bisogno di caricare prima un runtime (Do gli altri?).

Domanda 1: Erlang, Python e Haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT ?

Domanda 2: Perché Haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile visto che Haskell è un libro con sette sigilli per me.)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

MODIFICARE:

Domanda 4: Le mie implementazioni funzionali consentono LCO (l'ultima ottimizzazione delle chiamate, ovvero l'eliminazione della ricorsione di coda) e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Ho davvero cercato di implementare lo stesso algoritmo il più simile possibile nelle quattro lingue, anche se devo ammettere che la mia conoscenza di Haskell ed Erlang è molto limitata.

Codici sorgente utilizzati:

#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



Trying GO:

package main

import "fmt"
import "math"

func main() {
    var n, m, c int
    for i := 1; ; i++ {
        n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
        for f := 1; f < m; f++ {
            if n % f == 0 { c++ }
    }
    c *= 2
    if m * m == n { c ++ }
    if c > 1001 {
        fmt.Println(n)
        break
        }
    }
}

I get:

original c version: 9.1690 100%
go: 8.2520 111%

But using:

package main

import (
    "math"
    "fmt"
 )

// Sieve of Eratosthenes
func PrimesBelow(limit int) []int {
    switch {
        case limit < 2:
            return []int{}
        case limit == 2:
            return []int{2}
    }
    sievebound := (limit - 1) / 2
    sieve := make([]bool, sievebound+1)
    crosslimit := int(math.Sqrt(float64(limit))-1) / 2
    for i := 1; i <= crosslimit; i++ {
        if !sieve[i] {
            for j := 2 * i * (i + 1); j <= sievebound; j += 2*i + 1 {
                sieve[j] = true
            }
        }
    }
    plimit := int(1.3*float64(limit)) / int(math.Log(float64(limit)))
    primes := make([]int, plimit)
    p := 1
    primes[0] = 2
    for i := 1; i <= sievebound; i++ {
        if !sieve[i] {
            primes[p] = 2*i + 1
            p++
            if p >= plimit {
                break
            }
        }
    }
    last := len(primes) - 1
    for i := last; i > 0; i-- {
        if primes[i] != 0 {
            break
        }
        last = i
    }
    return primes[0:last]
}



func main() {
    fmt.Println(p12())
}
// Requires PrimesBelow from utils.go
func p12() int {
    n, dn, cnt := 3, 2, 0
    primearray := PrimesBelow(1000000)
    for cnt <= 1001 {
        n++
        n1 := n
        if n1%2 == 0 {
            n1 /= 2
        }
        dn1 := 1
        for i := 0; i < len(primearray); i++ {
            if primearray[i]*primearray[i] > n1 {
                dn1 *= 2
                break
            }
            exponent := 1
            for n1%primearray[i] == 0 {
                exponent++
                n1 /= primearray[i]
            }
            if exponent > 1 {
                dn1 *= exponent
            }
            if n1 == 1 {
                break
            }
        }
        cnt = dn * dn1
        dn = dn1
    }
    return n * (n - 1) / 2
}

I get:

original c version: 9.1690 100%
thaumkid's c version: 0.1060 8650%
first go version: 8.2520 111%
second go version: 0.0230 39865%

I also tried Python3.6 and pypy3.3-5.5-alpha:

original c version: 8.629 100%
thaumkid's c version: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

and then with following code I got:

original c version: 8.629 100%
thaumkid's c version: 0.109 8650%
Python3.6: 1.489 580%
pypy3.3-5.5-alpha: 0.582 1483%

def D(N):
    if N == 1: return 1
    sqrtN = int(N ** 0.5)
    nf = 1
    for d in range(2, sqrtN + 1):
        if N % d == 0:
            nf = nf + 1
    return 2 * nf - (1 if sqrtN**2 == N else 0)

L = 1000
Dt, n = 0, 0

while Dt <= L:
    t = n * (n + 1) // 2
    Dt = D(n/2)*D(n+1) if n%2 == 0 else D(n)*D((n+1)/2)
    n = n + 1

print (t)



Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

L'implementazione C è subottimale (come suggerito da Thomas M. DuBuisson), la versione utilizza interi a 64 bit (cioè un tipo di dati lungo ). Analizzerò l'elenco di assembly più tardi, ma con un'ipotesi plausibile, ci sono alcuni accessi di memoria in corso nel codice compilato, che rendono l'uso di numeri interi a 64 bit molto più lento. È quello o il codice generato (sia che sia possibile inserire meno di 64 bit in un registro SSE o arrotondare un doppio a un intero a 64 bit è più lento).

Ecco il codice modificato (semplicemente sostituisci long con int e I in modo esplicito in factorCount, anche se non penso che questo sia necessario con gcc -O3):

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

static inline int factorCount(int n)
{
    double square = sqrt (n);
    int isquare = (int)square;
    int count = isquare == square ? -1 : 0;
    int candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

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

Running + timing dà:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Come riferimento, l'implementazione haskell di Thomas nella risposta precedente fornisce:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

Conclusione: non prendere nulla da ghc, è un ottimo compilatore, ma gcc normalmente genera codice più veloce.




Some more numbers and explanations for the C version. Apparently noone did it during all those years. Remember to upvote this answer so it can get on top for everyone to see and learn.

Step One: Benchmark of the author's programs

Laptop Specifications:

  • CPU i3 M380 (931 MHz - maximum battery saving mode)
  • 4GB memory
  • Win7 64 bits
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin with gcc 4.9.3
  • Python 2.7.10

Commands:

compiling on VS x64 command prompt > `for /f %f in ('dir /b *.c') do cl /O2 /Ot /Ox %f -o %f_x64_vs2012.exe`
compiling on cygwin with gcc x64   > `for f in ./*.c; do gcc -m64 -O3 $f -o ${f}_x64_gcc.exe ; done`
time (unix tools) using cygwin > `for f in ./*.exe; do  echo "----------"; echo $f ; time $f ; done`

.

----------
$ time python ./original.py

real    2m17.748s
user    2m15.783s
sys     0m0.093s
----------
$ time ./original_x86_vs2012.exe

real    0m8.377s
user    0m0.015s
sys     0m0.000s
----------
$ time ./original_x64_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./original_x64_gcc.exe

real    0m20.951s
user    0m20.732s
sys     0m0.030s

Filenames are: integertype_architecture_compiler.exe

  • integertype is the same as the original program for now (more on that later)
  • architecture is x86 or x64 depending on the compiler settings
  • compiler is gcc or vs2012

Step Two: Investigate, Improve and Benchmark Again

VS is 250% faster than gcc. The two compilers should give a similar speed. Obviously, something is wrong with the code or the compiler options. Let's investigate!

The first point of interest is the integer types. Conversions can be expensive and consistency is important for better code generation & optimizations. All integers should be the same type.

It's a mixed mess of int and long right now. We're going to improve that. What type to use? The fastest. Gotta benchmark them'all!

----------
$ time ./int_x86_vs2012.exe

real    0m8.440s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int_x64_vs2012.exe

real    0m8.408s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int32_x86_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int32_x64_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x86_vs2012.exe

real    0m18.112s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x64_vs2012.exe

real    0m18.611s
user    0m0.000s
sys     0m0.015s
----------
$ time ./long_x86_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.000s
----------
$ time ./long_x64_vs2012.exe

real    0m8.440s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x86_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x64_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.015s
----------
$ time ./uint64_x86_vs2012.exe

real    0m15.428s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint64_x64_vs2012.exe

real    0m15.725s
user    0m0.015s
sys     0m0.015s
----------
$ time ./int_x64_gcc.exe

real    0m8.531s
user    0m8.329s
sys     0m0.015s
----------
$ time ./int32_x64_gcc.exe

real    0m8.471s
user    0m8.345s
sys     0m0.000s
----------
$ time ./int64_x64_gcc.exe

real    0m20.264s
user    0m20.186s
sys     0m0.015s
----------
$ time ./long_x64_gcc.exe

real    0m20.935s
user    0m20.809s
sys     0m0.015s
----------
$ time ./uint32_x64_gcc.exe

real    0m8.393s
user    0m8.346s
sys     0m0.015s
----------
$ time ./uint64_x64_gcc.exe

real    0m16.973s
user    0m16.879s
sys     0m0.030s

Integer types are int long int32_t uint32_t int64_t and uint64_t from #include <stdint.h>

There are LOTS of integer types in C, plus some signed/unsigned to play with, plus the choice to compile as x86 or x64 (not to be confused with the actual integer size). That is a lot of versions to compile and run ^^

Step Three: Understanding the Numbers

Definitive conclusions:

  • 32 bits integers are ~200% faster than 64 bits equivalents
  • unsigned 64 bits integers are 25 % faster than signed 64 bits (Unfortunately, I have no explanation for that)

Trick question: "What are the sizes of int and long in C?"
The right answer is: The size of int and long in C are not well-defined!

From the C spec:

int is at least 32 bits
long is at least an int

From the gcc man page (-m32 and -m64 flags):

The 32-bit environment sets int, long and pointer to 32 bits and generates code that runs on any i386 system.
The 64-bit environment sets int to 32 bits and long and pointer to 64 bits and generates code for AMD's x86-64 architecture.

From MSDN documentation (Data Type Ranges) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 bytes, also knows as signed
long, 4 bytes, also knows as long int and signed long int

To Conclude This: Lessons Learned

  • 32 bits integers are faster than 64 bits integers.

  • Standard integers types are not well defined in C nor C++, they vary depending on compilers and architectures. When you need consistency and predictability, use the uint32_t integer family from #include <stdint.h> .

  • Speed issues solved. All other languages are back hundreds percent behind, C & C++ win again ! They always do. The next improvement will be multithreading using OpenMP :D




I made the assumption that the number of factors is only large if the numbers involved have many small factors. So I used thaumkid's excellent algorithm, but first used an approximation to the factor count that is never too small. It's quite simple: Check for prime factors up to 29, then check the remaining number and calculate an upper bound for the nmber of factors. Use this to calculate an upper bound for the number of factors, and if that number is high enough, calculate the exact number of factors.

The code below doesn't need this assumption for correctness, but to be fast. It seems to work; only about one in 100,000 numbers gives an estimate that is high enough to require a full check.

Here's the code:

// Return at least the number of factors of n.
static uint64_t approxfactorcount (uint64_t n)
{
    uint64_t count = 1, add;

#define CHECK(d)                            \
    do {                                    \
        if (n % d == 0) {                   \
            add = count;                    \
            do { n /= d; count += add; }    \
            while (n % d == 0);             \
        }                                   \
    } while (0)

    CHECK ( 2); CHECK ( 3); CHECK ( 5); CHECK ( 7); CHECK (11); CHECK (13);
    CHECK (17); CHECK (19); CHECK (23); CHECK (29);
    if (n == 1) return count;
    if (n < 1ull * 31 * 31) return count * 2;
    if (n < 1ull * 31 * 31 * 37) return count * 4;
    if (n < 1ull * 31 * 31 * 37 * 37) return count * 8;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41) return count * 16;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43) return count * 32;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47) return count * 64;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53) return count * 128;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59) return count * 256;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61) return count * 512;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67) return count * 1024;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71) return count * 2048;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73) return count * 4096;
    return count * 1000000;
}

// Return the number of factors of n.
static uint64_t factorcount (uint64_t n)
{
    uint64_t count = 1, add;

    CHECK (2); CHECK (3);

    uint64_t d = 5, inc = 2;
    for (; d*d <= n; d += inc, inc = (6 - inc))
        CHECK (d);

    if (n > 1) count *= 2; // n must be a prime number
    return count;
}

// Prints triangular numbers with record numbers of factors.
static void printrecordnumbers (uint64_t limit)
{
    uint64_t record = 30000;

    uint64_t count1, factor1;
    uint64_t count2 = 1, factor2 = 1;

    for (uint64_t n = 1; n <= limit; ++n)
    {
        factor1 = factor2;
        count1 = count2;

        factor2 = n + 1; if (factor2 % 2 == 0) factor2 /= 2;
        count2 = approxfactorcount (factor2);

        if (count1 * count2 > record)
        {
            uint64_t factors = factorcount (factor1) * factorcount (factor2);
            if (factors > record)
            {
                printf ("%lluth triangular number = %llu has %llu factors\n", n, factor1 * factor2, factors);
                record = factors;
            }
        }
    }
}

This finds the 14,753,024th triangular with 13824 factors in about 0.7 seconds, the 879,207,615th triangular number with 61,440 factors in 34 seconds, the 12,524,486,975th triangular number with 138,240 factors in 10 minutes 5 seconds, and the 26,467,792,064th triangular number with 172,032 factors in 21 minutes 25 seconds (2.4GHz Core2 Duo), so this code takes only 116 processor cycles per number on average. The last triangular number itself is larger than 2^68, so




Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Questo è improbabile. Non posso dire molto di Erlang e Haskell (beh, forse un po 'di Haskell in basso), ma posso indicare molti altri colli di bottiglia in Python. Ogni volta che il programma tenta di eseguire un'operazione con alcuni valori in Python, dovrebbe verificare se i valori sono del tipo corretto e costa un po 'di tempo. factorCount funzione factorCount assegna solo una lista con range (1, isquare + 1) varie volte e runtime, l'allocazione della memoria con malloc è molto più lenta di iterare su un intervallo con un contatore come si fa in C. In particolare, il factorCount() è chiamato più volte e quindi assegna un sacco di liste. Inoltre, non dimentichiamo che Python è interpretato e l'interprete CPython non si concentra molto sull'ottimizzazione.

EDIT : oh, beh, noto che stai usando Python 3 quindi range() non restituisce una lista, ma un generatore. In questo caso, il mio punto sull'allocazione delle liste è metà sbagliato: la funzione alloca solo oggetti di range , che sono comunque inefficienti ma non altrettanto inefficienti quanto l'assegnazione di una lista con molti articoli.

Domanda 2: Perché haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile poichè haskell è un libro con sette sigilli per me.)

Stai usando gli Hugs ? Hugs è un interprete molto lento. Se lo stai usando, forse puoi ottenere un tempo migliore con GHC - ma io sono solo un'ipotesi incentrata sul cogit, il tipo di roba che un buon compilatore Haskell fa sotto la cappa è piuttosto affascinante e ben oltre la mia comprensione :)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

Direi che stai giocando un gioco poco divertente. La parte migliore di conoscere le varie lingue è usarle nel modo più diverso possibile :) Ma sto divagando, non ho alcuna raccomandazione per questo punto. Scusa, spero che qualcuno possa aiutarti in questo caso :)

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Per quanto mi ricordo, devi solo assicurarti che la tua chiamata ricorsiva sia l'ultimo comando prima di restituire un valore. In altre parole, una funzione come quella di seguito potrebbe utilizzare tale ottimizzazione:

def factorial(n, acc=1):
    if n > 1:
        acc = acc * n
        n = n - 1
        return factorial(n, acc)
    else:
        return acc

Tuttavia, non avresti tale ottimizzazione se la tua funzione fosse simile a quella qui sotto, perché c'è un'operazione (moltiplicazione) dopo la chiamata ricorsiva:

def factorial2(n):
    if n > 1:
        f = factorial2(n-1)
        return f*n
    else:
        return 1

Ho separato le operazioni in alcune variabili locali per chiarire quali operazioni sono state eseguite. Tuttavia, il più comune è vedere queste funzioni come sotto, ma sono equivalenti per il punto che sto facendo:

def factorial(n, acc=1):
    if n > 1:
        return factorial(n-1, acc*n)
    else:
        return acc

def factorial2(n):
    if n > 1:
        return n*factorial(n-1)
    else:
        return 1

Si noti che spetta al compilatore / interprete decidere se eseguire la ricorsione in coda. Ad esempio, l'interprete Python non lo fa se ricordo bene (ho usato Python nel mio esempio solo per la sua sintassi fluente). Ad ogni modo, se trovi cose strane come le funzioni fattoriali con due parametri (e uno dei parametri ha nomi come acc , accumulator ecc.) Ora sai perché le persone lo fanno :)




L'implementazione di Haskell potrebbe essere notevolmente accelerata utilizzando alcune funzioni dei pacchetti Haskell. In questo caso ho usato i primes, che sono stati appena installati con 'cabal install primi';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

Tempi:

Il tuo programma originale:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Migliore implementazione

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Come puoi vedere, questo viene eseguito in 38 millisecondi sulla stessa macchina in cui il tuo ha funzionato in 16 secondi :)

Comandi di compilazione:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe



#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

tempo ./a.out

2.79s utente 0.00 sistema 99% cpu 2.794 totale




Guardando la tua implementazione di Erlang. La tempistica ha incluso l'avvio dell'intera macchina virtuale, l'esecuzione del programma e l'arresto della macchina virtuale. Sono abbastanza sicuro che l'installazione e l'interruzione dell'erlang vm richiedono del tempo.

If the timing was done within the erlang virtual machine itself, results would be different as in that case we would have the actual time for only the program in question. Otherwise, i believe that the total time taken by the process of starting and loading of the Erlang Vm plus that of halting it (as you put it in your program) are all included in the total time which the method you are using to time the program is outputting. Consider using the erlang timing itself which we use when we want to time our programs within the virtual machine itself timer:tc/1 or timer:tc/2 or timer:tc/3 . In this way, the results from erlang will exclude the time taken to start and stop/kill/halt the virtual machine. That is my reasoning there, think about it, and then try your bench mark again.

I actually suggest that we try to time the program (for languages that have a runtime), within the runtime of those languages in order to get a precise value. C for example has no overhead of starting and shutting down a runtime system as does Erlang, Python and Haskell (98% sure of this - i stand correction). So (based on this reasoning) i conclude by saying that this benchmark wasnot precise /fair enough for languages running on top of a runtime system. Lets do it again with these changes.

EDIT: besides even if all the languages had runtime systems, the overhead of starting each and halting it would differ. so i suggest we time from within the runtime systems (for the languages for which this applies). The Erlang VM is known to have considerable overhead at start up!






Related