Robert Sedgewick: Algorithmen

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


7. Implementation von Algorithmen



Auswahl eines Algorithmus

Wie wir in den folgenden Kapiteln sehen werden, steht für die Lösung jedes Problems gewöhnlich eine Reihe von Algorithmen zur Verfügung, die alle unterschiedliche Leistungsmerkmale aufweisen, von einer einfachen, »gewaltsamen« (aber wahrscheinlich ineffizienten) Lösung bis zu einer komplexen »gut angepaßten« (und vielleicht sogar optimalen) Lösung. (Es trifft nicht generell zu, daß die Implementation eines Algorithmus um so komplizierter sein muß, je effizienter er ist. Einige unserer besten Algorithmen sind sehr elegant und kurz; für die Zwecke der vorliegenden Betrachtungen wollen wir jedoch annehmen, daß diese Regel gilt.) Wie bereits erwähnt wurde, kann man nicht entscheiden, welcher Algorithmus für ein Problem zu verwenden ist, ohne die Besonderheiten des Problems zu analysieren. Wie oft muß das Programm abgearbeitet werden? Welches sind die allgemeinen Merkmale des Computersystems, das verwendet werden soll? Ist der Algorithmus ein kleiner Teil einer umfangreichen Anwendung, oder verhält es sich umgekehrt?

Die erste Regel für die Implementation besagt, daß man zuerst den einfachsten Algorithmus zur Lösung eines gegebenen Problems implementieren sollte. Falls der vorliegende spezielle Fall des Problems sich als leicht erweist, kann der einfache Algorithmus das Problem lösen, und es bleibt nichts zu tun übrig; falls ein komplizierterer Algorithmus benötigt wird, so bietet die einfache Implementation die Möglichkeit einer Überprüfung der Korrektheit für kleine Fälle und einen Ausgangspunkt für die Einschätzung der Leistungsmerkmale.

Wenn ein Algorithmus nur einige wenige Male für nicht zu umfangreiche Fälle abgearbeitet werden muß, so ist es sicher vorzuziehen, wenn der Computer etwas zusätzliche Zeit für die Abarbeitung eines etwas weniger effizienten Algorithmus aufwendet als wenn der Programmierer einen erheblichen zusätzlichen Zeitaufwand hat, um eine komplizierte Implementation zu erstellen. Natürlich besteht die Gefahr, daß man am Ende das Programm öfter einsetzen muß als ursprünglich beabsichtigt war, so daß man stets darauf vorbereitet sein sollte, neu zu beginnen und einen besseren Algorithmus zu implementieren.

Falls der Algorithmus als Teil eines umfangreichen Systems implementiert werden soll, gewährleistet die »gewaltsame« Implementation auf zuverlässige Weise die geforderte Funktionalität, und später kann die Leistungsfähigkeit durch Einsetzen eines besseren Algorithmus gezielt verbessert werden. Natürlich sollte man darauf achten, daß man nicht im voraus seine Auswahlmöglichkeiten einschränkt, indem man den Algorithmus so implementiert, daß seine Verbesserung später kompliziert ist. Weiterhin sollte man sorgfältig darauf achten, welche Algorithmen »Engpässe« für die Leistung erzeugen, wenn man die Leistungsfähigkeit des Systems als Ganzes untersucht. Auch liegt in großen Systemen oft der Fall vor, daß die Anforderungen, die sich aus der Entwicklung des Systems ergeben, von Anfang an diktieren, welcher Algorithmus der beste ist. Zum Beispiel tritt vielleicht als systemweite Datenstruktur eine spezielle Form einer verketteten Liste oder eines Baumes auf, so daß jene Algorithmen vorzuziehen sind, die auf dieser speziellen Struktur beruhen. Andererseits sollte man, wenn man solche das ganze System betreffende Entscheidungen trifft, den anzuwendenden Algorithmen viel Aufmerksamkeit schenken, denn oft erweist es sich am Ende, daß die Leistungsfähigkeit des Gesamtsystems von der eines gewissen grundlegenden Algorithmus von der Art, wie wir sie in diesem Buch betrachten, abhängt.

Wenn der Algorithmus nur einige Male, jedoch für sehr umfangreiche Probleme, abgearbeitet werden soll, ist es wünschenswert darauf vertrauen zu können, daß er sinnvolle Ausgabedaten erzeugt, und eine gewisse Schätzung der Laufzeit zu haben. Auch hier kann eine einfache Implementation oft von großem Nutzen sein, um eine lange Abarbeitung vorzubereiten, einschließlich der Entwicklung von Instrumenten zur Überprüfung der Ausgabedaten.

Der am weitesten verbreitete Fehler, der bei der Auswahl eines Algorithmus begangen wird, besteht in der Mißachtung der Leistungsmerkmale. Schnellere Algorithmen sind oft komplizierter, und Programmierer, die eine Implementation erstellen, sind oft bereit, einen langsameren Algorithmus zu akzeptieren, um zusätzliche Komplexität zu vermeiden. Doch ein schnellerer Algorithmus ist oft nicht wesentlich komplizierter, und eine leicht erhöhte Komplexität ist ein geringer Preis, wenn man damit den Einsatz eines langsamen Algorithmus vermeiden kann. Überraschend viele Anwender von Computersystemen verlieren kostbare Zeit, indem sie warten, bis ein einfacher quadratischer Algorithmus beendet ist, während Algorithmen vom Typ N log N zur Verfügung stehen, die nur unwesentlich komplizierter sind und einen Bruchteil der Zeit benötigen würden.

Der zweithäufigste Fehler, der bei der Wahl eines Algorithmus begangen wird, besteht darin, daß den Leistungsmerkmalen zu viel Aufmerksamkeit geschenkt wird. So kann der Fall eintreten, daß ein einfacher Algorithmus vom Typ N log N nur wenig komplizierter ist als ein quadratischer Algorithmus für das gleiche Problem, daß jedoch ein besserer Algorithmus vom Typ N log N mit einer erheblichen Erhöhung der Komplexität verbunden ist (und in Wirklichkeit vielleicht nur für sehr große Werte von N schneller ist). Weiterhin werden viele Programme tatsächlich nur wenige Male abgearbeitet; der Zeitaufwand, der erforderlich ist, um einen optimierten Algorithmus zu implementieren und zu debuggen, kann weit größer sein als der Zeitverlust, der entsteht, wenn man einfach einen etwas langsameren Algorithmus anwendet.


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