Robert Sedgewick: Algorithmen

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


7. Implementation von Algorithmen



Empirische Analyse

Wie in Kapitel 6 schon erwähnt wurde, liegt leider allzu oft der Fall vor, daß eine mathematische Analyse sehr wenig Licht in die Frage bringen kann, welche Leistung von einem gegebenen Algorithmus in einer gegebenen Situation erwartet werden kann. In solchen Fällen müssen wir uns auf eine empirische Analyse verlassen, bei der wir einen Algorithmus sorgfältig implementieren und dann seine Leistungsfähigkeit anhand »typischer« Eingabedaten prüfen. Tatsächlich sollte man das sogar dann tun, wenn vollständige mathematische Ergebnisse verfügbar sind, um deren Richtigkeit zu überprüfen.

Wenn zwei Algorithmen zur Lösung des gleichen Problems vorliegen, so ist die Vorgehensweise ganz einfach: Man lasse sie beide ablaufen, um zu sehen, welcher von ihnen mehr Zeit benötigt! Dies mag zu offensichtlich erscheinen, als daß man es erwähnen müßte, doch es ist wahrscheinlich die am weitesten verbreitete Unterlassungssünde bei der vergleichenden Untersuchung von Algorithmen. Die Tatsache, daß ein Algorithmus zehnmal so schnell ist wie ein anderer, dürfte kaum jemandem entgehen, der bei dem einen Algorithmus drei Sekunden und beim anderen dreißig Sekunden lang auf das Ende wartet. Jedoch kann dies sehr leicht übersehen werden, wenn diese Differenz als kleiner konstanter Faktor des Spielraums bei einer mathematischen Analyse auftritt.

Beim Vergleich von Implementationen können jedoch auch leicht Fehler begangen werden, besonders dann, wenn verschiedene Maschinen, Compiler oder Systeme einbezogen werden oder wenn sehr umfangreiche Programme mit ungünstig gewählten Eingabedaten verglichen werden. Tatsächlich bestand ein zur Entwicklung der mathematischen Analyse von Algorithmen führender Faktor, in der Tendenz, sich auf Benchmarks zu verlassen, deren Leistungsfähigkeit vielleicht durch sorgfältige Analyse besser verstanden werden kann.

Die prinzipielle Gefahr beim empirischen Vergleich von Programmen besteht darin, daß eine Implementation besser »optimiert« sein kann als eine andere. Der Erfinder eines neu entwickelten Algorithmus wird sicher jedem Aspekt seiner Implementation viel Aufmerksamkeit widmen, nicht aber den Einzelheiten der Implementation eines vergleichbaren klassischen Algorithmus. Um sich auf die Korrektheit einer empirischen Untersuchung zum Vergleich von Algorithmen verlassen zu können, muß man sicher sein, daß den Implementationen die gleiche Aufmerksamkeit geschenkt wurde. Zum Glück ist das oft der Fall: Viele ausgezeichnete Algorithmen werden aus relativ geringfügigen Modifikationen anderer Algorithmen für das gleiche Problem entwickelt, und vergleichende Untersuchungen haben tatsächlich Gültigkeit.

Ein wichtiger Spezialfall liegt vor, wenn ein Algorithmus mit einer anderen Variante von sich selbst verglichen werden soll oder wenn verschiedene Varianten seiner Implementation zu vergleichen sind. Ein ausgezeichneter Weg, die Effizienz einer speziellen Idee betreffs einer Modifikation oder Implementation zu überprüfen, besteht darin, beide Varianten mit gewissen »typischen« Eingabedaten abzuarbeiten und dann der schnelleren den Vorzug zu geben. Auch dies scheint fast zu offensichtlich zu sein, als daß man es erwähnen müßte, doch eine erstaunliche Anzahl von Fachleuten, die sich mit der Entwicklung von Algorithmen beschäftigen, implementieren die von ihnen entwickelten Algorithmen niemals, so daß der Anwender vorsichtig sein sollte!

Wie oben und zu Beginn von Kapitel 6 dargelegt wurde, stellen wir uns hier auf den Standpunkt, daß Entwicklung, Implementation, mathematische Analyse und empirische Analyse Elemente sind, die alle einen wesentlichen Beitrag zur Schaffung von guten Implementationen guter Algorithmen leisten können. Wir möchten alle verfügbaren Mittel nutzen, um Informationen über die Eigenschaften unserer Programme zu erhalten, und auf der Basis dieser Informationen dann die Programme modifizieren oder neue entwickeln. Andererseits ist es nicht immer gerechtfertigt, in der Hoffnung auf geringfügige Verbesserungen der Leistungsfähigkeit eine große Zahl kleiner Veränderungen vorzunehmen. Nachfolgend erörtern wir diese Frage ausführlicher.


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