Ist Hashset der schnellste Container, in dem man nachschauen kann?

Question

Ich muss überprüfen, ob eine bestimmte Zeichenfolge im Satz anderer enthält:

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

Was ist die beste Art von Container, wenn nur eine Aufgabe davon - eine Reihe von Zeichenfolgen und Überprüfungen zu finden ist, in die sich eine andere befindet oder nicht?

Answer 1

Ja, Hashset ist perfekt dafür, da es einen Wert enthält, um im Gegensatz zu einem Wörterbuch nachzuschlagen, das einen Schlüssel und einen Wert erfordert.

Answer 2

Funktioniert Hashset? Sicher. Aber das ist nicht die Frage, die Sie gestellt haben. Sie haben nach dem gefragt am schnellsten möglich Sieh nach oben.

Ist es am schnellsten möglich? Nein, natürlich nicht, nicht in keiner Weise.

Um zuerst über "schnellste" zu sprechen, müssen wir genau beschreiben, was "schnellste" bedeutet. Meinst du:

• kleinste schlimmster Fall zeitliche Koordinierung
• kleinste Durchschnitt Das Timing hat über viele Timings gemittelt
• Kleinstes durchschnittliches Timing bei einem bestimmten Verwendungsmuster
• etwas anderes

? Bitte klären Sie genau das, was "schnellstmöglich" bedeutet. Wir können Ihnen einen Algorithmus entwickeln, der das ist Theoretisch schnellstmöglich Nur wenn wir genau wissen, was am schnellsten möglich bedeutet für dich.

Angenommen, Sie schreiben einen Compiler. Etwas, das wir ständig in Compilern tun müssen, ist zu prüfen, ob sich eine bestimmte Zeichenfolge in einer Liste von Zeichenfolgen befindet. Vielleicht prüfen wir, ob eine Zeichenfolge ein Schlüsselwort ist. Daher müssen wir nachschlagen, ob sich eine bestimmte Zeichenfolge im Set {"int", "doppelt", "für", "foreach", "Klasse" befindet ... }

Wir könnten diese in ein Hash -Set einfügen und eine anständige Leistung erzielen. Aber wenn wir das wollten bestmögliche Leistung Wir könnten viel besser abschneiden. Wir konnten zum Beispiel eine Analyse einiger Milliarden Zeilen vorhandener Quellcode durchführen, um herauszufinden, welche Schlüsselwörter am häufigsten waren und welche am wenigsten häufig waren Kein Schlüsselwörter überhaupt und (2) die häufigsten Schlüsselwörter auf Kosten der Erkennung anderer Schlüsselwörter schnell erkennen.

Beachten Sie, dass dies eine statische Analyse erfordert; Obwohl es in typischen Fällen eine gute Leistung erbringt, funktioniert es in den seltenen Fällen, in denen viele seltene Schlüsselwörter verwendet werden, schlecht. Ein anderer Ansatz, den wir ergreifen könnten, wäre, a zu schreiben Selbsteinstellung Hash Table das dynamisch identifiziert, wenn bestimmte Zeichenfolgen häufig gesucht wurden.

Betrachten Sie beispielsweise, wenn Sie eine Implementierung der JScript -Laufzeit schreiben. Wir müssen häufig nach einer Zeichenfolge in einer Reihe von Saiten suchen:

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

Hier müssen wir die String -Balken in dem von "Foo" identifizierten Objekt zehnmal nachschlagen. Die Hash -Tabelle in "foo", die implementiert, dass Lookup das erste Mal durch die Schleife bemerkt, dass "Balken" verwendet wurde, sodass sie die Hash -Tabellenstruktur dynamisch optimiert, damit die zweite Die Zeit durch die Schleife ist die Suche schneller. Dies ist die Strategie, die wir in unserer Implementierung von JScript angewendet haben.

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

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

Weil wir nicht mehr Analysen durchführen und feststellen, dass "Hey, wir haben diesen Hash-Tisch nur dreimal wieder optimiert, und jetzt werden wir alles wieder tun, vielleicht sollten wir ihn einfach so lassen, wie es ist."

Zum Glück für uns waren wir nicht wie Sie nach dem am schnellsten möglich Sieh nach oben. Wir suchten nur nach einem einigermaßen schnell Sieh nach oben.

Können Sie sorgfältig und vollständig beschreiben, wofür Ihr Verwendungsfall für die ist? schnellstmögliche Suche? Es gibt viele Algorithmen, mit denen Sie die Lookups beschleunigen können, aber sie werden sehr kompliziert.