Sind Versuche immer noch eine gute Idee zu modernen Architekturen?

Question

Eine meiner Lieblingsdatenstrukturen im College war die Trie. Es ist eine großartige Datenstruktur, um einen großen Satz von Zeichenfolgen zu halten, wenn die Präfixe gemeinsam genutzt werden. Die Suchfunktionen sind auch schön, da sie bei O (| Länge |) der Saite durchgeführt werden, unabhängig davon, wie viele Saiten im Set sind.

Im Vergleich dazu wäre ein ausgewogener Baum o (log n) in der Anzahl der festgelegten Elemente und alles, was Sie für Vergleiche bezahlen. Eine Hash -Tabelle würde die Hash -Berechnung, den Vergleich usw. beinhalten.

Es ist daher überraschend für mich, dass ich das In der Standardbibliothek der meisten Sprachen gibt es keine Trie -Implementierung.

Der einzige Grund, warum ich mich einfallen konnte, war die Möglichkeit, dass Speicherzugriffskosten es zu teuer machen. Anstatt O (log n) -Spositionen zu untersuchen, wenn Sie eine Baumanschauung durchführen, machen Sie nicht mit allen Konsequenzen o (| Länge |) verschiedene Stellen. Wenn die Saiten lang sind, könnte dies viel zu viel sein.

Ich frage mich also: Wie viel habe ich gerade ein Problem beschrieben? Was tun Sie, wenn Sie einen großen Satz oder eine Karte der Strings speichern müssen?

Answer 1

Ich hatte dies vorher nicht als ein Anliegen angesehen, aber jetzt, wo Sie es erwähnen, gibt es Zeiten, in denen eine Standard -Trie -Implementierung praktisch sein könnte. Auf der anderen Seite werden, soweit ich weiß, Versuche von Python und Perl und anderen von String versierten Sprachen verwendet, die ich jetzt verwende.

Zuletzt habe ich überprüft, wie vor seit langem der BSD -Kernelcode verwendet wurde, um die beste Schnittstelle zum Senden von Paketen auszuwählen. Sieht aus wie Wikipedia hat einige Informationen.

Answer 2

Sie können einfach zwei Beispiel -Apps erstellen und sehen, welche besser abschneidet. Der Speicherzugriff ist günstig, vorausgesetzt, Sie haben keinen Seitenfehler. Dann ist es sehr teuer. Für die Entwicklung von Client -Anwendungen ist es fast immer besser zu verarbeiten, als aus diesem Grund auf Speicher zuzugreifen. Moderne Prozessoren sind lächerlich schnell, aber Cache -Misses verletzen immer noch.

Answer 3

Ich habe einige Leistungstests in C# mit einem Trie und einem Wörterbuch (einer stark typisierten Hash -Tabelle) durchgeführt. Ich stellte fest, dass das Wörterbuch 5-10-mal schneller war als der Trie. Vielleicht könnte meine Implementierung des Tries ein wenig optimiert werden, aber kaum genug, um viel schneller zu sein als (oder vielleicht sogar so schnell wie) das Wörterbuch.

Die enthaltende Methode im Wörterbuch liegt in der Nähe einer O (1) -Operation (je nachdem, wie gut der Hashing -Algorithmus ist). Es ist also nicht einfach, eine Sammlung zu erstellen, die schlägt, solange der Hashing -Algorithmus einigermaßen schnell ist.

Mit einem benutzerdefinierten iEqualityComparer können Sie fast alles als Schlüssel in einem Wörterbuch verwenden, was es ziemlich flexibel macht. Ein Trie ist in dem, was Sie als Schlüssel verwenden können, etwas begrenzter, so dass die Nützlichkeit etwas einschränkt.