Ist HashSet <T> der schnellste Container zum Nachschlagen?

Question

Ich brauche, dass bestimmte Zeichenfolge zu überprüfen, in dem Satz von anderen enthält:

private bool Contains(string field) 
{ 
    return this.Fields.Contains(field); // HashSet<string> local property 
} 

Was ist die beste Art von Behälter ist zu verwenden, wenn nur eine Aufgabe davon - eine Reihe von Zeichenkette zu halten und die Prüfung hat ein anderes ist in oder nicht?

Answer 1

Ja, das ist HashSet perfekt für diesen, da es einen Wert enthält im Gegensatz zu einem Wörterbuch nachschlagen, die einen Schlüssel und einen Wert erfordert.

Answer 2

Funktioniert HashSet? Sicher. Aber das ist nicht die Frage, die du gestellt hast. Sie haben nach dem schnellstmöglichen Lookup gefragt.

Ist es das schnellste möglich? Nein, natürlich nicht, nicht in jedem Maße.

Zunächst, um über "Schnellster" zu sprechen, müssen wir genau beschreiben, was "Schnell" bedeutet. Meinen Sie:

• kleinste schlimmster Fall Timing
• kleinsten Durchschnitt Timing viele Timings gemittelt über
• kleinste durchschnittliche Zeit ein bestimmtes Nutzungsmuster gegeben
• etwas anderes

? Bitte präzisieren Sie, was "schnellstmöglich" bedeutet. Wir können Ihnen einen Algorithmus ausdenken, der in der Theorie am schnellsten möglich ist nur wenn wir genau wissen, was am schnellsten möglich ist bedeutet für Sie.

Angenommen, Sie schreiben einen Compiler. In Compilern müssen wir ständig prüfen, ob eine bestimmte Zeichenkette in einer Zeichenkettenliste enthalten ist. Vielleicht prüfen wir, ob eine Zeichenkette ein Schlüsselwort ist, also müssen wir nachsehen, ob eine gegebene Zeichenkette innerhalb der Menge liegt ("int", "double", "for", "foreach", "class" ...). }

Wir könnten diese in einem Hash-Set setzen und anständige Leistung bekommen. Aber wenn wir die bestmögliche Leistung wollten, könnten wir viel besser machen. Wir könnten zum Beispiel eine Analyse von einigen Milliarden Zeilen des vorhandenen Quellcodes durchführen, um herauszufinden, welche Schlüsselwörter am häufigsten und welche am seltensten waren, und dann eine benutzerdefinierte Hash-Tabelle schreiben, die für (1) das schnelle Zurückweisen von Dingen optimiert wurde überhaupt keine Keywords und (2) die am häufigsten verwendeten Keywords auf Kosten der Erkennung anderer Keywords schnell erkennen.

Beachten Sie, dass dies eine statische Analyse erfordert; Obwohl es in typischen Fällen gut funktioniert, schneidet es in den seltenen Fällen, in denen viele seltene Keywords verwendet werden, schlecht ab. Ein anderer Ansatz, den wir nehmen könnten, wäre, eine Selbstoptimierung Hash-Tabelle zu schreiben, die dynamisch identifiziert, wenn bestimmte Strings häufig gesucht wurden.

Betrachten Sie zum Beispiel, wenn Sie eine Implementierung der JScript-Laufzeit schreiben.Wir müssen häufig suchen Sie nach einer Zeichenkette in einer Reihe von Strings:

for(i = 0; i < 10; ++i) { foo.bar(i); } 

Hier stellen wir die Zeichenfolge sehen müssen „bar“ in das Objekt identifiziert durch „foo“ zehnmal. Die Hashtabelle in "foo", die diese Suche implementiert, merkt das erste Mal durch die Schleife, dass "bar" verwendet wurde, so dass es dynamisch die Hash-Tabellenstruktur so zwickt, dass die Suche schneller ist. Dies ist die Strategie, die wir bei der Implementierung von JScript angewendet haben.

Nun, die den Fall für Schleifen optimiert, aber es macht diesen Fall möglicherweise langsamer als es sein könnte:

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); } 

, weil wir nicht mehr tun, Analyse und erkennen, „hey, wir nur nachoptimiert diese Hashtabelle dreimal, und jetzt werden wir alles wieder machen, vielleicht sollten wir es einfach so lassen wie es ist. "

Zum Glück für uns waren wir nicht, wie Sie, auf der Suche nach der schnellstmöglichen Lookup. Wir suchten nur nach einem halbwegs schnellen Lookup.

Können Sie sorgfältig und vollständig beschreiben, was genau Ihr Anwendungsfall für die schnellstmögliche Suche ist? Es gibt viele Algorithmen, die Sie verwenden können, um Nachschläge zu beschleunigen, aber sie werden sehr kompliziert.