Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


7. Implementation von Algorithmen



Programmoptimierung

Der allgemeine Prozeß der Realisierung sukzessiver Veränderungen in einem Programm mit dem Ziel, eine andere Variante herzustellen, die schneller abläuft, wird Programmoptimierung genannt. Diese Bezeichnung ist unpassend, denn wir können wahrscheinlich keine »optimale« Implementation finden; wir können ein Programm nicht optimieren, aber wir können hoffen, es zu verbessern. Normalerweise bezeichnet Programmoptimierung die automatischen Techniken, die als Teil des Compilierungsprozesses zur Verbesserung der Leistungsfähigkeit des compilierten Programms angewandt werden. Hier benutzen wir diesen Begriff, um algorithmenspezifische Verbesserungen zu bezeichnen. Natürlich hängt dieser Prozeß auch stark von der verwendeten Programmierumgebung und -hardware ab, so daß wir hier nur allgemeine Fragen, doch keine speziellen Techniken betrachten.

Diese Arbeit ist nur dann gerechtfertigt, wenn man sicher ist, daß das Programm viele Male oder für umfangreiche Eingabedaten eingesetzt wird, und wenn Versuche zeigen, daß die für die Verbesserung der Implementation aufgewandte Mühe durch eine verbesserte Leistungsfähigkeit belohnt wird. Die beste Methode, um die Leistungsfähigkeit eines Algorithmus zu verbessern, besteht in einem stufenweisen Prozeß der Umwandlung des Programms in immer bessere Implementationen. Das Beispiel zur Beseitigung der Rekursion in Kapitel 5 ist ein Beispiel für einen solchen Prozeß, obwohl in diesem Fall unser Ziel nicht in der Verbesserung der Leistungsfähigkeit bestand.

Der erste Schritt beim Implementieren eines Algorithmus besteht in der Entwicklung einer lauffähigen Variante des Algorithmus in seiner einfachsten Form. Dies liefert einen Ausgangspunkt für Verfeinerungen und Verbesserungen und ist, wie oben erwähnt, sehr oft alles, was benötigt wird. Alle verfügbaren mathematischen Ergebnisse sollten mit der Implementation verglichen werden: Wenn zum Beispiel die Analyse zu besagen scheint, daß die Laufzeit O (log N) ist, aber die tatsächliche Laufzeit in die Sekunden geht, so ist entweder mit der Implementation oder mit der Analyse etwas nicht in Ordnung, und beide sollten etwas sorgfältiger untersucht werden.

Der nächste Schritt besteht darin, die »innere Schleife« zu identifizieren und zu versuchen, die Anzahl der in ihr enthaltenen Befehle zu minimieren. Der wahrscheinlich einfachste Weg, die innere Schleife zu finden, besteht darin, das Programm abzuarbeiten und dann zu prüfen, welche Befehle am häufigsten ausgeführt werden. Normalerweise erhält man dadurch sehr gute Anhaltspunkte, wo das Programm verbessert werden sollte. Jeder Befehl in der inneren Schleife sollte gründlich geprüft werden. Ist der Befehl wirklich notwendig? Gibt es einen effizienteren Weg, um die gleiche Aufgabe zu erfüllen? Zum Beispiel lohnt es sich gewöhnlich, Prozeduraufrufe aus der inneren Schleife zu entfernen. Es gibt eine Reihe weiterer »automatischer« Techniken, um das zu tun, von denen viele in Standardcompilern implementiert sind. Letztlich wird die beste Leistungsfähigkeit erzielt, indem die innere Schleife in Maschinen- oder Assemblersprache übertragen wird, doch das ist gewöhnlich der letzte Ausweg.

Nicht alle »Verbesserungen« führen wirklich zu Erhöhungen der Leistungsfähigkeit; daher ist es äußerst wichtig, die Größe der Einsparungen zu überprüfen, die mit jedem Schritt erzielt werden. Darüber hinaus ist es in dem Maße, wie die Implementation immer mehr verfeinert wird, ratsam, erneut zu prüfen, ob es sich lohnt, den Einzelheiten des Programms so viel Aufmerksamkeit zu widmen. In der Vergangenheit war Rechenzeit so teuer, daß es fast immer gerechtfertigt war, Programmiererzeit aufzuwenden, um Berechnungszyklen einzusparen, doch in den letzten Jahren hat sich die Lage geändert.

Betrachten wir zum Beispiel den Algorithmus für die Preorder-Traversierung eines Baumes, der in Kapitel 5 behandelt wurde. Die Beseitigung der Rekursion ist praktisch der erste Schritt der »Optimierung« dieses Algorithmus, denn sie konzentriert sich auf die innere Schleife. Die angegebene nichtrekursive Variante ist in Wirklichkeit wahrscheinlich auf vielen Systemen langsamer als die rekursive Variante (der Leser kann es nachprüfen), da die innere Schleife länger ist und anstelle von zwei Prozeduraufrufen vier (wenn auch nichtrekursive) Prozeduraufrufe enthält (pop, push, push und stackempty). Wenn die Aufrufe der Stapel-Prozeduren durch Code für einen direkten Zugriff auf den Stapel ersetzt werden (etwa unter Verwendung einer Feld-Implementation), ist dieses Programm sicher wesentlich schneller als die rekursive Variante. (Eine der Operationen push stammt vom Algorithmus, so daß das Standardprogramm mit verschachtelten Schleifen wahrscheinlich die Ausgangsbasis für eine optimierte Variante sein sollte.) Damit ist klar, daß die innere Schleife das Inkrementieren des Stapel-Zeigers, das Speichern eines Zeigers (t^.r) im Stapel-Feld, das Zurücksetzen des t-Zeigers (auf t^.l) und seinen Vergleich mit z beinhaltet. Auf vielen Maschinen könnte das mit vier Maschinensprache-Befehlen implementiert werden, obwohl ein typischer Compiler doppelt so viele Befehle oder mehr erzeugt. Dieses Programm kann man ohne viel zusätzliche Arbeit vielleicht vier- oder fünfmal schneller ablaufen lassen als die einfache rekursive Implementation.

Offenbar sind die hier betrachteten Fragen sehr stark system- und maschinenabhängig. Man kann keinen ernsthaften Versuch unternehmen, ein Programm zu beschleunigen, ohne das Betriebssystem und die Programmierumgebung sehr gründlich zu kennen. Die optimierte Variante eines Programms kann sehr instabil und schwer zu verändern werden, und ein neuer Compiler oder ein neues Betriebssystem (ganz zu schweigen von einem neuen Computer) kann eine sorgfältig optimierte Implementation vollständig ruinieren. Andererseits konzentrieren wir uns auf die Effizienz unserer Implementationen, indem wir der inneren Schleife einen hohen Grad an Aufmerksamkeit widmen, und indem wir gewährleisten, daß überflüssige Elemente aus dem Algorithmus minimiert werden. Die Programme in diesem Buch sind kompakt formuliert, und für jede spezielle Programmierumgebung lassen sich weitere Verbesserungen auf einfache Weise erzielen.

Die Implementation eines Algorithmus ist ein zyklischer Prozeß, der in der Erstellung eines Programms, in dessen Debuggen und im Studium seiner Eigenschaften sowie in der nachfolgenden Verfeinerung der Implementation besteht, so lange, bis eine Leistungsfähigkeit erreicht ist. Wie in Kapitel 6 erörtert wurde, kann eine mathematische Analyse in diesem Prozeß gewöhnlich hilfreich sein: Erstens, um zu ermitteln, welche Algorithmen aussichtsreiche Kandidaten für eine gute Leistungsfähigkeit als Ergebnis einer sorgfältigen Implementation sind; zweitens, um bei der Überprüfung zu helfen, ob die Implementation die erwartete Leistung erbringt. In manchen Fällen kann dieser Prozeß zur Entdeckung von das Problem betreffenden Tatsachen führen, aus denen sich Anregungen für einen neuen Algorithmus oder für wesentliche Verbesserungen in einem alten ergeben.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]