Haftungsausschluss
Ich weiß, dass künstliche Benchmarks böse sind. Sie können Ergebnisse nur für eine ganz bestimmte enge Situation anzeigen. Ich gehe nicht davon aus, dass eine Sprache wegen der dummen Bank besser ist als die andere. Ich frage mich jedoch, warum die Ergebnisse so unterschiedlich sind. Bitte sehen Sie meine Fragen unten.
Beschreibung des mathematischen Benchmarks
Benchmark ist eine einfache mathematische Berechnung, um Paare von Primzahlen zu finden, die sich um 6 unterscheiden (sogenannte sexy Primzahlen ). ZB wären sexy Primzahlen unter 100:(5 11) (7 13) (11 17) (13 19) (17 23) (23 29) (31 37) (37 43) (41 47) (47 53) (53 59) (61 67) (67 73) (73 79) (83 89) (97 103)
Ergebnistabelle
In Tabelle: Berechnungszeit in Sekunden Ausführen: Alle außer Factor wurden in VirtualBox ausgeführt (Debian instabiler amd64-Gast, Windows 7 x64-Host). CPU: AMD A4-3305M
Sexy primes up to: 10k 20k 30k 100k
Bash 58.00 200.00 [*1] [*1]
C 0.20 0.65 1.42 15.00
Clojure1.4 4.12 8.32 16.00 137.93
Clojure1.4 (optimized) 0.95 1.82 2.30 16.00
Factor n/a n/a 15.00 180.00
Python2.7 1.49 5.20 11.00 119
Ruby1.8 5.10 18.32 40.48 377.00
Ruby1.9.3 1.36 5.73 10.48 106.00
Scala2.9.2 0.93 1.41 2.73 20.84
Scala2.9.2 (optimized) 0.32 0.79 1.46 12.01
[* 1] - Ich habe Angst, mir vorzustellen, wie viel Zeit es dauern wird
Codeauflistungen
C:
int isprime(int x) {
int i;
for (i = 2; i < x; ++i)
if (x%i == 0) return 0;
return 1;
}
void findprimes(int m) {
int i;
for ( i = 11; i < m; ++i)
if (isprime(i) && isprime(i-6))
printf("%d %d\n", i-6, i);
}
main() {
findprimes(10*1000);
}
Rubin:
def is_prime?(n)
(2...n).all?{|m| n%m != 0 }
end
def sexy_primes(x)
(9..x).map do |i|
[i-6, i]
end.select do |j|
j.all?{|j| is_prime? j}
end
end
a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"
Scala:
def isPrime(n: Int) =
(2 until n) forall { n % _ != 0 }
def sexyPrimes(n: Int) =
(11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }
val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")
Scala opimiert isPrime
(die gleiche Idee wie bei der Clojure-Optimierung):
import scala.annotation.tailrec
@tailrec // Not required, but will warn if optimization doesn't work
def isPrime(n: Int, i: Int = 2): Boolean =
if (i == n) true
else if (n % i != 0) isPrime(n, i + 1)
else false
Clojure:
(defn is-prime? [n]
(every? #(> (mod n %) 0)
(range 2 n)))
(defn sexy-primes [m]
(for [x (range 11 (inc m))
:let [z (list (- x 6) x)]
:when (every? #(is-prime? %) z)]
z))
(let [a (System/currentTimeMillis)]
(println (sexy-primes (* 10 1000)))
(let [b (System/currentTimeMillis)]
(println (- b a) "mils")))
Clojure optimiert is-prime?
:
(defn ^:static is-prime? [^long n]
(loop [i (long 2)]
(if (= (rem n i) 0)
false
(if (>= (inc i) n) true (recur (inc i))))))
Python
import time as time_
def is_prime(n):
return all((n%j > 0) for j in xrange(2, n))
def primes_below(x):
return [[j-6, j] for j in xrange(9, x+1) if is_prime(j) and is_prime(j-6)]
a = int(round(time_.time() * 1000))
print(primes_below(10*1000))
b = int(round(time_.time() * 1000))
print(str((b-a)) + " mils")
Faktor
MEMO:: prime? ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;
MEMO: sexyprimes ( n n -- r r )
[a,b] [ prime? ] filter [ 6 + ] map [ prime? ] filter dup [ 6 - ] map ;
5 10 1000 * sexyprimes . .
Bash (zsh):
#!/usr/bin/zsh
function prime {
for (( i = 2; i < $1; i++ )); do
if [[ $[$1%i] == 0 ]]; then
echo 1
exit
fi
done
echo 0
}
function sexy-primes {
for (( i = 9; i <= $1; i++ )); do
j=$[i-6]
if [[ $(prime $i) == 0 && $(prime $j) == 0 ]]; then
echo $j $i
fi
done
}
sexy-primes 10000
Fragen
- Warum ist Scala so schnell? Liegt es an der statischen Eingabe ? Oder nutzt es JVM nur sehr effizient?
Warum so ein großer Unterschied zwischen Ruby und Python? Ich dachte, diese beiden sind nicht ganz anders. Vielleicht ist mein Code falsch. Bitte erleuchte mich! Vielen Dank.UPD Ja, das war ein Fehler in meinem Code. Python und Ruby 1.9 sind ziemlich gleich.- Wirklich beeindruckender Produktivitätssprung zwischen Ruby-Versionen.
- Kann ich Clojure-Code durch Hinzufügen von Typdeklarationen optimieren? Wird es helfen?
sqrt(n)
aber das kann einige Zeit dauern, um zu berechnen. Außerdem druckt Ihr C-Code die Primzahlen so aus, wie sie gefunden werden, während Ihre anderen Sprachen sie in Listen berechnen und dann ausdrucken. Während C nicht überraschend das schnellste ist, können Sie es möglicherweise schneller bekommen.C: 2.723s
Go: 2.743s
.sqrt
für diese Prüfung nicht berechnen . Sie können das Quadrat voni
wie infor (i = 2; i * i <= x; ++i) ...
isPrime
mit@tailrec
, um sicherzustellen, dass Sie die Schwanzrekursion verwenden. Es ist leicht, versehentlich etwas zu tun, das eine Schwanzrekursion verhindert, und diese Anmerkung sollte Sie warnen, wenn dies passiert.Antworten:
Grobe Antworten:
(2...n).all?
die Funktionis-prime?
in Ruby wahrscheinlich recht gut optimiert ist (BEARBEITEN: Klingt so, als wäre dies tatsächlich der Fall, siehe Julians Antwort für weitere Einzelheiten ...)Die wichtigste Optimierung im Clojure-Code wäre die Verwendung von typisierter primitiver Mathematik
is-prime?
, etwa:Mit dieser Verbesserung schaffe ich es, dass Clojure in 0,635 Sekunden 10 km zurücklegt (dh die zweitschnellste auf Ihrer Liste, die Scala besiegt).
PS: Beachten Sie, dass in einigen Fällen Druckcode in Ihrem Benchmark enthalten ist - keine gute Idee, da dies die Ergebnisse verfälscht, insbesondere wenn
print
die erstmalige Verwendung einer Funktion die Initialisierung von E / A-Subsystemen oder Ähnlichem verursacht!quelle
is-prime?
zeigt eine zweifache Verbesserung. ;)(zero? (mod n i))
sollte schneller sein als(= (mod n i) 0)
Hier ist eine schnelle Clojure-Version, die dieselben grundlegenden Algorithmen verwendet:
Es läuft ungefähr 20x schneller als Ihr Original auf meinem Computer. Und hier ist eine Version, die die neue Reduziererbibliothek in 1.5 nutzt (erfordert Java 7 oder JSR 166):
Dies läuft etwa 40x schneller als Ihr Original. Auf meinem Computer sind das 100.000 in 1,5 Sekunden.
quelle
unchecked-remainder-int
oder nurrem
anstelle vonmod
statischen Tippergebnissen führt zu einer 4-fachen Leistungssteigerung. Nett!Ich werde antworten nur # 2, da es das einzige , das ich etwas aus der Ferne , intelligent zu sagen haben, aber für Ihre Python - Code, du bist eine Zwischenliste bei der Erstellung
is_prime
, während Sie verwenden.map
in Ihremall
in Ruby , die gerade ist iterieren.Wenn Sie Ihre ändern
is_prime
zu:Sie sind auf Augenhöhe.
Ich könnte Python weiter optimieren, aber mein Ruby ist nicht gut genug, um zu wissen, wann ich einen größeren Vorteil verschafft habe (z. B.
xrange
bringt Python Python auf meinem Computer zum Gewinnen, aber ich erinnere mich nicht, ob der von Ihnen verwendete Ruby-Bereich erstellt wurde ein ganzer Bereich im Speicher oder nicht).EDIT: Ohne zu albern zu sein, lässt der Python-Code wie folgt aussehen:
Das ändert sich nicht viel mehr und bringt es für mich auf 1,5 Sekunden. Wenn ich es mit PyPy besonders albern mache, liegt es bei 0,3 Sekunden für 10.000 und 21 Sekunden für 100.000.
quelle
False
(guter Fang).xrange
! Ich habe behoben und jetzt zeigen Python und Ruby gleiche Ergebnisse.lru_cache
Implementierung für 2.7 auf AS läuft 100K in 2.3s.Sie können die Scala viel schneller machen, indem Sie Ihre
isPrime
Methode auf ändernNicht ganz so prägnant, aber das Programm läuft in 40% der Fälle!
Wir schneiden die überflüssigen
Range
und anonymenFunction
Objekte aus, der Scala-Compiler erkennt die Schwanzrekursion und wandelt sie in eine while-Schleife um, die die JVM in mehr oder weniger optimalen Maschinencode umwandeln kann, damit sie nicht zu weit vom C entfernt ist Ausführung.Siehe auch: Wie kann ich das Verständnis und die Schleifen in Scala optimieren?
quelle
i == n || n % i != 0 && isPrime(n, i + 1)
, der kürzer ist, wenn auch etwas schwerer zu lesen@tailrec
Anmerkung hinzugefügt haben , um sicherzustellen, dass diese Optimierung durchgeführt wird.Hier ist meine Scala-Version sowohl parallel als auch nicht parallel, nur zum Spaß: (Bei meiner Dual-Core-Berechnung dauert die parallele Version 335 ms, während die nicht parallele Version 655 ms dauert.)
BEARBEITEN: Gemäß dem Vorschlag von Emil H habe ich meinen Code geändert, um die Auswirkungen des Aufwärmens von E / A und JVM zu vermeiden:
Das Ergebnis zeigt in meiner Berechnung:
quelle
isSexyPrime
könnte (mehr) optimiert werden, wenn von angerufenfindPrimesPar
und nicht so sehr, wenn von angerufenfindPrimes
Kümmere dich nicht um die Benchmarks; Das Problem hat mich interessiert und ich habe einige schnelle Änderungen vorgenommen. Hierbei wird der
lru_cache
Dekorator verwendet, der eine Funktion auswendig lernt. Wenn wir also anrufenis_prime(i-6)
, bekommen wir diesen Prime Check im Grunde kostenlos. Diese Änderung halbiert die Arbeit ungefähr. Außerdem können wir dierange()
Anrufe nur durch die ungeraden Nummern führen und die Arbeit wieder ungefähr halbieren.http://en.wikipedia.org/wiki/Memoization
http://docs.python.org/dev/library/functools.html
Dies erfordert Python 3.2 oder neuer,
lru_cache
kann aber mit einem älteren Python funktionieren, wenn Sie ein Python-Rezept installieren, das bereitstelltlru_cache
. Wenn Sie Python 2.x verwenden, sollten Sie wirklichxrange()
anstelle von verwendenrange()
.http://code.activestate.com/recipes/577479-simple-caching-decorator/
Die Bearbeitung der oben genannten Informationen dauerte nur sehr kurze Zeit. Ich beschloss, noch einen Schritt weiter zu gehen und den Primer-Test nur mit Primteilern und nur bis zur Quadratwurzel der getesteten Zahl durchzuführen. Die Art und Weise, wie ich es gemacht habe, funktioniert nur, wenn Sie die Zahlen in der richtigen Reihenfolge überprüfen, damit alle Primzahlen im Laufe der Zeit akkumuliert werden können. Aber dieses Problem überprüfte bereits die Nummern in der richtigen Reihenfolge, so dass das in Ordnung war.
Auf meinem Laptop (nichts Besonderes; Prozessor ist ein 1,5-GHz-AMD Turion II "K625") lieferte diese Version in weniger als 8 Sekunden eine Antwort für 100K.
Der obige Code ist ziemlich einfach in Python, Ruby usw. zu schreiben, würde aber in C eher schmerzhaft sein.
Sie können die Zahlen dieser Version nicht mit den Zahlen der anderen Versionen vergleichen, ohne die anderen neu zu schreiben, um ähnliche Tricks anzuwenden. Ich versuche hier nichts zu beweisen; Ich dachte nur, dass das Problem Spaß macht und ich wollte sehen, welche einfachen Leistungsverbesserungen ich finden kann.
quelle
lru_cache
ist definitiv geschickt. Für bestimmte Problemklassen, wie das Erzeugen aufeinanderfolgender Fibonacci-Zahlen, kann dies eine enorme Beschleunigung bewirken, indem nur dieser eine Zeilendekorator zur Funktion hinzugefügt wird! Hier ist ein Link zu einem Vortrag von Raymond Hettinger, derlru_cache
ungefähr 26 Minuten dauert. Blip.tv/pycon-us-videos-2009-2010-2011/…lru_cache
vermeidet es, eine Berechnung zu wiederholen, die bereits kürzlich durchgeführt wurde, und das ist alles; Ich verstehe nicht, wie das "tatsächlich einen anderen Algorithmus verwendet". Und Python leidet darunter, langsam zu sein, profitiert aber von coolen Sachen wielru_cache
; Ich sehe nichts falsches daran, die nützlichen Teile einer Sprache zu verwenden. Und ich sagte, dass man die Laufzeit meiner Antwort nicht mit den anderen Sprachen vergleichen sollte, ohne ähnliche Änderungen an den anderen vorzunehmen. Ich verstehe also nicht, was du meinst.0.03
Sekunden (30
ms) .Vergiss Fortran nicht! (Meistens ein Scherz, aber ich würde eine ähnliche Leistung wie C erwarten). Die Anweisungen mit Ausrufezeichen sind optional, haben aber einen guten Stil. (
!
ist ein Kommentarzeichen in fortran 90)quelle
Ich konnte nicht widerstehen, einige der offensichtlichsten Optimierungen für die C-Version vorzunehmen, wodurch der 100k-Test auf meinem Computer jetzt 0,3 Sekunden dauerte (fünfmal schneller als die fragliche C-Version, beide mit MSVC 2010 / Ox kompiliert). .
Hier ist die identische Implementierung in Java:
Mit Java 1.7.0_04 läuft dies fast genauso schnell wie die C-Version. Die Client- oder Server-VM zeigt keinen großen Unterschied, außer dass das JIT-Training der Server-VM ein wenig zu helfen scheint (~ 3%), während es fast keine Auswirkungen auf die Client-VM hat. Die Ausgabe in Java scheint langsamer zu sein als in C. Wenn die Ausgabe in beiden Versionen durch einen statischen Zähler ersetzt wird, wird die Java-Version etwas schneller ausgeführt als die C-Version.
Dies sind meine Zeiten für den 100-km-Lauf:
und der 1M-Lauf (16386 Ergebnisse):
Dies beantwortet Ihre Fragen zwar nicht wirklich, zeigt jedoch, dass kleine Änderungen einen bemerkenswerten Einfluss auf die Leistung haben können. Um Sprachen wirklich vergleichen zu können, sollten Sie versuchen, alle algorithmischen Unterschiede so weit wie möglich zu vermeiden.
Es gibt auch einen Hinweis, warum Scala ziemlich schnell scheint. Es läuft auf der Java VM und profitiert somit von seiner beeindruckenden Leistung.
quelle
Versuchen Sie in Scala, Tuple2 anstelle von List zu verwenden. Dies sollte schneller gehen. Entfernen Sie einfach das Wort 'Liste', da (x, y) ein Tupel2 ist.
Tuple2 ist auf Int, Long und Double spezialisiert, was bedeutet, dass diese Rohdatentypen nicht ein- und ausgepackt werden müssen. Tuple2-Quelle . Liste ist nicht spezialisiert. Liste Quelle .
quelle
forall
. Ich dachte auch, dass dies möglicherweise nicht der effizienteste Code ist (mehr, weil eine große strenge Sammlung für große erstellt wird,n
anstatt nur eine Ansicht zu verwenden), aber es ist sicherlich kurz + elegant, und ich war überrascht, wie gut es trotz der Verwendung von a funktioniert viel funktionaler Stil.def sexyPrimes(n: Int) = (11 to n).map(i => (i-6, i)).filter({ case (i, j) => isPrime(i) && isPrime(j) })
etwa 60% schneller hier, sollte also den C-Code schlagen :)collect
wesentlich langsamer. Schneller ist es, wenn Sie zuerst den Filter ausführen und dann zuordnen.withFilter
ist etwas schneller, da keine Zwischensammlungen erstellt werden.(11 to n) withFilter (i => isPrime(i - 6) && isPrime(i)) map (i => (i - 6, i))
Hier ist der Code für die Go-Version (golang.org):
Es lief genauso schnell wie die C-Version.
Verwenden eines Asus u81a Intel Core 2 Duo T6500 mit 2,1 GHz, 2 MB L2-Cache und 800 MHz FSB. 4 GB RAM
Die 100k-Version:
C: 2.723s
Go: 2.743s
Mit 1000000 (1M statt 100K):
C: 3m35.458s
Go: 3m36.259s
Aber ich denke, es wäre fair, die in Go integrierten Multithreading-Funktionen zu verwenden und diese Version mit der regulären C-Version (ohne Multithreading) zu vergleichen, nur weil es fast zu einfach ist, Multithreading mit Go durchzuführen.
Update: Ich habe eine parallele Version mit Goroutines in Go erstellt:
Die parallelisierte Version wurde in durchschnittlich 2,743 Sekunden verwendet, genau zur gleichen Zeit wie die reguläre Version.Die parallelisierte Version wurde in 1.706 Sekunden fertiggestellt. Es wurden weniger als 1,5 MB RAM verwendet.
Eine seltsame Sache: Mein Dual-Core-Kubuntu 64-Bit hat in beiden Kernen nie einen Höhepunkt erreicht. Es sah so aus, als würde Go nur einen Kern verwenden.Behoben mit einem Anruf beiruntime.GOMAXPROCS(4)
Update: Ich habe die paralellisierte Version mit bis zu 1 Million Nummern ausgeführt.
Einer meiner CPU-Kerne war die ganze Zeit zu 100% ausgelastet, während der andere überhaupt nicht verwendet wurde (ungerade). Es dauerte eine ganze Minute länger als die C- und die regulären Go-Versionen. :(Mit 1000000 (1M statt 100K):
C: 3m35.458s
Go: 3m36.259s
Go using goroutines:
3m27.137s2m16.125s
Die 100k-Version:
C: 2.723s
Go: 2.743s
Go using goroutines: 1.706s
quelle
-O3
oder besser.Nur zum Spaß gibt es hier eine parallele Ruby-Version.
Auf meinem 1,8 GHz Core i5 MacBook Air sind die Leistungsergebnisse:
Es sieht so aus, als würde die JIT der JVM Ruby im Standardfall einen schönen Leistungsschub verleihen, während echtes Multithreading JRuby dabei hilft, im Thread-Fall 50% schneller zu arbeiten. Interessanter ist, dass JRuby 1.7 den JRuby 1.6-Score um gesunde 17% verbessert!
quelle
Basierend auf der Antwort von x4u habe ich eine Scala-Version mit Rekursion geschrieben und sie verbessert, indem ich für die Prime-Check-Funktion nur zum sqrt anstelle von x / 2 gegangen bin. Ich bekomme ~ 250ms für 100k und ~ 600ms für 1M. Ich ging voran und ging in ~ 6s auf 10M.
Ich ging auch zurück und schrieb eine CoffeeScript (V8 JavaScript) -Version, die ~ 15 ms für 100.000, 250 ms für 1 Million und 6 Sekunden für 10 Millionen mit einem Zähler (ohne Berücksichtigung von E / A) erhält. Wenn ich den Ausgang einschalte, dauert es ~ 150 ms für 100k, 1s für 1M und 12s für 10M. Die Schwanzrekursion konnte hier leider nicht verwendet werden, daher musste ich sie wieder in Schleifen umwandeln.
quelle
Die Antwort auf Ihre Frage Nr. 1 lautet: Ja, die JVM ist unglaublich schnell und ja, statische Eingabe hilft.
Die JVM sollte auf lange Sicht schneller als C sein, möglicherweise sogar schneller als die Assemblersprache "Normal". Natürlich können Sie die Assemblierung jederzeit von Hand optimieren, um alles zu übertreffen, indem Sie eine manuelle Laufzeitprofilerstellung durchführen und für jede CPU eine separate Version erstellen müssen erstaunlich gut und kompetent sein.
Die Gründe für die Geschwindigkeit von Java sind:
Die JVM kann Ihren Code während der Ausführung analysieren und von Hand optimieren - zum Beispiel, wenn Sie eine Methode hatten, die zur Kompilierungszeit statisch analysiert werden konnte, um eine echte Funktion zu sein, und die JVM bemerkte, dass Sie sie häufig mit derselben aufgerufen haben Parameter, es KÖNNTE den Aufruf tatsächlich vollständig eliminieren und nur die Ergebnisse des letzten Aufrufs einspeisen (ich bin nicht sicher, ob Java dies tatsächlich genau tut, aber es macht eine Menge solcher Dinge).
Aufgrund der statischen Typisierung kann die JVM beim Kompilieren viel über Ihren Code wissen. Dadurch kann sie einige Dinge voroptimieren. Außerdem kann der Compiler jede Klasse einzeln optimieren, ohne zu wissen, wie eine andere Klasse sie verwenden möchte. Auch Java hat keine willkürlichen Zeiger auf den Speicherort, es weiß, welche Werte im Speicher geändert werden können und welche nicht und kann entsprechend optimiert werden.
Die Heap-Zuweisung ist VIEL effizienter als C, die Heap-Zuweisung von Java ähnelt eher der Stapelzuweisung von C in Bezug auf die Geschwindigkeit - und ist dennoch vielseitiger. Es wurde viel Zeit in die verschiedenen hier verwendeten Algroithims investiert, es ist eine Kunst - zum Beispiel werden alle Objekte mit einer kurzen Lebensdauer (wie die Stapelvariablen von C) einem "bekannten" freien Ort zugeordnet (keine Suche nach einem freien Platz) mit genügend Platz) und werden alle zusammen in einem einzigen Schritt freigegeben (wie ein Stack Pop).
Die JVM kann Macken über Ihre CPU-Architektur kennen und Maschinencode speziell für eine bestimmte CPU generieren.
Die JVM kann Ihren Code beschleunigen, lange nachdem Sie ihn versendet haben. Ähnlich wie das Verschieben eines Programms auf eine neue CPU es beschleunigen kann, kann das Verschieben auf eine neue Version der JVM auch enorme Geschwindigkeitsleistungen bringen, die auf CPUs zugeschnitten sind, die beim erstmaligen Kompilieren Ihres Codes noch nicht vorhanden waren, was physisch nicht möglich ist verzichten Sie auf ein Rezept.
Übrigens ist der größte Teil der schlechten Wiederholung der Java-Geschwindigkeit auf die lange Startzeit zum Laden der JVM zurückzuführen (eines Tages wird jemand die JVM in das Betriebssystem einbauen und dies wird verschwinden!) Und auf die Tatsache, dass viele Entwickler wirklich schlecht schreiben können GUI-Code (insbesondere mit Threads), der dazu führte, dass Java-GUIs häufig nicht mehr reagierten und fehlerhaft waren. Einfach zu verwendende Sprachen wie Java und VB werden durch die Tatsache verstärkt, dass die Fähigkeiten eines durchschnittlichen Programmierers tendenziell geringer sind als bei komplizierteren Sprachen.
quelle