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




performance (12)

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 :)

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 numero del primo triangolo con più di 1000 divisori anziché 500 come indicato nel problema originale.

Il risultato è il seguente:

C:

[email protected]:~/erlang$ gcc -lm -o euler12.bin euler12.c
[email protected]:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Pitone:

[email protected]:~/erlang$ time ./euler12.py 
842161320

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

Python con PyPy:

[email protected]:~/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:

[email protected]:~/erlang$ erlc euler12.erl 
[email protected]:~/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:

[email protected]:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
[email protected]:~/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

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 in seguito, ma con un'ipotesi plausibile, ci sono alcuni accessi di memoria in corso nel codice compilato, che rendono l'utilizzo 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.


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 possa provare 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 in 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.


Con Haskell, non hai davvero bisogno di pensare esplicitamente alle ricorsioni.

factorCount number = foldr factorCount' 0 [1..isquare] -
                     (fromEnum $ square == fromIntegral isquare)
    where
      square = sqrt $ fromIntegral number
      isquare = floor square
      factorCount' candidate
        | number `rem` candidate == 0 = (2 +)
        | otherwise = id

triangles :: [Int]
triangles = scanl1 (+) [1,2..]

main = print . head $ dropWhile ((< 1001) . factorCount) triangles

Nel codice precedente, ho sostituito le ricorsioni esplicite nella risposta di @Thomas con le operazioni dell'elenco comune. Il codice fa ancora esattamente la stessa cosa senza preoccuparci della ricorsione della coda. Esegue (~ 7.49s ) circa il 6% più lento della versione nella risposta di @Thomas (~ 7.04s ) sulla mia macchina con GHC 7.6.2, mentre la versione C di @Raedwulf gira ~ 3.15s . Sembra che il GHC sia migliorato nel corso dell'anno.

PS. So che è una vecchia domanda, e mi ci imbattuto in ricerche di google (ho dimenticato quello che stavo cercando, ora ...). Volevo solo commentare la domanda su LCO ed esprimere i miei sentimenti su Haskell in generale. Volevo commentare la risposta in alto, ma i commenti non consentono blocchi di codice.


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

Per quanto riguarda l'ottimizzazione di Python, oltre all'uso di PyPy (per accelerazioni piuttosto impressionanti con zero modifiche al codice), è possibile utilizzare la toolchain di traduzione di PyPy per compilare una versione compatibile con Cython o Cython per creare un modulo di estensione, entrambi che sono più veloci della versione C nei miei test, con il modulo Cython quasi due volte più veloce . Per riferimento, includo anche i risultati benchmark C e PyPy:

C (compilato con gcc -O3 -lm )

% time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

PyPy 1.5

% time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

RPython (usando l'ultima revisione PyPy, c2f583445aee )

% time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

Cython 0.15

% time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

La versione di RPython ha un paio di cambiamenti chiave. Per tradurre in un programma standalone devi definire il tuo target , che in questo caso è la funzione main . Si presuppone che accetti sys.argv poiché è solo un argomento ed è necessario per restituire un int. Puoi tradurlo usando translate.py, % translate.py euler12-rpython.py che si traduce in C e lo compila per te.

# euler12-rpython.py

import math, sys

def factorCount(n):
    square = math.sqrt(n)
    isquare = int(square)
    count = -1 if isquare == square else 0
    for candidate in xrange(1, isquare + 1):
        if not n % candidate: count += 2
    return count

def main(argv):
    triangle = 1
    index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle
    return 0

if __name__ == '__main__':
    main(sys.argv)

def target(*args):
    return main, None

La versione di Cython è stata riscritta come un modulo di estensione _euler12.pyx , che _euler12.pyx e richiamo da un normale file python. _euler12.pyx è essenzialmente uguale alla tua versione, con alcune dichiarazioni di tipo statico aggiuntive. Setup.py ha il normale boilerplate per costruire l'estensione, usando python setup.py build_ext --inplace .

# _euler12.pyx
from libc.math cimport sqrt

cdef int factorCount(int n):
    cdef int candidate, isquare, count
    cdef double square
    square = 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

cpdef main():
    cdef int triangle = 1, index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle

# euler12-cython.py
import _euler12
_euler12.main()

# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("_euler12", ["_euler12.pyx"])]

setup(
  name = 'Euler12-Cython',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Sinceramente ho avuto pochissima esperienza con RPython o Cython, e sono rimasto piacevolmente sorpreso dai risultati. Se stai usando CPython, scrivere i bit di codice a uso intensivo della CPU in un modulo di estensione Cython sembra un modo davvero semplice per ottimizzare il tuo programma.


Usando GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 su una macchina x86_64 Core2 Duo (2.5GHz), compilando usando ghc -O2 -fllvm -fforce-recomp per Haskell e gcc -O3 -lm per C.

  • La tua routine C viene eseguita in 8,4 secondi (più veloce della tua corsa probabilmente a causa di -O3 )
  • La soluzione Haskell funziona in 36 secondi (a causa del flag -O2 )
  • Il codice del tuo factorCount' non è stato digitato esplicitamente e predefinito su Integer (grazie a Daniel per correggere la mia diagnosi errata qui!). Dando una firma di tipo esplicita (che è comunque una pratica standard) usando Int e il tempo cambia a 11.1 secondi
  • in factorCount' hai inutilmente chiamato da fromIntegral . Tuttavia, una correzione non comporta alcun cambiamento (il compilatore è intelligente, fortunato per te).
  • Hai usato mod dove rem è più veloce e sufficiente. Questo cambia il tempo a 8,5 secondi .
  • factorCount' applica costantemente due argomenti extra che non cambiano mai ( number , sqrt ). Una trasformazione worker / wrapper ci dà:
 $ time ./so
 842161320  

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

Esatto, 7,95 secondi . Costantemente mezzo secondo più veloce della soluzione C. Senza il flag -fllvm sto ancora ottenendo 8.182 seconds , quindi anche il backend NCG sta andando bene in questo caso.

Conclusione: Haskell è fantastico.

Codice risultante

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

EDIT: Così ora che abbiamo esplorato questo, lascia rispondere alle 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?

In Haskell, l'uso di Integer è più lento di Int ma quanto più lento dipende dai calcoli eseguiti. Fortunatamente (per macchine a 64 bit) Int è sufficiente. Per motivi di portabilità dovresti probabilmente riscrivere il mio codice per usare Int64 o Word64 (C non è l'unica lingua con un long ).

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.)

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.

Questo è quello che ho risposto sopra. La risposta era

  • 0) Usa l'ottimizzazione tramite -O2
  • 1) Utilizzare i tipi veloci (in particolare: unbox-able) quando possibile
  • 2) rem not mod (un'ottimizzazione frequentemente dimenticata) e
  • 3) trasformazione worker / wrapper (forse l'ottimizzazione più comune).

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

Sì, non era questo il problema. Buon lavoro e felice che tu abbia preso in considerazione questo.


C ++ 11, <20ms per me - Esegui qui

Capisco che tu voglia dei suggerimenti per migliorare la tua conoscenza specifica della lingua, ma dal momento che è stato ben trattato qui, ho pensato di aggiungere un contesto per le persone che potrebbero aver guardato il commento matematico sulla tua domanda, ecc., E si sono chiesti perché questo il codice era molto più lento.

Questa risposta serve principalmente a fornire un contesto per aiutare, sperabilmente, a valutare più facilmente il codice nella domanda / altre risposte.

Questo codice utilizza solo un paio di ottimizzazioni (orribili), non correlate alla lingua utilizzata, basate su:

  1. ogni numero di traingle è della forma n (n + 1) / 2
  2. n e n + 1 sono coprimi
  3. il numero di divisori è una funzione moltiplicativa

#include <iostream>
#include <cmath>
#include <tuple>
#include <chrono>

using namespace std;

// Calculates the divisors of an integer by determining its prime factorisation.

int get_divisors(long long n)
{
    int divisors_count = 1;

    for(long long i = 2;
        i <= sqrt(n);
        /* empty */)
    {
        int divisions = 0;
        while(n % i == 0)
        {
            n /= i;
            divisions++;
        }

        divisors_count *= (divisions + 1);

        //here, we try to iterate more efficiently by skipping
        //obvious non-primes like 4, 6, etc
        if(i == 2)
            i++;
        else
            i += 2;
    }

    if(n != 1) //n is a prime
        return divisors_count * 2;
    else
        return divisors_count;
}

long long euler12()
{
    //n and n + 1
    long long n, n_p_1;

    n = 1; n_p_1 = 2;

    // divisors_x will store either the divisors of x or x/2
    // (the later iff x is divisible by two)
    long long divisors_n = 1;
    long long divisors_n_p_1 = 2;

    for(;;)
    {
        /* This loop has been unwound, so two iterations are completed at a time
         * n and n + 1 have no prime factors in common and therefore we can
         * calculate their divisors separately
         */

        long long total_divisors;                 //the divisors of the triangle number
                                                  // n(n+1)/2

        //the first (unwound) iteration

        divisors_n_p_1 = get_divisors(n_p_1 / 2); //here n+1 is even and we

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1);   //n_p_1 is now odd!

        //now the second (unwound) iteration

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1 / 2);   //n_p_1 is now even!
    }

    return (n * n_p_1) / 2;
}

int main()
{
    for(int i = 0; i < 1000; i++)
    {
        using namespace std::chrono;
        auto start = high_resolution_clock::now();
        auto result = euler12();
        auto end = high_resolution_clock::now();

        double time_elapsed = duration_cast<milliseconds>(end - start).count();

        cout << result << " " << time_elapsed << '\n';
    }
    return 0;
}

Ciò richiede in media circa 19ms per il mio desktop e 80ms per il mio laptop, ben lontano dalla maggior parte degli altri codici che ho visto qui. E ci sono, senza dubbio, molte ottimizzazioni ancora disponibili.


Modificare: case (divisor(T,round(math:sqrt(T))) > 500) of

A: case (divisor(T,round(math:sqrt(T))) > 1000) of

Questo produrrà la risposta corretta per l'esempio multiprocesso di Erlang.


Altri numeri e spiegazioni per la versione C. Apparentemente nessuno lo fece durante tutti quegli anni. Ricordati di revocare questa risposta in modo che possa essere in grado di vedere e imparare da tutti.

Primo passo: benchmark dei programmi dell'autore

Specifiche del laptop:

  • CPU i3 M380 (931 MHz - modalità di risparmio massimo della batteria)
  • Memoria da 4 GB
  • Win7 64 bit
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin con gcc 4.9.3
  • Python 2.7.10

comandi:

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

I nomi dei file sono: integertype_architecture_compiler.exe

  • integertype è lo stesso del programma originale per ora (ne riparleremo più avanti)
  • l'architettura è x86 o x64 a seconda delle impostazioni del compilatore
  • il compilatore è gcc o vs2012

Fase due: indagare, migliorare e valutare nuovamente

VS è il 250% più veloce di gcc. I due compilatori dovrebbero dare una velocità simile. Ovviamente, c'è qualcosa di sbagliato nel codice o nelle opzioni del compilatore. Investighiamo!

Il primo punto di interesse sono i tipi interi. Le conversioni possono essere costose e la coerenza è importante per una migliore generazione e ottimizzazione del codice. Tutti gli interi devono essere dello stesso tipo.

È un miscuglio misto di inte in longquesto momento. Miglioreremo questo. Che tipo usare? Il più veloce. Devo segnarli tutti quanti!

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

I tipi interi sono int long int32_t uint32_t int64_te uint64_tda#include <stdint.h>

Ci sono molti tipi interi in C, più alcuni firmati / non firmati con cui giocare, più la scelta di compilare come x86 o x64 (da non confondere con la dimensione intera effettiva). Sono molte versioni da compilare ed eseguire ^^

Terzo passo: Capire i numeri

Conclusioni definitive:

  • I numeri interi a 32 bit sono ~ 200% più veloci rispetto agli equivalenti a 64 bit
  • interi a 64 bit senza segno sono più veloci del 25% rispetto ai 64 bit con segno (purtroppo, non ho alcuna spiegazione per quello)

Domanda di trucco: "Quali sono le dimensioni di int e long in C?"
La risposta corretta è: le dimensioni di int e long in C non sono ben definite!

Dalla specifica C:

int è almeno
lungo 32 bit è almeno un int

Dalla pagina man di gcc (flag -m32 e -m64):

L'ambiente a 32 bit imposta int, long e puntatore su 32 bit e genera codice che gira su qualsiasi sistema i386.
L'ambiente a 64 bit imposta int a 32 bit, long e puntatore a 64 bit e genera il codice per l'architettura x86-64 di AMD.

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

int, 4 byte, sa anche come firmato
long, 4 byte, anche conosciuto come long int e firmato long int

Per concludere: lezioni apprese

  • 32 bit interi sono più veloci di numeri interi a 64 bit.

  • I tipi di interi standard non sono ben definiti in C o C ++, variano a seconda dei compilatori e delle architetture. Quando hai bisogno di coerenza e prevedibilità, usa la uint32_tfamiglia intera da #include <stdint.h>.

  • Problemi di velocità risolti. Tutte le altre lingue sono tornate indietro di centinaia, C & C ++ vincono di nuovo! Lo fanno sempre. Il prossimo miglioramento sarà il multithreading usando OpenMP: D


Ho ipotizzato che il numero di fattori sia grande solo se i numeri coinvolti hanno molti piccoli fattori. Quindi ho usato l'algoritmo eccellente di thaumkid, ma prima ho usato un'approssimazione del conteggio dei fattori che non è mai troppo piccola. È abbastanza semplice: controlla i fattori primi fino a 29, quindi controlla il numero rimanente e calcola un limite superiore per il numero di fattori. Usalo per calcolare un limite superiore per il numero di fattori, e se quel numero è abbastanza alto, calcola il numero esatto di fattori.

Il codice sotto non ha bisogno di questa assunzione per correttezza, ma per essere veloce. Sembra funzionare; solo circa uno su 100.000 numeri dà una stima che è abbastanza alta da richiedere un controllo completo.

Ecco il codice:

// 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;
            }
        }
    }
}

Questo trova il 14.753.024th triangolare con 13824 fattori in circa 0,7 secondi, il numero triangolare 879,207,615th con 61,440 fattori in 34 secondi, il numero triangolare 12,524,486,975th con 138,240 fattori in 10 minuti 5 secondi e il numero triangolare 26,467,792,064th con 172,032 fattori in 21 minuti e 25 secondi (Core2 Duo 2,4 GHz), quindi questo codice richiede in media solo 116 cicli del processore per numero. L'ultimo numero triangolare è più grande di 2 ^ 68, quindi


Ho modificato la versione "Jannich Brendle" a 1000 invece di 500. E elenco il risultato di euler12.bin, euler12.erl, p12dist.erl. Entrambi i codici erl usano '+ nativo' per compilare.

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$




erlang