Der Taschenrechner unserer Schule – TI-82 STATS – ist programmierbar. Spiele wie Snake, Schiffe versenken, Memory oder Flappy Bird liefen alle bereits auf meinem GTR. Ein Problem: das Gerät ist langsam, denn der Prozessor kam schon vor knapp 50 Jahren auf den Markt. Um Spiele und Programme trotzdem schnell zu halten, müssen wir TI-82 STATS Softwareentwickler also tief in die Trickkiste greifen.

Genau das war Thema meiner Seminarfacharbeit: Software-Geschwindigkeitsoptimierung am Beispiel TI-82 STATS. Dort habe ich 12 verschiedene Optimierungsansätze getestet, von denen ich gleich zwei erkläre. Es wird etwas technisch!

1, 2, 3, 4, 5, 6: Zählen muss gelernt sein

In Programmen braucht man manchmal eine Liste von aufsteigenden Zahlen: [1, 2, 3, 4, 5, 6…]. Das lässt sich im Taschenrechner ganz einfach mit folgenden Anweisungen umsetzen:

• Erstelle eine leere Liste mit 6 Einträgen
• Für jede Zahl von 1 bis 6:
  • Füge die Zahl an die richtige Stelle der Liste ein

Folgende Anweisungen werden dann ausgeführt (L1 ist die Liste, dim(L1) ist die Länge der Liste):

Können wir die Anzahl von Anweisungen verkleinern? Der Taschenrechner hat eine vielversprechende Funktion „cumSum“, welche alle Einträge einer Liste schrittweise addiert und alle Zwischenergebnisse in einer neuen Liste speichert. (cumSum = cumulative Sum). Beispiel: cumSum({1, 2, 3, 0, -1}) = {1, 3, 6, 6, 5}. Versuchen wir also folgendes:

• Erstelle eine leere Liste mit 6 Einträgen
• Fülle die Liste mit Einsen
• cumSum

Und tatsächlich: diese Änderung brachte die Laufzeit meines Testprogramms von 49 Sekunden auf 47 Sekunden, eine Verbesserung von 4%! Es ist nicht viel, aber wer den Pfennig nicht ehrt, ist des Talers nicht wert.

Nullen herausfiltern, in einfach und kompliziert

Eine weitere Aufgabe, die mein Testprogramm bewältigen musste, ist, die Nullen aus einer Liste von Zahlen zu entfernen. Aus {2, 3, 0, 5, 0, 7} wird {2, 3, 5, 7}. Auch hier gibt es einen einfachen Ansatz:

• Betrachte nacheinander jede Zahl in der Liste:
  • Wenn es 0 ist, überspringe
  • Ansonsten, schreibe die Zahl in die fertige Liste

Problem: jeder Listeneintrag muss wieder einzeln überprüft werden. Gibt es vielleicht einen weiteren praktischen Taschenrechner-Befehl, der uns helfen kann? Ja, nämlich der Sortierungsbefehl!

Neuer Ansatz:

• Zahlen sortieren: alle Nullen rutschen an den Anfang
• Anzahl Nullen zählen
• Die gezählten Einträge von der Liste abschneiden

Der neue Ansatz benötigt nur drei Befehle und ist theoretisch schneller. Doch entspricht die Praxis unserer Theorie?

Leider nicht, denn die Laufzeit des Testprogramms stieg von 42 Sekunden auf 46 Sekunden (etwa +10%). Vermutlich ist unsere Verwendung vom Sortierungsbefehl Overkill: schließlich müssen wir unsere Zahlen eigentlich gar nicht extra sortieren. Deshalb ist der manuelle Ansatz – trotz mehr Befehle – in diesem Fall schneller, weil weniger unnötige Arbeit verrichtet wird.

Moral von der Geschicht

Mal gewinnt man, mal verliert man. Wichtig ist auf jeden Fall, Optimierungsansätze tatsächlich zu messen, weil sich schlecht voraussagen lässt, ob die Änderung guten oder schlechten Einfluss hat.