Robert Sedgewick: Algorithmen

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


7. Implementation von Algorithmen



Algorithmen und Systeme

Implementationen der Algorithmen in diesem Buch findet man in einer großen Menge von umfangreichen Programmen, Betriebs- und Anwendungssystemen. Unsere Absicht ist, die Algorithmen zu beschreiben und den Leser zu ermutigen, durch Experimente mit den angegebenen Implementationen insbesondere ihre dynamischen Eigenschaften zu untersuchen. Für manche Anwendungen mögen die Implementationen genau in der angegebenen Form recht nützlich sein, für andere Anwendungen jedoch kann mehr Arbeit erforderlich sein.

Wie in Kapitel 2 erwähnt wurde, verwenden die Programme in diesem Buch nur elementare Eigenschaften von Pascal und nutzen nicht die erweiterten Möglichkeiten aus, die in Pascal und anderen Programmierumgebungen zur Verfügung stehen. Unser Ziel ist es, Algorithmen zu untersuchen, nicht Systemprogrammierung oder fortgeschrittene Elemente von Programmiersprachen. Wir hoffen, daß die wesentlichen Merkmale der Algorithmen am besten durch einfache, direkte Implementationen in einer nahezu universellen Sprache dargelegt werden können.

Der von uns verwendete Programmierstil ist recht knapp, mit kurzen Variablennamen und wenig Kommentaren, so daß die Steuerstrukturen sichtbar werden. Die »Dokumentation« der Algorithmen ist der Begleittext. Es wird erwartet, daß Leser, die diese Programme für reale Anwendungen nutzen, sie etwas ergänzen, indem sie sie für einen speziellen Verwendungszweck anpassen. Ein »defensiverer« Programmierstil ist beim Aufbau von realen Systemen gerechtfertigt: Die Programme müssen so implementiert werden, daß sie leicht verändert, schnell gelesen und von anderen Programmierern verstanden werden können und daß sie sich gut an andere Teile des Systems anpassen lassen.

Insbesondere enthalten die Datenstrukturen, die normalerweise für Anwendungen benötigt werden, viel mehr Informationen als die, die in diesem Buch verwendet werden, obwohl die von uns betrachteten Algorithmen für komplexere Datenstrukturen durchaus geeignet sind. Zum Beispiel sprechen wir vom Durchsuchen von Dateien, die ganze Zahlen oder kurze Zeichenfolgen enthalten, während es für typische Anwendungen erforderlich wäre, lange Zeichenfolgen zu betrachten, die Bestandteil langer Datensätze sind. Doch die verfügbaren grundlegenden Methoden sind in beiden Fällen die gleichen. In solchen Fällen werden wir herausragende Merkmale jedes Algorithmus erörtern und die Frage betrachten, wie sie an verschiedene Anforderungen der Anwendung angepaßt werden können.

Viele der obigen Bemerkungen, die die Verbesserung der Leistungsfähigkeit eines speziellen Algorithmus betrafen, gelten ebenso für die Verbesserung der Effizienz in einem großen System. Auf dieser höheren Ebene könnte jedoch eine Methode der Verbesserung der Leistungsfähigkeit des Systems darin bestehen, einen Baustein, in dem ein Algorithmus implementiert wird, durch einen Baustein zu ersetzen, in dem ein anderer implementiert wird. Ein grundlegendes Prinzip beim Aufbau großer Systeme ist, daß solche Auswechslungen möglich sein sollten. Typisch ist, daß in dem Maße, wie ein System Gestalt annimmt, genauere Kenntnisse über die spezifischen Anforderungen an spezielle Bausteine gewonnen werden. Diese spezifischeren Kenntnisse geben die Möglichkeit, den besten zur Erfüllung dieser Anforderungen anzuwendenden Algorithmus sorgfältiger auszuwählen; danach kann man sich in der oben beschriebenen Weise auf die Verbesserung der Leistungsfähigkeit dieses Algorithmus konzentrieren. Sicherlich trifft es zu, daß die große Mehrheit von Systemcode nur wenige Male (oder überhaupt nicht) ausgeführt wird; das vorrangige Bestreben des Systementwicklers ist es, ein einheitliches Ganzes zu schaffen. Andererseits ist es ebenfalls sehr wahrscheinlich, daß, wenn ein System in Gebrauch kommt, viele seiner Ressourcen für die Lösung fundamentaler Probleme von der Art, wie sie im vorliegenden Buch behandelt werden, aufgewandt werden. Daher ist es für den Systementwickler von Vorteil, wenn er mit den grundlegenden Algorithmen, die wir hier behandeln, vertraut ist.


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