HyperLogLog schätzt 370.103 Wörter mit nur 2,71 % Fehler

Sorting, hashing, and sketches on 370,103 words

Dieser Beitrag nimmt 370.103 englische Wörter aus dem dwyl/english-words-Repository und sortiert sie auf sechs Arten, hasht sie in vier Strukturen und skizziert sie mit vier probabilistischen Algorithmen – alles unter Beobachtung von Zeit- und Speicherbedarf. Das Ergebnis: HyperLogLog schätzt die Vokabelgröße mit nur 2,71 % Fehler und 4.096 Registern. Wir bauen jeden Mechanismus von Grund auf, messen ihn an echten Wörtern und prüfen, ob sich die Komplexität lohnt. Dabei zeigen wir, wie Big-O, Big-Theta und amortisierte Analyse das Verhalten von Timsort, Listen-Append und -Insert vorhersagen.