11 Nanosekunden pro Wort: Wie ein Entwickler Anagramme absurd schnell macht
11 Nanoseconds per Word: Over-Optimizing Anagrams
David G. Andersen baut einen Löser für ein Word-Ladder-Spiel mit Anagramm-Zügen und optimiert die Anagramm-Erkennung von 173 auf 13 Nanosekunden pro Wort. Statt Buchstaben zu sortieren, kodiert er Wörter als Produkt von Primzahlen – mit speziell abgestimmten Primzahlen, sodass kein Eintrag des Scrabble-Wörterbuchs eine 64-Bit-Ganzzahl überläuft. Der Trick liefert eine kollisionsfreie Kennung für jede Buchstabenkombination.
Wir haben eine kollisionsfreie kanonische 64-Bit-Kennung für die Buchstabenmenge eines (Scrabble-)Wortes gefunden.