Nadel im Heuhaufen in der Informatik

Der langsame Weg: alles ansehen

Wenn du nichts darüber weißt, wo die Nadel ist, bleibt nur, jedes Stück Heu zu prüfen, bis du sie findest. In der Informatik heißt das lineare Suche. Im Durchschnitt prüfst du die Hälfte von allem, bevor du Erfolg hast, im schlimmsten Fall alles. Es funktioniert immer, aber die Zeit wächst mit der Größe des Haufens.

Sortieren ändert alles

Stell dir nun vor, das Heu wäre der Reihe nach angeordnet, wie Wörter in einem Wörterbuch. Ein klügeres Verfahren, die binäre Suche, öffnet in der Mitte, entscheidet, in welcher Hälfte die Antwort liegt, und wirft die andere weg. Wiederhole das, und eine Million Einträge sind in etwa 20 Schritten durchsucht. Der Haken: Der Haufen muss zuerst geordnet sein, und ein Heuhaufen ist es nie.

Indizes: mogeln durch Vorbereitung

Datenbanken und Suchmaschinen umgehen das Problem, indem sie die harte Arbeit vorher erledigen. Sie bauen einen Index, wie das Register hinten in einem Buch, das dir sagt, auf welcher Seite ein Wort steht. Das Nachschlagen wird schnell, weil die Zeit vorher investiert wurde. Für einen echten Heuhaufen gibt es keinen Index, und genau deshalb gibt es die Redewendung.

Einem Signal folgen

Ein Metalldetektor ist anders. Er sagt dir nicht, wo die Nadel ist, aber ob du näher kommst. Stell dir eine Zahl vor, die steigt, wenn du dich näherst. Dann gilt eine einfache Regel: einen Schritt machen, prüfen, ob das Signal stärker wurde, und in der Richtung weitergehen, die es verbessert. Programmierer nennen eine Variante davon Hill Climbing, und sie steckt hinter vielen praktischen Optimierungen.

Im Spiel wird das Signal aus deiner Entfernung zum nächsten Metallstück im Vergleich zur Reichweite des Detektors berechnet. Das Piepen wird schneller, je näher die Zahl an 1 kommt, sodass dein Ohr das Hill Climbing für dich übernimmt. Mehr in So funktioniert der Metalldetektor.

Wenn Signale versagen

Hill Climbing kann stecken bleiben. Liegt viel Schrottmetall nahe der Nadel, führt dich das stärkste Signal vielleicht zu einem Nagel. Das Spiel löst das, indem die höheren Detektoren die Nadel unterscheiden können. Echte Suchen stoßen auf dasselbe Problem und nutzen bessere Sensoren oder zusätzliche Filter.

Der Heuhaufen als Daten

Der Heuhaufen im Spiel ist selbst eine Datenstruktur: ein Gitter aus 88 mal 40 mal 88 Zellen, jede mit einer Zahl für die Heudichte. Graben heißt Zahlen ändern, und Chunks von 16 Zellen halten die Arbeit klein. Wie das funktioniert, steht in So funktioniert der Heuhaufen.