Sortieren in BASIC
Teil 2

von Wolfgang Mayer-Gürr

Wenn man zeitaufwendige Routinen beschleunigen will, sollte man 2 Möglichkeiten untersuchen.

1. Muß der Rechner überflüssige Arbeit verrichten?
2. Gibt es einen effektiveren Algorithmus für das Problem?

Ein Basic-Interpreter arbeitet ein Programm zeilenweise ab. Dabei wird bei jeder Zeile ein Kontrollmechanismus durchlaufen, der die Zeile auf mögliche Fehler (Syntax, Overflow usw.) untersuchen muß. Außerdem erfordern die einzelnen Operationen natürlich einen unterschiedlich hohen Zeitaufwand. Bei dem „Hauruck“ Sortierverfahren aus dem letzten Journal stellt man fest, daß 3 Arten von Operationen häufig benutzt werden:

1. Zuweisungen (z.B. H$=N$(I)
2. FOR NEXT Schleifen
3. Vergleiche (IF N$(I)<H$ THEN)

Messen und vergleichen Sie einmal die Rechenzeit für folgende Programme !

Merke: Wie mache ich mein Programm schnell, aber unübersichtlich?

Wenn mit Konstanten gerechnet werden soll, empfiehlt es sich, diese immer einer Variablen am Programmanfang zuzuweisen. Das erleichtert auch spätere Änderungen. Es muß nur einmal die Umwandlung stattfinden, ein späterer Zugriff auf diese Variable beeinflußt intern nur 2 Byte statt der 8 Byte des Fließkomma-Akkus, (siehe Beispiel 2 und 3) .
REMs erhöhen zwar die Lesbarkeit eines Programms, kosten aber Laufzeit. Ein Tip: bei der Programmentwicklung ruhig viele REM-Zeilen einbauen. Diese sollten aber nie direkt aufgerufen werden. (z.B. 100 GOTO 200; 200 REM; 210 A=B). Wenn das Programm ausgetestet ist, kann bei einer 2.Version eine Laufzeitoptimierung vorgenommen werden.
Die Variable nach NEXT weglassen (auch hier mit dem Mangel an Übersichtlichkeit erkauft).
Möglichst viele Befehle in eine Zeile packen.

Wenn dies alles noch nicht genug ist, sollte man den Algorithmus überdenken, also die Zahl der Vergleichsoperationen minimieren. Beim Haurucksortieren ist der Programmablauf starr, also unabhängig vom Aufbau des Feldes. Eine Verbesserung bringt das Sortieren durch Einfügen.

Hier wird nicht jedesmal das Minimum gesucht, sondern die kleinere „Karte“ wird sofort zurückgesteckt. Fügt man als Zeile 315 ein Unterprogramm ein, das den Inhalt der einzelnen Variablen ausdruckt, erhält man für die einzelnen Durchläufe bei der Eingabe von SPIEL (N=5) folgende Werte: