If-Statement beschleunigen 1

01.11.2009

00:28

If-Statement beschleunigen 1

Während der Entwicklung eines Codes entstehen gerne angsteinflößend große If-Bedigungen. In der Entstehungsphase ist das OK. Zum Abschluss eines Projektes sollte man sich dieser Codeteile jedoch noch einmal annehmen, da hier sehr oft die Ausführungsgeschwindigkeit wesentlich erhöht werden kann.

Die ganze Thematik fällt in den Bereich der Bool’schen Algebra. de.wikipedia.org/wiki/Boolesche_Algebra

Ich portiere derzeit ein Spriteframework von AS2 nach AS3. Hier bin ich auf eine Funktion gestoßen, die prüft, ob ein Punkt ein Sprite berührt. An diesem Beispiel möchte ich vorführen, wie eine solche Optimierung durchgeführt werden kann.

Diese Version habe ich vorgefunden:

protected function pointInSprite2(sprite:AdvancedSprite, x:int, y:int):Boolean {
if (
x >= sprite.x && x <= sprite.x + sprite.width
&&
y >= sprite.y && y <= sprite.y + sprite.height
)
return true;
else
return false;
}

Logisch arbeitet diese Funktion korrekt, jedoch kann das gleiche Ergebnis mit weniger Aufwand erzielt werden. In der If-Bedingung finden wir vier Teilbedingungen. NUR wenn alle vier Teilbedingungen erfüllt sind ist die gesamte Bedingung erfüllt. Diese Codestruktur führt dazu, dass bei jedem Aufruf immer alle vier Teilbedingungen ausgewertet werden müssen, was Rechenzeit in Anspruch nimmt.

Wie sieht die Optimierung aus?

Im Grunde drehen wir die Prüfung um(Negation). Sobald eine Teilbedingung nicht erfüllt ist, können wir auf weitere Prüfungen verzichten, da durch eine UND-Verknüpfung das Gesamtergebnis gar nicht mehr Wahr sein kann.

Die Optimierung erfolgt in zwei Schritten:

1. Negation

protected function pointInSprite2(sprite:AdvancedSprite, x:int, y:int):Boolean {
if (
x < sprite.x || x > sprite.x + sprite.width
||
y < sprite.y || y > sprite.y + sprite.height
)
return false;
else
return true;
}

2. Auflösung der ODER-Verknüpfung

Durch die Auflösung der ODER-Verknüpfung werden Codeteile dupliziert(hier: "return false;"). Hier muss man von Fall zu Fall entscheiden, ob die Codevergrößerung durch die gewonnene Geschwindigkeit gerechtfertigt ist. In diesem Beispiel kommt erst durch diese Auflösung der Geschwindigkeitsgewinn zu Stande!

protected function pointInSprite2(sprite:AdvancedSprite, x:int, y:int):Boolean {
if ( x < sprite.x )
return false;
if ( y < sprite.y ) // Diese Prüfung wurde vorverlegt. Somit bleibt manche Addition erspart.
return false;
if ( x > sprite.x + sprite.width )
return false;
if ( y > sprite.y + sprite.height )
return false;
return true;
}

Die logischen Ergebnisse der beiden Versionen sind ident. Bei der optimierten Version, wird die durchschnittliche Ausführungsdauer jedoch geringer sein. Sollte sich der Punkt genau unter dem Sprite befinden, werden wieder alle vier Bedingungen geprüft, d. h.: In diesem einen Fall werden wir kaum Zeit gut machen können, in allen anderen jedoch schon. Wenn man es ganz genau nimmt, haben wir auch in der einen Situation Zeit gewonnen, da die UND-Verknüpfung der Teilbedingungen entfällt. Diese Ersparnis kann jedoch vernachlässigt werden.

In diesem Beispiel sind die optimierte und die nicht optimierte Version in etwa gleich lang. Es kann durchaus passieren das der optimierte Quellcode länger wird. Schließlich optimieren wir auf geringe Ausführungsgeschwindigkeit und nicht auf geringe Codegröße.

PermalinkTrackback link