Geschwindigkeitsvergleich mit Project Euler: C gegen Python gegen Erlang gegen Haskell

669

Ich habe Problem Nr. 12 von Project Euler übernommen als Programmierübung genommen und meine (sicherlich nicht optimalen) Implementierungen in C, Python, Erlang und Haskell verglichen. Um höhere Ausführungszeiten zu erzielen, suche ich nach der ersten Dreieckszahl mit mehr als 1000 Teilern anstelle von 500, wie im ursprünglichen Problem angegeben.

Das Ergebnis ist folgendes:

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 RichardC)
  • Haskell: 1421%

Ich nehme an, dass C einen großen Vorteil hat, da es Long für die Berechnungen verwendet und keine Ganzzahlen beliebiger Länge wie die anderen drei. Außerdem muss nicht zuerst eine Laufzeit geladen werden (tun die anderen?).

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

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

Frage 3: Können Sie mir einige Hinweise geben, wie Sie diese Implementierungen optimieren können, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "muttersprachlicher" in der Sprache.

BEARBEITEN:

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

Ich habe wirklich versucht, den gleichen 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
Hyperboreus
quelle
55
@Jochen (und Seth) Nicht wirklich, dass C schnell oder großartig ist, aber es wird als einfach empfunden, performanten Code zu schreiben (das mag nicht wahr sein, aber die meisten Programme scheinen in der Lage zu sein, also wahr genug). Wie ich in meiner Antwort untersuche und im Laufe der Zeit festgestellt habe, dass dies der Fall ist, ist die Fähigkeit des Programmierers und das Wissen über allgemeine Optimierungen für die ausgewählte Sprache von großer Bedeutung (insbesondere für Haskell).
Thomas M. DuBuisson
52
Gerade mit Mathematica überprüft - es dauert 0,25 Sekunden (mit C dauert es hier 6 Sekunden), und der Code ist nur : Euler12[x_Integer] := Module[{s = 1}, For[i = 2, DivisorSigma[0, s] < x, i++, s += i]; s]. Hurra!
Tsvikas
35
Gibt es noch jemanden da draußen, der sich an diese Kriege zwischen C und Versammlung erinnert? "Sicher! Sie können Ihren Code 10x schneller in C schreiben, aber kann Ihr C-Code so schnell ausgeführt werden? ..." Ich bin sicher, dass die gleichen Kämpfe zwischen Maschinencode und Assembly ausgetragen wurden.
JS.
39
@JS: Wahrscheinlich nicht, da Assembly einfach eine Reihe von Mnemonics ist, die Sie anstelle des rohen binären Maschinencodes eingeben - normalerweise besteht eine 1-1-Entsprechung zwischen ihnen.
Callum Rogers
9
die Schlussfolgerung für Haskell: -O2 gibt es ungefähr 3x schneller und Int anstelle von Integer ungefähr 4x-6x für die Gesamtgeschwindigkeit von 12x-14x und mehr.
Will Ness

Antworten:

794

Mit GHC 7.0.3, gcc 4.4.6, Linux 2.6.29auf einer x86_64 Core2 Duo (2,5 GHz) Maschine, Kompilieren mit ghc -O2 -fllvm -fforce-recompfür Haskell und gcc -O3 -lmfür C.

  • Ihre C-Routine läuft in 8,4 Sekunden (schneller als Ihr Lauf wahrscheinlich wegen -O3)
  • Die Haskell-Lösung läuft in 36 Sekunden (aufgrund der -O2Flagge)
  • Ihr factorCount'Code ist nicht explizit eingegeben und standardmäßig auf Integer(danke an Daniel für die Korrektur meiner Fehldiagnose hier!). Geben Sie eine explizite Typensignatur (was ohnehin Standard ist) mit Intund die Zeit ändert sich auf 11,1 Sekunden
  • in factorCount'hast du unnötig angerufen fromIntegral. Ein Fix führt jedoch zu keiner Änderung (der Compiler ist schlau, Glück für Sie).
  • Sie haben verwendet, modwo remschneller und ausreichend ist. Dies ändert die Zeit auf 8,5 Sekunden .
  • factorCount'wendet ständig zwei zusätzliche Argumente an, die sich nie ändern ( number, sqrt). Eine Worker / Wrapper-Transformation gibt uns:
 $ time ./so
 842161320  

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

Das ist richtig, 7,95 Sekunden . Durchweg eine halbe Sekunde schneller als die C-Lösung . Ohne die -fllvmFlagge bekomme ich immer noch 8.182 seconds, also geht es dem NCG-Backend auch in diesem Fall gut.

Fazit: Haskell ist großartig.

Resultierender Code

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: Nachdem wir das untersucht haben, wollen wir die Fragen beantworten

Frage 1: Verlieren erlang, python und haskell durch die Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit oder nicht, solange die Werte kleiner als MAXINT sind?

In Haskell ist die Verwendung Integerlangsamer als, Intaber wie viel langsamer hängt von den durchgeführten Berechnungen ab. Zum Glück (für 64-Bit-Maschinen) Intist ausreichend. Aus Gründen der Portabilität sollten Sie wahrscheinlich meinen Code neu schreiben, um ihn zu verwenden, Int64oder Word64(C ist nicht die einzige Sprache mit a long).

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

Frage 3: Können Sie mir einige Hinweise geben, wie Sie diese Implementierungen optimieren können, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "muttersprachlicher" in der Sprache.

Das habe ich oben beantwortet. Die Antwort war

  • 0) Optimierung über verwenden -O2
  • 1) Verwenden Sie nach Möglichkeit schnelle (insbesondere: nicht boxfähige) Typen
  • 2) remnicht mod(eine häufig vergessene Optimierung) und
  • 3) Worker / Wrapper-Transformation (möglicherweise die häufigste Optimierung).

Frage 4: Erlauben meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Ja, das war nicht das Problem. Gute Arbeit und froh, dass Sie darüber nachgedacht haben.

Thomas M. DuBuisson
quelle
25
@Karl Weil remeigentlich eine Unterkomponente der modOperation ist (sie sind nicht gleich). Wenn Sie in die GHC-Basisbibliothek schauen, sehen Sie modTests für verschiedene Bedingungen und passen das Vorzeichen entsprechend an. (siehe modInt#in Base.lhs)
Thomas M. DuBuisson
20
Ein weiterer Datenpunkt: Ich habe eine schnelle Haskell-Übersetzung des C-Programms geschrieben, ohne auf @ Hyperboreus 'Haskell zu achten. Es ist also ein bisschen näher an der Standard-Redewendung Haskell, und die einzige Optimierung, die ich absichtlich hinzugefügt habe, ist das Ersetzen moddurch, remnachdem ich diese Antwort gelesen habe (heh, oops). Siehe den Link für meine Timings, aber die Kurzversion ist "fast identisch mit dem C".
CA McCann
106
Obwohl die C-Version auf meinem Computer schneller lief, habe ich jetzt einen neuen Respekt vor Haskell. +1
Seth Carnegie
11
Das ist ziemlich überraschend für mich, obwohl ich es noch nicht ausprobiert habe. Da das Original factorCount'schwanzrekursiv war, hätte ich gedacht, der Compiler könnte die zusätzlichen Parameter, die nicht geändert werden, erkennen und die Schwanzrekursion nur für die sich ändernden Parameter optimieren (Haskell ist schließlich eine reine Sprache, dies sollte einfach sein). Glaubt jemand, der Compiler könnte das tun, oder sollte ich zurückgehen, um weitere theoretische Arbeiten zu lesen?
kizzx2
22
@ kizzx2: Es gibt ein GHC-Ticket , um es hinzuzufügen. Soweit ich verstanden habe, kann diese Transformation zu zusätzlichen Zuordnungen von Abschlussobjekten führen. Dies bedeutet in einigen Fällen eine schlechtere Leistung, aber wie Johan Tibell in seinem Blogbeitrag vorschlägt, kann dies vermieden werden, wenn der resultierende Wrapper eingebunden werden kann.
Hammar
224

Es gibt einige Probleme mit der Erlang-Implementierung. Als Basis für das Folgende betrug meine gemessene Ausführungszeit für Ihr unverändertes Erlang-Programm 47,6 Sekunden, verglichen mit 12,7 Sekunden für den C-Code.

Das erste, was Sie tun sollten, wenn Sie rechenintensiven Erlang-Code ausführen möchten, ist die Verwendung von nativem Code. Beim Kompilieren erlc +native euler12wurde die Zeit auf 41,3 Sekunden reduziert. Dies ist jedoch eine viel geringere Beschleunigung (nur 15%) als von der nativen Kompilierung für diese Art von Code erwartet, und das Problem ist Ihre Verwendung von -compile(export_all). Dies ist nützlich für Experimente, aber die Tatsache, dass alle Funktionen möglicherweise von außen erreichbar sind, führt dazu, dass der native Compiler sehr konservativ ist. (Der normale BEAM-Emulator ist nicht so stark betroffen.) Das Ersetzen dieser Deklaration durch -export([solve/0]).führt zu einer viel besseren Beschleunigung: 31,5 Sekunden (fast 35% gegenüber der Basislinie).

Der Code selbst hat jedoch ein Problem: Für jede Iteration in der factorCount-Schleife führen Sie diesen Test durch:

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

Der C-Code macht das nicht. Im Allgemeinen kann es schwierig sein, einen fairen Vergleich zwischen verschiedenen Implementierungen desselben Codes vorzunehmen, insbesondere wenn der Algorithmus numerisch ist, da Sie sicher sein müssen, dass sie tatsächlich dasselbe tun. Ein leichter Rundungsfehler in einer Implementierung aufgrund einer Typumwandlung kann dazu führen, dass viel mehr Iterationen als in der anderen ausgeführt werden, obwohl beide letztendlich das gleiche Ergebnis erzielen.

Um diese mögliche Fehlerquelle zu beseitigen (und den zusätzlichen Test in jeder Iteration zu beseitigen), habe ich die Funktion factorCount wie folgt umgeschrieben, die eng an den C-Code angelehnt ist:

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.

Diese Umschreibung, nein export_all, und native Kompilierung gab mir die folgende Laufzeit:

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

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

was im Vergleich zum C-Code nicht schlecht ist:

$ time ./a.out 
842161320

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

wenn man bedenkt, dass Erlang überhaupt nicht darauf ausgerichtet ist, numerischen Code zu schreiben, ist es ziemlich gut, in einem Programm wie diesem nur 50% langsamer als C zu sein.

Zum Schluss noch zu Ihren Fragen:

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

Ja, etwas. In Erlang gibt es keine Möglichkeit zu sagen, dass "32/64-Bit-Arithmetik mit Wrap-Around verwendet wird". Wenn der Compiler also keine Grenzen für Ihre Ganzzahlen nachweisen kann (und dies normalerweise nicht kann), muss er alle Berechnungen überprüfen, um zu sehen ob sie in ein einzelnes getaggtes Wort passen oder ob es sie in Heap-zugewiesene Bignums verwandeln muss. Auch wenn in der Praxis zur Laufzeit niemals Bignums verwendet werden, müssen diese Überprüfungen durchgeführt werden. Auf der anderen Seite bedeutet dies, dass Sie wissen, dass der Algorithmus niemals aufgrund eines unerwarteten Integer-Wraparounds fehlschlagen wird, wenn Sie ihm plötzlich größere Eingaben als zuvor geben.

Frage 4: Erlauben meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Ja, Ihr Erlang-Code ist in Bezug auf die Optimierung des letzten Anrufs korrekt.

RichardC
quelle
2
Ich stimme mit Ihnen ein. Dieser Benchmark war aus mehreren Gründen nicht genau für Erlang
Muzaaya Joshua
156

In Bezug auf die Python-Optimierung können Sie zusätzlich zur Verwendung von PyPy (für beeindruckende Beschleunigungen ohne Änderung Ihres Codes) die Übersetzungs-Toolchain von PyPy verwenden , um eine RPython-kompatible Version zu kompilieren, oder Cython , um ein Erweiterungsmodul zu erstellen Diese sind in meinen Tests schneller als die C-Version, wobei das Cython-Modul fast doppelt so schnell ist . Als Referenz füge ich auch C- und PyPy-Benchmark-Ergebnisse hinzu:

C (zusammengestellt mit 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 (mit der neuesten PyPy-Version 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

Die RPython-Version enthält einige wichtige Änderungen. Um in ein eigenständiges Programm zu übersetzen, müssen Sie Ihr definieren target, was in diesem Fall die mainFunktion ist. Es wird erwartet, dass sys.argves als einziges Argument akzeptiert wird , und es ist erforderlich, ein int zurückzugeben. Sie können es mit translate.py übersetzen, % translate.py euler12-rpython.pydas in C übersetzt und für Sie kompiliert wird.

# 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

Die Cython-Version wurde als Erweiterungsmodul umgeschrieben _euler12.pyx, das ich aus einer normalen Python-Datei importiere und aufrufe. Das _euler12.pyxist im Wesentlichen dasselbe wie Ihre Version, mit einigen zusätzlichen statischen Typdeklarationen. Die setup.py hat die normale Boilerplate, um die Erweiterung mit zu erstellen 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
)

Ich habe ehrlich gesagt sehr wenig Erfahrung mit RPython oder Cython und war angenehm überrascht über die Ergebnisse. Wenn Sie CPython verwenden, scheint das Schreiben Ihrer CPU-intensiven Codebits in ein Cython-Erweiterungsmodul eine wirklich einfache Möglichkeit zu sein, Ihr Programm zu optimieren.

Zeekay
quelle
6
Ich bin gespannt, ob die C-Version so optimiert werden kann, dass sie mindestens so schnell wie CPython ist.
Anzeigename
4
@ SargeBorsch, dass die Cython-Version so schnell ist, weil sie zu einer hochoptimierten C-Quelle kompiliert wird, was bedeutet, dass Sie diese Leistung sicher aus C.
herausholen können
72

Frage 3: Können Sie mir einige Hinweise geben, wie Sie diese Implementierungen optimieren können, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "muttersprachlicher" in der Sprache.

Die C-Implementierung ist suboptimal (wie von Thomas M. DuBuisson angedeutet), die Version verwendet 64-Bit-Ganzzahlen (dh langen Datentyp). Ich werde die Assembly-Liste später untersuchen, aber mit einer fundierten Vermutung gibt es einige Speicherzugriffe im kompilierten Code, die die Verwendung von 64-Bit-Ganzzahlen erheblich verlangsamen. Es ist dieser oder generierter Code (sei es die Tatsache, dass Sie weniger 64-Bit-Ints in ein SSE-Register einpassen oder ein Double auf eine 64-Bit-Integer runden können, ist langsamer).

Hier ist der geänderte Code (ersetzen Sie einfach long durch int und ich habe factorCount explizit eingefügt, obwohl ich nicht denke, dass dies mit gcc -O3 notwendig ist):

#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);
}

Laufen + Timing gibt es:

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

Als Referenz gibt die Haskell-Implementierung von Thomas in der früheren Antwort:

$ 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

Fazit: Wenn Sie ghc nichts wegnehmen, ist es ein großartiger Compiler, aber gcc generiert normalerweise schnelleren Code.

Raedwulf
quelle
22
Sehr schön! Zum Vergleich: Auf meinem Computer wird Ihre C-Lösung ausgeführt, 2.5 secondswährend eine ähnliche Änderung des Haskell-Codes (Verschieben auf Word32, Hinzufügen von INLINE-Pragma) zu einer Laufzeit von führt 4.8 seconds. Vielleicht kann etwas getan werden (nicht trivial, wie es scheint) - das gcc-Ergebnis ist sicherlich beeindruckend.
Thomas M. DuBuisson
1
Vielen Dank! Vielleicht sollte die Frage eher die Geschwindigkeit der kompilierten Ausgabe durch verschiedene Compiler als die eigentliche Sprache sein. Andererseits wird das Herausziehen der Intel-Handbücher und das Optimieren von Hand immer noch sofort gewinnen (vorausgesetzt, Sie haben das Wissen und die Zeit (viel)).
Raedwulf
56

Schauen Sie sich diesen Blog an . Im letzten Jahr hat er einige der Project Euler-Probleme in Haskell und Python gelöst, und er hat allgemein festgestellt, dass Haskell viel schneller ist. Ich denke, dass es zwischen diesen Sprachen mehr mit Ihrer Geläufigkeit und Ihrem Codierungsstil zu tun hat.

Wenn es um Python-Geschwindigkeit geht, verwenden Sie die falsche Implementierung! Probieren Sie PyPy aus , und für solche Dinge werden Sie feststellen, dass es viel, viel schneller ist.

agf
quelle
32

Ihre Haskell-Implementierung kann durch die Verwendung einiger Funktionen aus Haskell-Paketen erheblich beschleunigt werden. In diesem Fall habe ich Primzahlen verwendet, die nur mit 'cabal install primes' installiert werden;)

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)

Timings:

Ihr ursprüngliches Programm:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Verbesserte Implementierung

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Wie Sie sehen können, läuft dieser in 38 Millisekunden auf demselben Computer, auf dem Ihr Computer in 16 Sekunden ausgeführt wurde :)

Kompilierungsbefehle:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe
Connie Hilarides
quelle
5
Zuletzt habe ich überprüft, ob Haskell "Primzahlen" nur eine riesige Liste vorberechneter Primzahlen sind - keine Berechnung, nur Nachschlagen. Ja, das wird natürlich schneller sein, aber es sagt nichts über die Rechengeschwindigkeit beim Ableiten von Primzahlen in Haskell aus.
zxq9
21
@ zxq9 Könnten Sie mich darauf hinweisen, wo sich in der Quelle des Primzahlpakets ( hackage.haskell.org/package/primes-0.2.1.0/docs/src/… ) die Liste der Primzahlen befindet?
Fraser
4
Während die Quelle zeigt, dass die Primzahlen nicht vorberechnet sind, ist diese Beschleunigung völlig verrückt, meilenweit schneller als die C-Version. Was zum Teufel ist also los?
Semikolon
1
@semicolon Auswendiglernen. In diesem Fall denke ich, dass Haskell alle Primzahlen zur Laufzeit gespeichert hat, sodass sie nicht bei jeder Iteration neu berechnet werden müssen.
Hauleth
5
Es sind 1000 Teiler, nicht 500.
Casper Færgemand
29

Nur zum Spaß. Das Folgende ist eine "native" Haskell-Implementierung:

import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares

isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round

intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'

factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
  where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]

factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

Mit ghc -O3läuft diese konsequent in 0,55-0,58 Sekunden auf meinem Rechner (1,73 GHz Core i7).

Eine effizientere factorCount-Funktion für die C-Version:

int factorCount (int n)
{
  int count = 1;
  int candidate,tmpCount;
  while (n % 2 == 0) {
    count++;
    n /= 2;
  }
    for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
    if (n % candidate == 0) {
      tmpCount = 1;
      do {
        tmpCount++;
        n /= candidate;
      } while (n % candidate == 0);
       count*=tmpCount;
      }
  if (n > 1)
    count *= 2;
  return count;
}

Wenn Sie longs in ints in main ändern gcc -O3 -lm, läuft dies konsistent in 0,31 bis 0,35 Sekunden.

Beide können noch schneller ausgeführt werden, wenn Sie die Tatsache ausnutzen, dass die n-te Dreieckszahl = n * (n + 1) / 2 und n und (n + 1) völlig unterschiedliche Primfaktoren haben, also die Anzahl der Faktoren jeder Hälfte kann multipliziert werden, um die Anzahl der Faktoren des Ganzen zu ermitteln. Folgende:

int main ()
{
  int triangle = 0,count1,count2 = 1;
  do {
    count1 = count2;
    count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
  } while (count1*count2 < 1001);
  printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}

reduziert die Laufzeit des C-Codes auf 0,17 bis 0,19 Sekunden und kann viel größere Suchvorgänge verarbeiten - mehr als 10000 Faktoren dauern auf meinem Computer etwa 43 Sekunden. Ich überlasse dem interessierten Leser eine ähnliche Haskell-Beschleunigung.

Thaumkid
quelle
3
Nur zum Vergleich: Original c Version: 9.1690, Thaumkids Version: 0.1060 86x Verbesserung.
Thanos
Beeindruckend. Haskell ist großartig, wenn Sie abgeleitete Typen vermeiden
Piyush Katariya
Eigentlich ist es nicht die Schlussfolgerung, die es getan hat. Dies hilft Ihnen nur A) Debuggen oder Vermeiden von Typproblemen und Problemen bei der Auswahl von Typklasseninstanzen B) Debuggen und Vermeiden einiger unentscheidbarer Typprobleme mit einigen modernen Spracherweiterungen. Es hilft Ihnen auch dabei, Ihre Programme nicht zusammensetzbar zu machen, sodass Sie Ihre Entwicklungsbemühungen niemals vergrößern können.
Codeshot
c Version 0.11 s auf Intel Skull Canyon
Codeshot
13
Frage 1: Verlieren Erlang, Python und Haskell aufgrund der Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit oder nicht, solange die Werte kleiner als MAXINT sind?

Dies ist unwahrscheinlich. Ich kann nicht viel über Erlang und Haskell sagen (naja, vielleicht ein bisschen über Haskell unten), aber ich kann auf viele andere Engpässe in Python hinweisen. Jedes Mal, wenn das Programm versucht, eine Operation mit einigen Werten in Python auszuführen, sollte überprüft werden, ob die Werte vom richtigen Typ sind, und dies kostet etwas Zeit. Ihre factorCountFunktion weist nur eine Liste mit range (1, isquare + 1)verschiedenen Zeiten zu, und die mallocSpeicherzuweisung im Laufzeitstil ist viel langsamer als das Iterieren in einem Bereich mit einem Zähler wie in C. Insbesondere wird der factorCount()mehrfach aufgerufen und weist daher viele Listen zu. Vergessen wir auch nicht, dass Python interpretiert wird und der CPython-Interpreter keinen großen Fokus auf die Optimierung legt.

EDIT : Oh, nun, ich stelle fest, dass Sie Python 3 verwenden, also range()keine Liste zurückgeben, sondern einen Generator. In diesem Fall ist mein Punkt beim Zuweisen von Listen halb falsch: Die Funktion rangeweist nur Objekte zu, die zwar ineffizient, aber nicht so ineffizient sind wie das Zuweisen einer Liste mit vielen Elementen.

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

Benutzt du Umarmungen ? Hugs ist ein sehr langsamer Dolmetscher. Wenn Sie es verwenden, können Sie vielleicht eine bessere Zeit mit GHC bekommen - aber ich denke nur über Hypotese nach, die Art von Sachen, die ein guter Haskell-Compiler unter der Haube macht, ist ziemlich faszinierend und geht weit über mein Verständnis hinaus :)

Frage 3: Können Sie mir einige Hinweise geben, wie Sie diese Implementierungen optimieren können, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "muttersprachlicher" in der Sprache.

Ich würde sagen, Sie spielen ein unlustiges Spiel. Das Beste daran, verschiedene Sprachen zu kennen, ist, sie so unterschiedlich wie möglich zu verwenden :) Aber ich schweife ab, ich habe einfach keine Empfehlung für diesen Punkt. Entschuldigung, ich hoffe jemand kann dir in diesem Fall helfen :)

Frage 4: Erlauben meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Soweit ich mich erinnere, müssen Sie nur sicherstellen, dass Ihr rekursiver Aufruf der letzte Befehl ist, bevor Sie einen Wert zurückgeben. Mit anderen Worten, eine Funktion wie die folgende könnte eine solche Optimierung verwenden:

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

Sie hätten jedoch keine solche Optimierung, wenn Ihre Funktion wie die folgende wäre, da nach dem rekursiven Aufruf eine Operation (Multiplikation) erfolgt:

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

Ich habe die Operationen in einige lokale Variablen getrennt, um zu verdeutlichen, welche Operationen ausgeführt werden. Am üblichsten ist es jedoch, diese Funktionen wie folgt zu sehen, aber sie entsprechen dem Punkt, den ich anspreche:

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

Beachten Sie, dass es Sache des Compilers / Interpreters ist, zu entscheiden, ob eine Schwanzrekursion durchgeführt wird. Zum Beispiel macht der Python-Interpreter dies nicht, wenn ich mich gut erinnere (ich habe Python in meinem Beispiel nur wegen seiner fließenden Syntax verwendet). Wie auch immer, wenn Sie seltsame Sachen wie faktorielle Funktionen mit zwei Parametern (und einer der Parameter hat Namen wie finden acc, accumulatorjetzt etc.) wissen Sie , warum Menschen es tun :)

brandizzi
quelle
@ Hyperboreus danke! Ich bin auch sehr gespannt auf Ihre nächsten Fragen. Ich warne Sie jedoch, dass mein Wissen begrenzt ist, so dass ich nicht jede Ihrer Fragen beantworten konnte. Um dies zu kompensieren, habe ich mein Antwort-Community-Wiki erstellt, damit die Leute es leichter ergänzen können.
Brandizzi
Informationen zur Verwendung von Range. Wenn ich den Bereich durch eine while-Schleife mit Inkrement ersetze (imitiert die for-Schleife von C), verdoppelt sich die Ausführungszeit tatsächlich. Ich denke, Generatoren sind ziemlich optimiert.
Hyperboreus
12

Mit Haskell müssen Sie wirklich nicht explizit in Rekursionen denken.

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

Im obigen Code habe ich explizite Rekursionen in der Antwort von @Thomas durch allgemeine Listenoperationen ersetzt. Der Code macht immer noch genau das Gleiche, ohne dass wir uns um die Schwanzrekursion sorgen müssen. Es läuft (~ 7.49s ) ungefähr 6% langsamer als die Version in @Thomas 'Antwort (~ 7.04s ) auf meinem Computer mit GHC 7.6.2, während die C-Version von @Raedwulf ~ 3.15s läuft . Es scheint, dass sich GHC im Laufe des Jahres verbessert hat.

PS. Ich weiß, dass es eine alte Frage ist, und ich stolpere über sie bei Google-Suchen (ich habe vergessen, was ich jetzt gesucht habe ...). Ich wollte nur die Frage zu LCO kommentieren und meine Gefühle zu Haskell im Allgemeinen ausdrücken. Ich wollte die Top-Antwort kommentieren, aber Kommentare erlauben keine Codeblöcke.

jxy
quelle
9

Einige weitere Zahlen und Erklärungen für die C-Version. Anscheinend hat es in all den Jahren niemand getan. Denken Sie daran, diese Antwort zu verbessern, damit jeder sie sehen und lernen kann.

Erster Schritt: Benchmark der Programme des Autors

Laptop-Spezifikationen:

  • CPU i3 M380 (931 MHz - maximaler Batteriesparmodus)
  • 4 GB Speicher
  • Win7 64 Bit
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin mit gcc 4.9.3
  • Python 2.7.10

Befehle:

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

Dateinamen sind: integertype_architecture_compiler.exe

  • Der Integertyp ist vorerst derselbe wie das ursprüngliche Programm (dazu später mehr).
  • Die Architektur ist x86 oder x64, abhängig von den Compilereinstellungen
  • Compiler ist gcc oder vs2012

Schritt zwei: Erneut untersuchen, verbessern und bewerten

VS ist 250% schneller als gcc. Die beiden Compiler sollten eine ähnliche Geschwindigkeit haben. Offensichtlich stimmt etwas mit dem Code oder den Compileroptionen nicht. Lassen Sie uns untersuchen!

Der erste Punkt von Interesse sind die Ganzzahltypen. Konvertierungen können teuer sein und Konsistenz ist wichtig für eine bessere Codegenerierung und -optimierung. Alle Ganzzahlen sollten vom gleichen Typ sein.

Es ist ein gemischtes Durcheinander von intund im longMoment. Wir werden das verbessern. Welcher Typ soll verwendet werden? Das schnellste. Muss sie alle vergleichen!

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

Ganzzahlige Typen sind int long int32_t uint32_t int64_tund uint64_tvon#include <stdint.h>

Es gibt VIELE Ganzzahltypen in C sowie einige vorzeichenbehaftete / vorzeichenlose Typen zum Spielen sowie die Option zum Kompilieren als x86 oder x64 (nicht zu verwechseln mit der tatsächlichen Ganzzahlgröße). Das sind viele Versionen zum Kompilieren und Ausführen ^^

Schritt drei: Die Zahlen verstehen

Endgültige Schlussfolgerungen:

  • 32-Bit-Ganzzahlen sind ~ 200% schneller als 64-Bit-Äquivalente
  • unsigned 64 Bit ganze Zahlen sind 25% schneller als 64 Bit signed (Leider habe ich keine Erklärung dafür)

Trickfrage: "Wie groß sind int und long in C?"
Die richtige Antwort lautet: Die Größe von int und long in C ist nicht genau definiert!

Aus der C-Spezifikation:

int ist mindestens 32 Bit
lang ist mindestens ein int

Von der gcc-Manpage (-m32- und -m64-Flags):

Die 32-Bit-Umgebung setzt int, long und den Zeiger auf 32 Bit und generiert Code, der auf jedem i386-System ausgeführt wird.
Die 64-Bit-Umgebung setzt int auf 32 Bit und long und zeigt auf 64 Bit und generiert Code für die x86-64-Architektur von AMD.

Aus der MSDN-Dokumentation (Datentypbereiche) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 Bytes, weiß auch als signiertes
Long, 4 Bytes, kennt auch als Long Int und Signed Long Int

Zum Abschluss: Lessons Learned

  • 32-Bit-Ganzzahlen sind schneller als 64-Bit-Ganzzahlen.

  • Standard-Integer-Typen sind weder in C noch in C ++ gut definiert. Sie variieren je nach Compiler und Architektur. Wenn Sie Konsistenz und Vorhersagbarkeit benötigen, verwenden Sie die uint32_tGanzzahlfamilie von #include <stdint.h>.

  • Geschwindigkeitsprobleme gelöst. Alle anderen Sprachen sind hundertprozentig zurück, C & C ++ gewinnt wieder! Sie tun es immer. Die nächste Verbesserung wird Multithreading mit OpenMP sein: D.

user5994461
quelle
Wie machen es die Intel-Compiler aus Neugier? Sie sind normalerweise sehr gut darin, numerischen Code zu optimieren.
kirbyfan64sos
Wo finden Sie eine Referenz, die besagt, dass die C-Spezifikation garantiert, dass "int mindestens 32 Bit ist"? Die einzigen mir bekannten Garantien sind die Mindestgrößen von INT_MINund INT_MAX(-32767 und 32767, die praktisch eine Anforderung von intmindestens 16 Bit auferlegen ). longmuss mindestens so groß wie ein sein int, und der Mittelwert der Bereichsanforderungen longbeträgt mindestens 32 Bit.
ShadowRanger
Sie scheinen richtig zu sein. stackoverflow.com/questions/1231147/is-int-in-c-always-32-bit
user5994461
8

Betrachten Sie Ihre Erlang-Implementierung. Das Timing beinhaltete den Start der gesamten virtuellen Maschine, das Ausführen Ihres Programms und das Anhalten der virtuellen Maschine. Ich bin mir ziemlich sicher, dass das Einrichten und Stoppen des erlang vm einige Zeit in Anspruch nimmt.

Wenn das Timing innerhalb der erlang virtuellen Maschine selbst durchgeführt würde, wären die Ergebnisse unterschiedlich, da wir in diesem Fall die tatsächliche Zeit nur für das betreffende Programm hätten. Ansonsten glaube ich, dass die Gesamtzeit, die für das Starten und Laden des Erlang Vm benötigt wird, sowie die Zeit zum Anhalten (wie Sie es in Ihr Programm aufgenommen haben) in der Gesamtzeit enthalten sind, die die Methode verwendet, um die Zeit zu messen Programm wird ausgegeben. Verwenden Sie das erlang-Timing selbst, das wir verwenden, wenn wir unsere Programme innerhalb der virtuellen Maschine selbst zeitlich festlegen möchten timer:tc/1 or timer:tc/2 or timer:tc/3. Auf diese Weise schließen die Ergebnisse von erlang die Zeit aus, die zum Starten und Stoppen / Beenden / Stoppen der virtuellen Maschine benötigt wird. Das ist meine Argumentation, denken Sie darüber nach und versuchen Sie es dann erneut mit Ihrer Benchmark.

Ich schlage tatsächlich vor, dass wir versuchen, das Programm (für Sprachen mit einer Laufzeit) innerhalb der Laufzeit dieser Sprachen zeitlich festzulegen, um einen genauen Wert zu erhalten. C zum Beispiel hat keinen Aufwand für das Starten und Herunterfahren eines Laufzeitsystems, ebenso wie Erlang, Python und Haskell (98% sicher - ich stehe Korrektur). (Basierend auf dieser Überlegung) schließe ich abschließend, dass dieser Benchmark für Sprachen, die auf einem Laufzeitsystem ausgeführt werden, nicht präzise / fair genug war. Machen wir es noch einmal mit diesen Änderungen.

BEARBEITEN: Außerdem wäre der Aufwand für das Starten und Stoppen aller Sprachen unterschiedlich, selbst wenn alle Sprachen Laufzeitsysteme hätten. Daher schlage ich vor, dass wir Zeit innerhalb der Laufzeitsysteme haben (für die Sprachen, für die dies gilt). Es ist bekannt, dass die Erlang-VM beim Start einen erheblichen Overhead hat!

Muzaaya Joshua
quelle
Ich habe vergessen, es in meinem Beitrag zu erwähnen, aber ich habe die Zeit gemessen, die nur zum Starten des Systems benötigt wird (erl -noshell -s erlang halt) - ungefähr 0,1 Sekunden auf meinem Computer. Dies ist im Vergleich zur Laufzeit des Programms (ca. 10 Sekunden) so klein, dass es sich nicht lohnt, darüber zu streiten.
RichardC
auf Ihrer Maschine! Wir wissen nicht, ob Sie an einem Sonnenfeuerserver arbeiten!. Da die Zeit eine Variable ist, die proportional zu den Maschinenspezifikationen ist, sollte sie berücksichtigt werden .... Streit?
Muzaaya Joshua
2
@RichardC Nirgendwo erwähnt, dass Erlang schneller ist :) Es hat andere Ziele, nicht Geschwindigkeit!
Ausnahme
7

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

Frage eins kann für Erlang verneint werden. Die letzte Frage wird mit angemessener Verwendung von Erlang beantwortet, wie in:

http://bredsaal.dk/learning-erlang-using-projecteuler-net

Da es schneller ist als Ihr erstes C-Beispiel, würde ich vermuten, dass es zahlreiche Probleme gibt, die andere bereits ausführlich behandelt haben.

Dieses Erlang-Modul wird in etwa 5 Sekunden auf einem billigen Netbook ausgeführt ... Es verwendet das Netzwerkthread-Modell in erlang und zeigt als solches, wie das Ereignismodell genutzt werden kann. Es könnte auf viele Knoten verteilt sein. Und es ist schnell. Nicht mein Code.

-module(p12dist).  
-author("Jannich Brendle, [email protected], http://blog.bredsaal.dk").  
-compile(export_all).

server() ->  
  server(1).

server(Number) ->  
  receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},  
  server(Number+101);  
  {result,T} -> io:format("The result is: \~w.\~n", [T]);  
  _ -> server(Number)  
  end.

worker(Server_PID) ->  
  Server_PID ! {getwork, self()},  
  receive {work,Start,End} -> solve(Start,End,Server_PID)  
  end,  
  worker(Server_PID).

start() ->  
  Server_PID = spawn(p12dist, server, []),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]).

solve(N,End,_) when N =:= End -> no_solution;

solve(N,End,Server_PID) ->  
  T=round(N*(N+1)/2),
  case (divisor(T,round(math:sqrt(T))) > 500) of  
    true ->  
      Server_PID ! {result,T};  
    false ->  
      solve(N+1,End,Server_PID)  
  end.

divisors(N) ->  
  divisor(N,round(math:sqrt(N))).

divisor(_,0) -> 1;  
divisor(N,I) ->  
  case (N rem I) =:= 0 of  
  true ->  
    2+divisor(N,I-1);  
  false ->  
    divisor(N,I-1)  
  end.

Der folgende Test fand auf einer Intel (R) Atom (TM) CPU N270 bei 1,60 GHz statt

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

real    0m5.510s
user    0m5.836s
sys 0m0.152s
Mark Washeim
quelle
Wenn Sie den Wert wie folgt auf 1000 erhöhen, erhalten Sie nicht das richtige Ergebnis. Mit> 500 wie oben, neuester Test: IntelCore2 CPU 6600 @ 2.40GHz Comletes in echten 0m2.370s
Mark Washeim
Ihr Ergebnis: 76576500 Alle anderen: 842161320 Es gibt etwas Falsches an Ihrem Ergebnis
DavidDavidson
Da ich einige andere Euler-Probleme hatte, habe ich nur mein Ergebnis überprüft. Die Antwort auf projecteuler.net/problem=12 lautet 76576500, keine Frage. Ich weiß, dass es seltsam erscheint, aber ich habe es nur überprüft.
Mark Washeim
Zum Vergleich: Ich erhalte 9.03 mit der Original-C-Version, während ich Erlang 19 mit Marks Code verwende. Ich erhalte 5.406, 167.0366% schneller.
Thanos
5

C ++ 11, <20 ms für mich - Führen Sie es hier aus

Ich verstehe, dass Sie Tipps zur Verbesserung Ihrer sprachspezifischen Kenntnisse wünschen, aber da dies hier ausführlich behandelt wurde, dachte ich, ich würde einen Kontext für Personen hinzufügen, die sich möglicherweise den mathematischen Kommentar zu Ihrer Frage usw. angesehen haben, und mich gefragt haben, warum dies so ist Code war so viel langsamer.

Diese Antwort dient hauptsächlich dazu, einen Kontext bereitzustellen, der den Menschen hoffentlich hilft, den Code in Ihrer Frage / anderen Antworten leichter zu bewerten.

Dieser Code verwendet nur einige (hässliche) Optimierungen, die nicht mit der verwendeten Sprache zusammenhängen, basierend auf:

  1. Jede Traingle-Nummer hat die Form n (n + 1) / 2
  2. n und n + 1 sind Koprime
  3. Die Anzahl der Teiler ist eine multiplikative Funktion

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

Das dauert durchschnittlich 19 ms für meinen Desktop und 80 ms für meinen Laptop, weit entfernt von den meisten anderen Codes, die ich hier gesehen habe. Und es gibt zweifellos noch viele Optimierungen.

user3125280
quelle
7
Dies ist ziemlich explizit nicht das, was der Fragesteller verlangte: "Ich habe wirklich versucht, den gleichen Algorithmus so ähnlich wie möglich in den vier Sprachen zu implementieren." Um einen Kommentar zu einer der vielen gelöschten Antworten zu zitieren, die Ihrer ähnlich sind: "Es ist ziemlich offensichtlich, dass Sie mit einem besseren Algorithmus unabhängig von der Sprache schnellere Geschwindigkeiten erzielen können."
Thomas M. DuBuisson
2
@ ThomasM.DuBuisson. Darauf komme ich an. Die Frage \ Antworten impliziert stark, dass algorithmische Beschleunigungen signifikant sind (und OP fragt natürlich nicht danach), aber es gibt kein explizites Beispiel. Ich denke, diese Antwort - die nicht gerade stark optimierter Code ist - bietet einen nützlichen Kontext für jeden wie mich, der sich gefragt hat, wie langsam / schnell der Code des OP war.
user3125280
gcc kann sogar viele Muster vorberechnen. int a = 0; for (int i = 0; i <10000000; ++ i) {a + = i;} wird zur Kompilierungszeit berechnet, nehmen Sie also zur Laufzeit <1 ms. Es zählt auch
Arthur
@Thomas: Ich muss mit user3125280 zustimmen - die Sprachen verglichen werden sollten , wie sie etwas zu tun Noch Smart statt , wie sie nicht an , etwas zu tun stumm eine echte Programmiersprache zu schlagen. Intelligente Algorithmen kümmern sich normalerweise weniger um mikroskopische Effizienz als um Flexibilität, die Fähigkeit, Dinge zu verkabeln (zu kombinieren) und die Infrastruktur. Es geht nicht so sehr darum, ob man 20 ms oder 50 ms bekommt, es geht nicht um 8 Sekunden oder 8 Minuten.
DarthGizka
5

Versuch 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
        }
    }
}

Ich bekomme:

Original c Version: 9.1690 100%
gehen: 8.2520 111%

Aber mit:

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
}

Ich bekomme:

Original-C-Version: 9.1690 100%
Thaumkids C-Version: 0.1060 8650%
First-Go-Version: 8.2520 111%
Second-Go-Version: 0.0230 39865%

Ich habe auch Python3.6 und pypy3.3-5.5-alpha ausprobiert:

Original-C-Version: 8.629 100%
Thaumkids C-Version: 0.109 7916%
Python3.6: 54.795 16%
Pypy3.3-5.5-Alpha: 13.291 65%

und dann mit folgendem Code bekam ich:

Original-C-Version: 8.629 100%
Thaumkids 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)
Danke
quelle
1

Veränderung: case (divisor(T,round(math:sqrt(T))) > 500) of

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

Dies ergibt die richtige Antwort für das Erlang-Multiprozessbeispiel.

user3051214
quelle
2
War dies als Kommentar zu dieser Antwort gedacht ? Weil es nicht klar ist und dies keine Antwort für sich ist.
ShadowRanger
1

Ich ging davon aus, dass die Anzahl der Faktoren nur dann groß ist, wenn die Anzahl der beteiligten Faktoren viele kleine Faktoren enthält. Also habe ich den hervorragenden Algorithmus von thaumkid verwendet, aber zuerst eine Annäherung an die Faktoranzahl verwendet, die niemals zu klein ist. Es ist ganz einfach: Suchen Sie nach Primfaktoren bis zu 29, überprüfen Sie dann die verbleibende Zahl und berechnen Sie eine Obergrenze für die Anzahl der Faktoren. Verwenden Sie diese Option, um eine Obergrenze für die Anzahl der Faktoren zu berechnen. Wenn diese Anzahl hoch genug ist, berechnen Sie die genaue Anzahl der Faktoren.

Der folgende Code benötigt diese Annahme nicht für die Richtigkeit, sondern um schnell zu sein. Es scheint zu funktionieren; Nur etwa eine von 100.000 Zahlen gibt eine Schätzung an, die hoch genug ist, um eine vollständige Überprüfung zu erfordern.

Hier ist der 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;
            }
        }
    }
}

Dies ergibt das 14.753.024ste Dreieck mit 13824 Faktoren in etwa 0,7 Sekunden, die 879.207.615. Dreieckszahl mit 61.440 Faktoren in 34 Sekunden, die 12.524.486.975. Dreieckszahl mit 138.240 Faktoren in 10 Minuten 5 Sekunden und die 26.467.792.064. Dreieckszahl mit 172.032 Faktoren in 21 Minuten 25 Sekunden (2,4 GHz Core2 Duo), sodass dieser Code durchschnittlich nur 116 Prozessorzyklen pro Nummer benötigt. Die letzte dreieckige Zahl selbst ist also größer als 2 ^ 68

gnasher729
quelle
0

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

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$
Witeman
quelle
0
#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

user3250089
quelle