Winkel normalisieren (360°)

tueftli

Mitglied
Hallo zusammen!

Für ein Berechnungsprogramm benötige ich eine Methode, welche mir den Wert einer Winkelangabe (in Grad) normalisiert, was heißt, dass der als Eingangsparameter übergebene Winkel positiv wie negativ und beliebig groß sein kann (von Sonderfällen wie Infinity, NaN, ... kann abgesehen werden) und der Ausgabewert einem Wert des Vollkreis-Winkels entspricht, also im Intervall [0.0, 360.0[.
Ich habe mir dazu bereits zahlreiche Gedanken gemacht und recherchiert, habe aber noch keine für mich zufriedenstellende Lösung gefunden (sofern es denn eine gibt), da die Methode in mehrfach verschachtelten Schleifen ablaufen muss und daher entsprechend performant sein sollte.

Zuerst hatte ich diese Methode entwickelt:

[CODE lang="java" title="Variante 1"]public static double normalizeAngle_1(double angle) {
if(angle >= 360.0) {
angle %= 360.0;
}
else while(angle < 0.0) {
angle += 360.0;
}
return angle;
}[/CODE]

Ja, dieses abenteuerlich anmutende else-while-Konstrukt funktioniert, braucht jedoch einiges an Rechenzeit, wenn die Beträge größer werden.


Danach habe ich einige Varianten entwickelt:

[CODE lang="java" title="Variante 2"]public static double normalizeAngle_2(double angle) {
if(angle >= 360.0) {
angle %= 360.0;
}
else if(angle < 0.0) {
angle = (360.0 + (angle % 360.0)) % 360.0;
}
return angle;
}[/CODE]

[CODE lang="java" title="Variante 3"]public static double normalizeAngle_3(double angle) {
if(angle >= 360.0) {
angle %= 360.0;
}
else if(angle < 0.0) {
angle = angle + Math.ceil(-angle / 360.0) * 360.0;
}
return angle;
}[/CODE]

[CODE lang="java" title="Variante 4"]public static double normalizeAngle_4(double angle) {
if(angle >= 360.0) {
angle %= 360.0;
}
else if(angle < 0.0) {
angle = 360.0 + (angle % 360.0);
if(angle >= 360.0) {
angle -= 360.0;
}
}
return angle;
}[/CODE]

Im Moment gehe ich davon aus, dass die 4. Variante die performanteste ist, da sie die wenigsten Modulo-Operationen und Methodenaufrufe enthält, dafür eine Fallunterscheidung mehr im worst-case. Ich frage mich, ob es nicht noch eine bessere Lösung gibt oder vielleicht eine vorgefertigte aus den Java-Bibliotheken, die ich nicht entdeckt habe...
Neben der Korrektheit ist wie gesagt die Performance wichtig und auf die Sonderfälle für die Eingangsparameter (Infinity, NaN, ...) braucht keine Rücksicht genommen zu werden!

Hat irgendjemand von euch hier bessere Vorschläge?
THX
tueftli
 

tueftli

Mitglied
Hallo, ja, so was ähnliches habe ich schon gesehen, aber ob das innerhalb von Mehfachschleifen performanter ist, glaub ich nicht, da in jedem Fall eine Modulo-Berechnung durchgeführt wird (auch wenn sie nicht nötig ist), was performancetechnisch relativ teuer ist....

Aber wenn sogar diese Quelle so eine ähnliche Lösung aufführt, dann dürfte es bei den o. g. Lösungen kaum Optimierungspotential geben, oder!?
 

Wurstkopp

Bekanntes Mitglied
Eine Modulooperation ist "Relativ teuer" bezogen auf was? Ohne jetzt irgendwas über dein Projekt zu Wissen sage ich einfach mal, dass das keine merkbaren Unterschiede macht. Wenn du deine Performance optimieren möchtest, solltest du zunächst via Benchmark deine eigentlichen Flaschenhälse wirklich nachweisbar rausfinden und nicht einfach auf gut Glück irgendetwas vermeintlich verbessern. Microbenchmarks in einzelnen Methoden ob nun eine Rechenoperation oder Abfrage mehr oder weniger ausgeführt wird sind in den allermeisten Fällen vernachlässigbar. Im Zweifel lieber stattdessen den am besten lesbaren Code bevorzugen.
 
Zuletzt bearbeitet:

tueftli

Mitglied
Das ist natürlich grundsätzlich richtig, da die JVM (z.B. Hotspot) selbst Optimierungen des Codes durchführt, die normalerweise durch manuelle Optimierungen nicht leicht zu überbieten sind!
Die genannte Methode ist übrigens einer der wesentlichen Flaschenhälse bei meinem Rechenprogramm, da sie sich im Kern von Mehrfachschleifen befindet (wir sprechen hier von vielen Millionen Ausführungen im Rahmen einer numerischen Berechnung). Darum ist mir diese Optimierung relativ wichtig...
Ich persönlich habe daher immer dem Wertevergleich den Vorzug vor der Modulooperation gegeben, weil der in Summe weniger Taktungen und damit weniger Zeit braucht...
Aber es ist durchaus möglich, so wie Du sagst, dass das hier nicht so groß ins Gewicht fällt! Aber dann ist es halt so!
 

Wurstkopp

Bekanntes Mitglied
Dann wäre es wie gesagt wichtig Benchmarks wie z.B. Harness heranzuziehen (und natürlich auch lernen wie diese richtig benutzt werden, dabei gibts nämlich viele Stolperfallen). Dann kannst grob überschlagen, wie viel performanter Variante A über B ist. Ggf. passiert das ja auch wirklich durch Dinge die man vielleicht nicht auf den 1. Blick sieht, wie z.B. die von dir erwähnten Compileroptimierungen, also z.B: ob deine Methode geinlined wird.

Und wie gesagt den ganzen Code nach Performancebremsen absuchen bzw. schauen wo die Rechenzeit wirklich hinfließt. Bei "vielen Millionen" Modulooperationen läufts bei mir jedenfalls noch nicht kalt den Rücken runter, das schaffen vermutlich selbst mittelklasse CPUs in kurzer Zeit. Kleiner Tipp: Meiner Erfahrung nach sind meistens zu viele kleine I/O Operationen der größte Zeitfresser.
 

fhoffmann

Top Contributor
Neben alle Anmerkungen zur Optimierung.
Genügt nicht einfach:
Java:
    public double normalizeAngle(double angle) {
        angle %= 360;
        if (angle < 0) {
            angle += 360;
        }
        return angle;
    }
 

mrBrown

Super-Moderator
Mitarbeiter
Die genannte Methode ist übrigens einer der wesentlichen Flaschenhälse bei meinem Rechenprogramm, da sie sich im Kern von Mehrfachschleifen befindet (wir sprechen hier von vielen Millionen Ausführungen im Rahmen einer numerischen Berechnung). Darum ist mir diese Optimierung relativ wichtig...
u.U kann man da mit expliziter Vectorization noch optimieren, wenn das möglich ist, dürfte das den größten Effekt haben.


Für gezieltes Optimieren der Methode selbst wäre der Wertebereich interessant, und falls der nicht absolut begrenzt ist zumindest eine Verteilung der erwarteten Werte, da die Methoden ihr "Optimum" bei unterschiedlichen Werte-Bereichen haben dürften.
 

tueftli

Mitglied
Also, ich hab die Methoden alle ausgemessen, indem ich sie in mehreren Durchläufen ca. 80 Mrd. mal ausgeführt habe...

Wie bereits vermutet, schenken sich die Varianten in Punkto Perfomance nicht viel: Die Rechendauer schwankt bei ca. 20 Minuten Rechenzeit je nach Variante um +-60 Sekunden.

Nachdem aber anzunehmen ist, dass mein Wertebereich für den Winkel-Eingangswert bei ca. -1000° bis +1000° liegen dürfte, habe ich noch eine 5. Variante programmiert, die mir das im Vergleich zu den bisherigen Varianten in nur 4 Minuten erledigt! Das liegt wahrscheinlich daran, dass sie dann im best case nur zwei Vergleiche, im worst case vier Vergleiche und zwei Additionen bzw. Subtraktionen beinhaltet.
Es ist aber auch klar, dass diese Variante bei Vergrößerung des Wertebereichs von den anderen in punkto Performance überholt wird, da die inneren Schleifen dann umso öfter ausgeführt werden müssen.

[CODE lang="java" title="Variante 5"]public static double normalizeAngle(double angle) {
while(angle >= 360.0) {
angle -= 360.0;
}
while(angle < 0.0) {
angle += 360.0;
}
return angle;
}[/CODE]
 

White_Fox

Top Contributor
Wo bekommst du deine Winkel eigentlich her? Vielleicht wäre es sinnvoll, dort anzusetzen und von vornherein zu unterbinden daß du riesige Wertebereiche erhalten kannst.

Und das Thema Optimierung haben wir hier schon ein paar Male diskutiert. Vielleicht sind da auch einige Anregungen für dich dabei:
 

mrBrown

Super-Moderator
Mitarbeiter
Wie bereits vermutet, schenken sich die Varianten in Punkto Perfomance nicht viel: Die Rechendauer schwankt bei ca. 20 Minuten Rechenzeit je nach Variante um +-60 Sekunden.

Nachdem aber anzunehmen ist, dass mein Wertebereich für den Winkel-Eingangswert bei ca. -1000° bis +1000° liegen dürfte, habe ich noch eine 5. Variante programmiert, die mir das im Vergleich zu den bisherigen Varianten in nur 4 Minuten erledigt!
Bei dem Unterschied würde ich am ehesten Probleme im Benchmark selbst vermuten, nur 20% der Zeit erscheint mir da nach kurzem eigenem Testen etwas zu groß, und alle von dir genannte Varianten dürften auch etwas weiter als nur 5% auseinander liegen.

Hast du mal versucht, das mit JMH umzusetzen?
Ansonsten Teil den Code gerne mal, vielleicht fällt da einem noch was raus und man kann man selber testen :)
 

tueftli

Mitglied
Den Benchmark hab ich jetzt nochmal etwas geändert, damit er nicht so lange laufen muss, aber die Ergebnisse bleiben im Verhältnis die gleichen, auch bei mehreren Durchläufen...
Wenn ich die beiden Grenzbedingungen +1000° und -1000° ansetze, so haben die Varianten 1 bis 4 nun eine durchschnittliche Laufzeit von ca. 2 Minuten, Variante 5 nur etwa 20 Sekunden.

Variante 5 ist unter diesen Bedingungen also etwa 5- bis 6-mal so schnell wie die anderen Varianten, für den allgemeinen Fall stellt sie aber wohl nicht unbedingt die beste Wahl dar.

Hier übrigens die selbsterstellte Benchmark-Methode für einen Testlauf:

[CODE lang="java" title="Benchmark"]private void benchmark(){
long t1 = System.nanoTime() / 1000000;

double r = 0, s = 0;
for(int i = -2_000_000_000; i < 2_000_000_000; i++) {
r = normalizeAngle(-1000.0);
s = normalizeAngle(1000.0);
}
System.out.println(r + " " + s);

long t2 = System.nanoTime() / 1000000;
double dt = (double)(t2 - t1);
System.out.println("Testzeit:\t" + dt + " ms");
}[/CODE]

Bei 4 Mrd. Durchläufen wird die normalizeAngle-Methode je zweimal aufgerufen und kann gegen die anderen Varianten ausgetauscht werden.
Für Verbesserungsvorschläge an der Testumgebung bin ich übrigens jederzeit dankbar...
 

mrBrown

Super-Moderator
Mitarbeiter
Das Problem an solchen Benchmarks ist, dass meist viele ungewollte Optimierungen greifen, die im Normalfall nicht greifen. Bei selbstgeschriebenen Benchmarks ist das ein besonders großes Problem, deshalb für sowas immer JMH nutzen, damit lässt sich ein großer Teil vermeiden.

Erstes Problem an deinem Benchmark dürften die konstanten Werte (-1000, 1000) sein. Das kann sowohl Einfluss auf die Optimierungen der JVM als auch auf Branch-Prediction in der CPU haben
Die JVM kann den Code so optimieren, dass die Pfade für -1000/1000 "zuerst" kommen und/oder besonders optimiert sind, diese sind dann besonders schnell, andere Zahlen wären aber deutlich langsamer. Gleiches auf CPU-Ebene, da die Bedingungen einem festen Muster folgen, kann eine (ausreichend gute) Branch-Prediction das vorhersagen, und liegt damit für jeden bedingten Sprung richtig.
Unter realen Bedingungen würden beide Optimierung aber natürlich nicht möglich sein, da dort ja mehr Zahlen vorkommen. Bei einem Benchmark würden aber Algorithmen profitieren, bei denen beide Optimierungen möglich sind und besonders großen Vorteil bringen.

Außerdem hat dein Benchmark das Problem, dass die Schleife quasi irrelevant ist. Das sieht man, wenn man z.B. folgende normalizeAngle-Implementierung nutzt:
Java:
if (angle >= 360.0) {
    angle = angle - Math.floor(angle / 360.0) * 360.0;
} else if (angle < 0.0) {
    angle = angle + Math.ceil(-angle / 360.0) * 360.0;
}
return angle;

Damit läuft es ziemlich konstant unabhängig von der Anzahl der Schleifendurchläufe, egal ob's 5 oder 5_000_000 sind. (Interessanterweise hat das nur Auswirkungen, wenn man int als Schleifen-Variable nutzt, mit long wird das nicht optimiert.)


Löst man das Problem (indem man die Werte zB summiert, und damit die Schleife nicht ignoriert werden kann), landet man beim nächsten: Bei Varianten ohne innere Schleifen profitiert die große Schleife deutlich besser von CPU-Pipelining und/oder Auto-Vectorization, sodass auch da langsamere Varianten schneller erscheinen könnten.


Da alle Fehlerquellen in so einem künstlichem Benchmark zu vermeiden in diesem Fall relativ schwierig ist, dürfte es am sinnvollsten sein, nicht nur das normalisieren, sondern auch einen Teil des Codes drum herum zu messen. Dadurch verhindert man Optimierungen, die unter realen Bedingungen nicht möglich sind, und erlaubt gleichzeitig Bedingungen, die möglich wären.


Gibts ein kurzes Stück echten Code, den man mal testen könnte? Muss nicht das ganze Programm sein, sondern nur ein Hotspot daraus, dann könnte man das mal sinnvoll testen und nicht nur auf eine so kleinen Ebenen nach Verbesserungen gucken :)




f % g dürfte z.T. deshalb so langsam sein, weil es nicht inlined wird, sondern jedes Mal einen Funktionsaufruf braucht. Hat deshalb im vergleich zu den anderen Varianten immer einen Overhead.
 

Ähnliche Java Themen

Neue Themen


Oben