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
Euler12[x_Integer] := Module[{s = 1}, For[i = 2, DivisorSigma[0, s] < x, i++, s += i]; s]
. Hurra!Antworten:
Mit
GHC 7.0.3
,gcc 4.4.6
,Linux 2.6.29
auf einer x86_64 Core2 Duo (2,5 GHz) Maschine, Kompilieren mitghc -O2 -fllvm -fforce-recomp
für Haskell undgcc -O3 -lm
für C.-O3
)-O2
Flagge)factorCount'
Code ist nicht explizit eingegeben und standardmäßig aufInteger
(danke an Daniel für die Korrektur meiner Fehldiagnose hier!). Geben Sie eine explizite Typensignatur (was ohnehin Standard ist) mitInt
und die Zeit ändert sich auf 11,1 SekundenfactorCount'
hast du unnötig angerufenfromIntegral
. Ein Fix führt jedoch zu keiner Änderung (der Compiler ist schlau, Glück für Sie).mod
worem
schneller 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:Das ist richtig, 7,95 Sekunden . Durchweg eine halbe Sekunde schneller als die C-Lösung . Ohne die
-fllvm
Flagge bekomme ich immer noch8.182 seconds
, also geht es dem NCG-Backend auch in diesem Fall gut.Fazit: Haskell ist großartig.
Resultierender Code
EDIT: Nachdem wir das untersucht haben, wollen wir die Fragen beantworten
In Haskell ist die Verwendung
Integer
langsamer als,Int
aber wie viel langsamer hängt von den durchgeführten Berechnungen ab. Zum Glück (für 64-Bit-Maschinen)Int
ist ausreichend. Aus Gründen der Portabilität sollten Sie wahrscheinlich meinen Code neu schreiben, um ihn zu verwenden,Int64
oderWord64
(C ist nicht die einzige Sprache mit along
).Das habe ich oben beantwortet. Die Antwort war
-O2
rem
nichtmod
(eine häufig vergessene Optimierung) undJa, das war nicht das Problem. Gute Arbeit und froh, dass Sie darüber nachgedacht haben.
quelle
rem
eigentlich eine Unterkomponente dermod
Operation ist (sie sind nicht gleich). Wenn Sie in die GHC-Basisbibliothek schauen, sehen Siemod
Tests für verschiedene Bedingungen und passen das Vorzeichen entsprechend an. (siehemodInt#
inBase.lhs
)mod
durch,rem
nachdem ich diese Antwort gelesen habe (heh, oops). Siehe den Link für meine Timings, aber die Kurzversion ist "fast identisch mit dem C".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?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 euler12
wurde 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:
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:
Diese Umschreibung, nein
export_all
, und native Kompilierung gab mir die folgende Laufzeit:was im Vergleich zum C-Code nicht schlecht ist:
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.
quelle
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
)PyPy 1.5
RPython (mit der neuesten PyPy-Version
c2f583445aee
)Cython 0,15
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 diemain
Funktion ist. Es wird erwartet, dasssys.argv
es 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.py
das in C übersetzt und für Sie kompiliert wird.Die Cython-Version wurde als Erweiterungsmodul umgeschrieben
_euler12.pyx
, das ich aus einer normalen Python-Datei importiere und aufrufe. Das_euler12.pyx
ist im Wesentlichen dasselbe wie Ihre Version, mit einigen zusätzlichen statischen Typdeklarationen. Die setup.py hat die normale Boilerplate, um die Erweiterung mit zu erstellenpython setup.py build_ext --inplace
.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.
quelle
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):
Laufen + Timing gibt es:
Als Referenz gibt die Haskell-Implementierung von Thomas in der früheren Antwort:
Fazit: Wenn Sie ghc nichts wegnehmen, ist es ein großartiger Compiler, aber gcc generiert normalerweise schnelleren Code.
quelle
2.5 seconds
während eine ähnliche Änderung des Haskell-Codes (Verschieben auf Word32, Hinzufügen von INLINE-Pragma) zu einer Laufzeit von führt4.8 seconds
. Vielleicht kann etwas getan werden (nicht trivial, wie es scheint) - das gcc-Ergebnis ist sicherlich beeindruckend.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.
quelle
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;)
Timings:
Ihr ursprüngliches Programm:
Verbesserte Implementierung
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:
quelle
Nur zum Spaß. Das Folgende ist eine "native" Haskell-Implementierung:
Mit
ghc -O3
lä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:
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:
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.
quelle
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
factorCount
Funktion weist nur eine Liste mitrange (1, isquare + 1)
verschiedenen Zeiten zu, und diemalloc
Speicherzuweisung im Laufzeitstil ist viel langsamer als das Iterieren in einem Bereich mit einem Zähler wie in C. Insbesondere wird derfactorCount()
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 Funktionrange
weist nur Objekte zu, die zwar ineffizient, aber nicht so ineffizient sind wie das Zuweisen einer Liste mit vielen Elementen.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 :)
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 :)
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:
Sie hätten jedoch keine solche Optimierung, wenn Ihre Funktion wie die folgende wäre, da nach dem rekursiven Aufruf eine Operation (Multiplikation) erfolgt:
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:
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
,accumulator
jetzt etc.) wissen Sie , warum Menschen es tun :)quelle
Mit Haskell müssen Sie wirklich nicht explizit in Rekursionen denken.
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.
quelle
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:
Befehle:
.
Dateinamen sind:
integertype_architecture_compiler.exe
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
int
und imlong
Moment. Wir werden das verbessern. Welcher Typ soll verwendet werden? Das schnellste. Muss sie alle vergleichen!Ganzzahlige Typen sind
int
long
int32_t
uint32_t
int64_t
unduint64_t
von#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:
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:
Von der gcc-Manpage (-m32- und -m64-Flags):
Aus der MSDN-Dokumentation (Datentypbereiche) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :
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_t
Ganzzahlfamilie 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.
quelle
INT_MIN
undINT_MAX
(-32767 und 32767, die praktisch eine Anforderung vonint
mindestens 16 Bit auferlegen ).long
muss mindestens so groß wie ein seinint
, und der Mittelwert der Bereichsanforderungenlong
beträgt mindestens 32 Bit.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!
quelle
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.
Der folgende Test fand auf einer Intel (R) Atom (TM) CPU N270 bei 1,60 GHz statt
quelle
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:
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.
quelle
Versuch GO:
Ich bekomme:
Original c Version: 9.1690 100%
gehen: 8.2520 111%
Aber mit:
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%
quelle
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.
quelle
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:
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
quelle
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'.
quelle
gcc -lm -Ofast euler.c
Zeit ./a.out
2,79s Benutzer 0,00s System 99% CPU 2,794 insgesamt
quelle