Ich schreibe eine Anwendung, die den Dijkstra-Algorithmus verwendet, um minimale Pfade im Graphen zu finden. Die Gewichte der Knoten und Kanten in dem Graphen sind float Zahlen, so dass der Algorithmus viele Arithmetik auf Gleitkommazahlen ausführt. Kann ich eine Laufzeitverbesserung erzielen, wenn ich alle Gewichte in int s umwandle? Sind int arithmetische Operationen in Java schneller, dann floaten sie?
Ich habe versucht, einen einfachen Benchmark zu schreiben, um das zu überprüfen, aber ich bin nicht mit den Ergebnissen zufrieden, die ich bekommen habe. Möglicherweise hat der Compiler einige Teile des Programms optimiert, so dass die Ergebnisse für mich nicht gut aussehen.
BEARBEITEN:
Das Problem, das ich zu lösen versuche, ist im Feld Information Retrieval. Die Anwendung sollte Antworten auf eine Abfrage zeigen, die als eine Gruppe von Schlüsselwörtern gestellt wird.
Meine Datenstruktur ist ein gewichteter gerichteter Graph. Angesichts einer Reihe von Blattknoten muss ich einen kleinsten Baum finden, der diese Knoten verbindet und dem Benutzer die Antwort zeigt. Die Gewichtungen werden durch eine Gewichtungsfunktion teilweise basierend auf der tf / idf-Technik zugewiesen. Der Benutzer weiß nicht, welche Gewichte den Knoten und Kanten zugewiesen werden, für die er nur die Antworten sehen möchte, die für die von ihm gestellte Abfrage relevant sind. So sind keine genauen Ergebnisse erforderlich, sondern nur die Möglichkeit, die Antworten nach ihren Gewichten zu benennen. Nur die native Verwendung der Gewichtungsfunktion (wie ich es erwähnt habe, basiert auf tf / idf) gibt Float-Gewichte, so dass ich Floats bisher verwendet habe.
Ich hoffe, dass dies der Frage einen Hintergrund gibt.
Wie immer bei dieser Art von Dingen sollten Sie sich einige Leistungsziele setzen und dann die App profilieren, um zu sehen, ob sie ihnen entspricht.
Oft finden Sie vielleicht überraschende Ergebnisse; dass die Zeit, die Sie benötigen, kaum vom numerischen Basistyp beeinflusst wird oder dass Ihr Algorithmus suboptimal ist.
Und in Bezug auf Compiler-Optimierungen - sie sind ein echter und gültiger Teil der Performance-Optimierung.
Wenn Typ A theoretisch schneller ist als Typ B, aber Ihr Compiler kann Typ B optimieren, um in einem echten Szenario schneller zu sein, dann ist das ein wertvoller Beweis, keine Quelle für Enttäuschungen.
für einfache Operationen int ist schneller, aber mit int müssen Sie möglicherweise mehr arbeiten, um das gleiche Ergebnis zu erhalten. z.B.
als Gleitkommazahl
%Vor%als int
%Vor%Die Extra-Division bedeutet, dass die Int-Operation länger dauern kann.
Ganzzahlige Subtraktionen sind ~ 2,5 mal schneller als doppelte Subtraktionen auf meinem Rechner. Integer-Multiplikationen sind jedoch nur ~ 1,5 mal schneller als Doppelmultiplikationen.
Der folgende Test funktioniert mit zufälligen Daten, die möglicherweise die Optimierung des Compilers verhindern.
%Vor% Im Allgemeinen sollten Sie sich aus Leistungsgründen keine Gedanken über eine Auswahl zwischen int und float machen.
Hier ist ein Auszug aus dem Anhang von Java Puzzlers :
Gleitpunktarithmetik ist ungenau. Verwenden Sie Gleitkomma nicht, wo genaue Ergebnisse erforderlich sind; Verwenden Sie stattdessen einen ganzzahligen Typ oder
BigDecimal. Bevorzugen Siedoublebisfloat.
Wenn Sie keinen wirklich guten Grund haben, sollten Sie im Allgemeinen double bis float bevorzugen, wenn Sie Gleitkommaoperationen verwenden müssen. Wenn das genaue Ergebnis gewünscht wird, verwenden Sie BigDecimal ; es wird langsamer sein, da es kein primitives ist, aber wenn Profiling nicht zeigt, dass es nicht akzeptabel ist, ist dies oft die beste Option.
Wenn Sie die Fließkommaoperation verwenden müssen, ist es nicht ratsam, dies mit int zu optimieren. Dies ist wahrscheinlich eine vorzeitige Optimierung und wird den Code nur unnötig machen. Schreiben Sie es auf die natürlichste und lesbarste Art und Weise. Verkomplizieren Sie Ihren Code nicht unnötigerweise wegen geringfügiger Leistungssteigerungen.
Wenn Sie keine Gleitkommaoperation benötigen, verwenden Sie stattdessen unbedingt int oder long .
Ich denke, die Leistung hängt sehr stark vom Algorithmus und der Plattform ab, auf der die Software läuft.
Wenn Sie Matrix- / Array-Berechnungen auf einer X86-Plattform durchführen, könnte die Laufzeitumgebung sie optimieren, um SSE zu verwenden, bei dem es sich um einen erweiterten float / double-Befehlssatz handelt.
Auf anderen Plattformen könnte die Laufzeitumgebung auf OpenCL optimiert werden (ich glaube nicht, dass irgendjemand das gerade tut, aber es könnte passieren :). Ich habe keine Ahnung, was auf einer solchen Plattform am schnellsten läuft und unter welchen Bedingungen. Es kann nur sein, dass OpenCL für eine ganzzahlige Arbeitslast optimiert ist.
Unter diesen Umständen würde ich schlussfolgern, dass es nicht sinnvoll ist, den Datentyp (float oder int) an dieser Stelle zu optimieren und nur die Lesbarkeit des Codes zu optimieren.
Wenn Ihr Code sehr leistungskritisch ist und Sie genau wissen, auf welcher Hardware das System jetzt und in Zukunft läuft, können Sie typische Workloads mit verschiedenen Algorithmen testen und denjenigen auswählen, der Ihren Anforderungen am besten entspricht.
Aber im Allgemeinen verwenden Sie einfach einen Algorithmus, den Sie verstehen können, halten Sie den Code lesbar und dadurch die Anzahl der Fehler niedrig. Schneller Code ist nicht so viel wert, wenn die Ergebnisse nicht korrekt sind:)
Tags und Links java math performance primitive