Die Komplexität der Suchoperation auf einem nedtrie (bitweise trie)

Question

Ich habe vor kurzem gehört, über nedtries und beschlossen, zu versuchen, sie umzusetzen, aber mich etwas stört über die Komplexität ihrer Suchoperation; Ich kann es nicht ertragen, warum sie eigentlich so schnell sein.

Von dem, was ich verstand, die erwartete Komplexität ihrer Suchoperation sollte O (m / 2) mit m der Größe des Schlüssels in Bits. Wenn Sie es auf die Komplexität der Suchoperation in einem traditionellen binären Baum vergleichen, du erhältst:                  log2 (n)> = m / 2

Lassen Sie uns der Schlüssel 32bits lang sein: log2 (n)> = 16 <=> n> = 65536

sollte also nedtries schneller sein als binäre Bäume aus 65536 Artikel starten. Allerdings behaupten die Verfasser sie sind immer schneller als Binärbaum, also entweder meine Vermutung auf ihrer Komplexität ist falsch oder die bei jedem Schritt der Suche durchgeführten Berechnungen sind erheblich schneller in einem nedtrie.

Also, was ist es?

Answer 1

Wenn Sie kleinere Bäume haben, können Sie kleinere Tasten verwenden!

Answer 2

(Anmerkung I der Autor von nedtries bin). Ich glaube, meine Erklärung der Komplexität auf der Vorderseite des Sinns nedtries Seite macht? Vielleicht nicht.

Der Schlüssel Sie fehlt ist, dass es die Unterschied zwischen Bits, die Komplexität bestimmt. Je mehr die Differenz, die die Suchkosten senken, während die den Unterschied senken, desto höher ist die Suchkosten.

Die Tatsache, das funktioniert stammt aus modernen Out-of-Order-Prozessoren. Als grobe Vereinfachung, wenn Sie den Hauptspeicher Code vermeiden läuft über 40-80x schneller, als wenn Sie auf den Hauptspeicher abhängig sind. Das heißt, Sie 50-150 ops in der Zeit ausführen kann es eine einzige Sache, aus dem Speicher lädt. Das bedeutet, dass können Sie ein wenig Scan und herauszufinden, was tun Knoten wir es dauert nicht viel länger als die Zeit Blick auf nächstes gehen sollte die Cache-Zeile für diesen Knoten in den Speicher.

laden

Dies entfernt effektiv die Logik, die Bit-Scannen und alles andere aus der Komplexitätsanalyse. Sie konnten alle O (N ^ N) sein, und es würde keine Rolle spielen. Was zählt, ist jetzt, dass die Auswahl des nächsten Knotens zu sehen, tatsächlich frei ist, so ist es die Anzahl der Knoten ist, die zur Prüfung geladen werden muss, ist die Skalierung Einschränkung und deshalb ist es die durchschnittliche Anzahl der Knoten an aus der Gesamtzahl sah von Knoten, die ihre mittlere Komplexität, weil Haupt Langsamkeit Speicher bei weitem die größte Komplexität Einschränkung ist.

Ist das sinnvoll? Es bedeutet weirdnesses wie wenn einige Bits an einem Ende des Schlüssels dicht gepackt sind, sondern lose am anderen Ende des Schlüssels gepackt, sucht in der dicht gepackten Ende wird sehr deutlich langsamer (O nähert (log N), wobei N die Zahl ist von dichten Elementen) als Suchaktionen im locker gepackten Ende (annähernd O (1)).

Ein Tag bald wird ich umgehen, um neue Funktionen hinzugefügt, die die Vorteile dieser Funktion von bitweise Versuchen dauern, so kann man sagen, „hinzufügen, diese Knoten zu einem losen / dicht gepackten Raum und gibt den Schlüssel, den Sie gewählt haben“, und alle Arten von Variationen über dieses Thema. Leider, wie immer, kommt es zu Zeit und Anforderungen an seine Zeit nach unten.

Niall