Cleverer/2
Wie man die binäre Suche pimpen kann
Sortierte Datenbestände lassen sich effizient mit binärer Suche durchsuchen. Mit Kenntnissen über die Struktur der Daten kann man die Performance des Algorithmus sogar noch um ein gehöriges Maß steigern.
Hacker veröffentlichen im Netz immer mal wieder riesige Batzen von Passwortlisten. Die Webseite HaveIBeenPwned.com sammelt sie und stellt sie zum Download bereit. In der Datei liegen die Passwörter allerdings nicht im Klartext vor, sondern als SHA1-Hashes in hexadezimaler Schreibweise, schön lexikografisch sortiert, je ein Hash pro Zeile. Kollegin Pina hat in c’t 5/2019 ein Python-Skript vorgestellt, mit dessen Hilfe man die 25 GByte große Textdatei mit über 550 Millionen Hashes in Sekundenbruchteilen nach einem bestimmten Passwort-Hash durchsuchen kann [1]. Das war der Startschuss zu einer Coding-Battle zwischen Pina und mir, die zur Aufgabenstellung hatte, das effizienteste Verfahren zum Durchsuchen von derlei Datenbeständen zu entwickeln. Es ging dabei nur um den schnellsten Algorithmus; die Daten durften beliebig darauf zugeschnitten werden.
Pina hatte sich der binären Suche bedient. Das Prinzip kennen Sie vom Zahlenratespiel: Jemand denkt sich eine Zahl zwischen 0 und 100, und Sie müssen mit möglichst wenig Fehlversuchen erraten, welche es ist. Ihr Widerpart gibt Ihnen nach jedem Versuch nur den Tipp, dass die gesuchte Zahl kleiner oder größer ist. Schlauerweise tippen Sie erst einmal auf die 50, weil sie genau in der Mitte liegt und deshalb den Suchraum auf einen Schlag halbiert. In der verbleibenden Hälfte tippen Sie wieder auf die Mitte und so weiter und so fort, bis Sie die richtige Zahl genannt haben. Im Mittel brauchen Sie log2 100 Versuche, weshalb man die binäre Suche auch als logarithmische Suche bezeichnet.