Wirkungsgrad/Geschwindigkeit für trigonometrische Funktionen

Question

In einem Spiel, das ich entwickle, habe ich zwei Punkte, pt1 und pt2, und ich möchte den Winkel zwischen ihnen berechnen. Die Entfernung habe ich bereits in einer früheren Berechnung ermittelt. Der offensichtliche Weg wäre, den horizontalen Abstand über den vertikalen Abstand zu arctanisieren (tan(theta) = opp/adj).

Ich frage mich jedoch, da ich die Entfernung bereits berechnet habe, ob es schneller wäre, Arkussinus/Arkosinus mit der Entfernung und dx oder dy zu verwenden?

Wäre es nicht auch besser, wenn ich in einer Tabelle vorberechne?

Answer 1

Machen Sie es zuerst richtig! Und dann profilieren und optimieren. Die Tabellensuche ist sicher ein guter Kandidat, aber stellen Sie sicher, dass Ihre Berechnung richtig ist, bevor Sie etwas Ausgefallenes tun

Answer 2

1. Wenn Sie an der Big-O-Notation interessiert sind, sind alle Methoden, die Sie verwenden könnten, O(1).

2. Wenn Sie wissen wollen, was am schnellsten funktioniert, testen Sie es. Schreiben Sie eine Wrapper-Funktion, die Ihre bevorzugte Methode aufruft, aber leicht geändert werden kann, und testen Sie mit dieser. Vergewissern Sie sich, dass Ihre Anwendung dabei einen nennenswerten Teil der Zeit verbringt, damit Sie nicht Ihre eigene Zeit verschwenden. Probieren Sie alle Möglichkeiten aus, die Ihnen einfallen. Idealerweise sollten Sie die Anwendung auf mehr als einer CPU laufen lassen.

Ich bin sehr misstrauisch geworden, wenn es darum geht, vorherzusagen, was auf modernen Prozessoren mehr oder weniger Zeit in Anspruch nehmen wird. Nachschlagetabellen waren früher die Antwort, wenn es um Geschwindigkeit ging, aber man weiß nicht von vornherein, wie sich das Caching auswirkt oder wie lange das Normalisieren und Nachschlagen im Vergleich zur Ausführung einer trigonometrischen Funktion auf einer bestimmten CPU dauern wird.

Answer 3

Da es sich um ein Spiel handelt, ist Ihnen wahrscheinlich die Geschwindigkeit wichtig. Eine Nachschlagetabelle ist definitiv am schnellsten, aber bei dieser Methode muss man Genauigkeit gegen Geschwindigkeit eintauschen. Wie genau müssen Sie also sein, um die Anforderungen zu erfüllen? Das können nur Sie selbst beantworten. Bevor Sie Genauigkeit eintauschen, sollten Sie zunächst feststellen, ob Sie ein Geschwindigkeitsproblem haben. Alle trigonometrischen Funktionen werden mit numerischen Methoden berechnet (informieren Sie sich über numerische Analyse, um mehr zu erfahren). Einige trigonometrische Funktionen sind teurer als andere, weil sie auf Reihen beruhen, die langsamer konvergieren, und wer weiß, vielleicht hat Ihr Computer andere Implementierungen für diese Funktionen als ein anderer. Auf jeden Fall kannst du selbst herausfinden, wie teuer diese Funktionen sind, indem du einige kleine Programme schreibst, die in einer Schleife so viele Iterationen durchlaufen, wie du möchtest, mit Inkrementen deiner Wahl, und dabei die Ergebnisse messen. Dann können Sie die schnellste Methode wählen.

Answer 4

Andere haben zwar Recht, wenn sie darauf hinweisen, dass Sie mit ziemlicher Sicherheit in die Falle der verfrühten Optimierung tappen, aber wenn sie sagen, dass trigonometrische Funktionen O(1) sind, sagen sie nicht die ganze Wahrheit.

Die meisten Implementierungen trigonometrischer Funktionen sind tatsächlich O(N) für den Wert der Eingabefunktion. Das liegt daran, dass die trigonometrischen Funktionen am effizientesten auf einem kleinen Intervall wie [0, 2] berechnet werden (oder, bei den besten Implementierungen, auf noch kleineren Teilen dieses Intervalls, aber das reicht zur Erklärung aus). In Pseudo-Python sieht der Algorithmus also etwa so aus:

def Cosine_0to2Pi(x):
    #a series approximation of some kind, or CORDIC, or perhaps a table
    #this function requires 0 <= x < 2Pi

def MyCosine(x):
    if x < 0:
         x = -x
    while x >= TwoPi:
         x -= TwoPi
    return Cosine_0to2Pi(x)

Selbst mikrokodierte CPU-Befehle wie die des x87 FSINCOS am Ende so etwas intern machen. Da trig-Funktionen periodisch sind, benötigen sie in der Regel O(N) Zeit für die Argumentreduktion. Es gibt jedoch zwei Vorbehalte:

1. Wenn Sie eine Vielzahl von Werten aus dem Hauptbereich der trigonometrischen Funktionen berechnen müssen, ist Ihre Mathematik wahrscheinlich nicht sehr gut durchdacht.
2. Die Big-O-Schreibweise verbirgt einen konstanten Faktor. Die Argumentreduktion hat einen sehr kleinen konstanten Faktor, weil sie einfach zu bewerkstelligen ist. Daher wird der O(1)-Teil den O(N)-Teil für so gut wie jede Eingabe dominieren.