Algorithmen und Datenstrukturen in C: Vorwort
Im Allgemeinen versteht man unter Algorithmus eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen, die sich in endlich vielen Schritten durchführen lässt. Algorithmen bilden somit das zentrale Wissen der Informatik.
Von besonderer Bedeutung ist dabei die Effizienz eines Algorithmus. Dabei gibt es natürlich unterschiedliche Betrachtungsweisen. Auf der einen Seite steht das Zeitverhalten. Exemplarisch kann man das gut bei den Sortieralgorithmen nachvollziehen. Auf der anderen Seite gibt es aber auch die Speichereffizienz und auch die Programmiereffizienz, die man nicht vernachlässigen darf. Dazu kommen heute Fragen, ob sich ein Algorithmus auf mehrere Prozesse verteilen lässt.
Effiziente Algorithmen sind die Basis für performante Programme. Jeder Programmierer sollte ein tiefer gehendes Verständnis von Algorithmen besitzen, da vielfach Lösungen wunderbar mit kleinen Datenmengen funktionieren. Wenn die Datenmengen dann steigen, werden diese Lösungen immer langsamer, bis sie dann unbenutzbar werden.
Ein kleines Beispiel aus der Praxis: Ich (c.hahn) war 1994 noch Student und bei einer Firma als Hilfskraft beschäftigt. Mein Chef hatte ein Bubblesort-Sortieralgorithmus benutzt um Adressen zu sortieren. Nun kam das System in den Einsatz (damals noch auf 386'er Prozessoren) und wurde nun mit 50.000 bis 100.000 Datensätzen bombardiert. Ergebnis war, das die Maschine bis zu 8 Stunden sortierte, was für ein Produktionssystem absolut tabu war. Er überlegte sich alle möglichen Lösungen, wie z. B. einen Rechner daneben zu stellen, der dann sortierte während der andere dann gleich die sortierte Liste erhielt. Mehrfach versuchte ich ihn darauf aufmerksam zu machen, dass er mal einen anderen effizienteren Algorithmus benutzen sollte. Kurz und gut, nach dem ich mich durchsetzen konnte und in einem Tag einen anderen Algorithmus (heapsort) erstellt hatte, brauchte meine Version nur 2 minuten für 100.000 Datensätze. Wie ihnen weiter hinten bestimmt klar werden wird, ist das eine Eigenschaft, die durch das Laufzeitverhalten der beiden Algorithmen begründet ist. Denn während Bubblesort mit wachsender Datensatzzahl quadratisch wächst (also wenn ich die Anzahl der Elemente verdoppele, brauche ich die vierfache Zeit), wächst Heapsort nur logarithmisch (n*log(n)).Umso mehr Daten, desto ineffizienter wird Bubblesort.
Wie man sieht, kann man mit vernünftigen Algorithmen ganze Rechner einsparen.