C++: Performance der binären Suche steigern

Inhaltsverzeichnis

Hacker veröffentlichen im Netz immer 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 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. 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 log₂ 100 Versuche, weshalb man die binäre Suche auch als logarithmische Suche bezeichnet.

Probleme

Pinas Skript muss vor jedem Vergleich den Anfang der Zeile suchen, da es sein kann, dass die berechnete Mitte mitten in der Zeile liegt. Es ist leider nicht möglich, die Position eines Zeilenanfangs arithmetisch zu ermitteln, weil die Zeilen in der HaveIBeenPwned-Datei unterschiedlich lang sind. Auf den Hash folgt nämlich eine Dezimalzahl, die angibt, wie häufig das zugrunde liegende Passwort in den Listen gefunden wurde:

Das war die Leseprobe unseres heise-Plus-Artikels "C++: Performance der binären Suche steigern". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.