Das ‚Schiffe versenken’ – Suchalgorithmen

Worum geht es in dieser Aktivität?

Computer speichern viele Informationen, die sie schnell durchsuchen können müssen. Eines der größten Suchprobleme der Welt steht den Internetsuchmaschinen gegenüber, die Milliarden von Websites in Sekundenbruchteilen durchsuchen müssen. Daten, wie ein Wort, eine Barcodenummer oder der Name eines Autors, nach denen ein Computer suchen muss, werden Suchbegriffe genannt.

Computer können Informationen schnell verarbeiten. Du denkst vielleicht, dass das Suchen immer am Anfang des Speichers beginnt und so lange ausgeführt wird, bis die gesuchte Information gefunden worden ist. So sind wir bei der linearen Suche vorgegangen. Und lineare Suche ist auch bei Computern eine langsame Methode. Stell dir z.B. vor, ein Supermarkt hat 10.000 verschiedene Produkte auf den Regalen verteilt. Wenn der Barcode an der Kasse gescannt wird, muss der Computer 10.000 Zahlen durchsuchen, um die Produktbezeichnung und den Preis zu finden. Selbst wenn es nur eine Tausendstel Sekunde braucht jeden Code zu prüfen, dauert es 10 Sekunden, um die gesamte Liste durchzugehen. Kannst du dir vorstellen wie lange es dauern würde, alle Einkaufswaren einer ganzen Familie zu verarbeiten!

Binäre Suche ist eine bessere Strategie. In dieser Methode sind die Zahlen bereits geordnet. Die Überprüfung des mittleren Wertes der Liste zeigt, welche Hälfte den Suchbegriff enthält. Bezüglich des vorigen Supermarktbeispiels können 10.000 Waren nun in 14 Schritte durchsucht werden, was zwei Hundertstel Sekunden bedeutet – kaum vorstellbar schnell.

Hashing ist die dritte Strategie für Datensuche. Hier wird der Suchbegriff verarbeitet, um genau anzugeben, wo die Informationen gefunden werden können. Wenn z.B. eine Telefonnummer gesucht wird, können alle Ziffern der Nummer addiert und der Rest der Summe geteilt durch 11 verwendet werden. Insofern ist Hashing hier ähnlich wie die Prüfziffer, die in Aktivität 4 betrachtet wurde – nur wenige Daten, deren Werte von den anderen bearbeiteten Daten abhängen. Normalerweise findet der Computer sofort die gesuchten Daten. Es ist sehr unwahrscheinlich, dass mehrere Schlüssel auf denselben Speicherbereich zeigen. Ist das der Fall, durchsucht der Computer alle möglichen Fälle bis der gesuchte Wert gefunden worden ist.

Meistens benutzen Computerprogrammierer eine Variante der Hashing-Suchstrategie, falls die Daten nicht geordnet gespeichert werden müssen, oder ein zu langsamer Suchablauf inakzeptabel ist.