Effizienz von C # -Wörterbüchern

13

C # -Wörterbücher sind ein einfacher Weg, um herauszufinden, ob etwas existiert usw. usw. Ich habe jedoch eine Frage dazu, wie sie funktionieren. Angenommen, ich verwende anstelle eines Wörterbuchs eine ArrayList. Anstatt ContainsKey(oder eine äquivalente Methode in einer anderen Sprache) zu verwenden, durchlaufe ich die ArrayList, um zu überprüfen, ob dort etwas vorhanden ist (oder eine binäre Suche durchzuführen, wenn Daten sortiert sind oder ähnliches). Was ist der Unterschied in der Effizienz? ContainsKeyVerwendet die Methode eine effizientere Methode, als die Schlüssel zu durchlaufen und zu überprüfen, ob das, was ich suche, vorhanden ist?

Wenn wir beispielsweise eine bestimmte Hash-Funktion erstellt haben, die dem Datentyp entspricht, den ich habe, und der speziell für diesen Datensatz entwickelt wurde, dann ist diese Hash-Funktion in der Tat schneller als das Durchlaufen von Daten. Aber Wörterbücher sind allgemein. Die ContainsKey-Methode ist nicht spezifisch für die Daten, die sie erhält, sondern eine allgemeine Suchmethode.

Grundsätzlich frage ich: Wörterbücher sind für Programmierer hilfreich. Sie enthalten Methoden, die bei vielen Dingen helfen, und sie kombinieren Zeichenfolgen mit Ganzzahlen (Schlüssel und Werte) und vielem mehr. Aber was bieten sie in Bezug auf Effizienz? Was ist der Unterschied in einem mit dictionaryvs einem ArrayListvonstructs(string,int)

c# efficiency dictionary John Demetriou
quelle
Sie vergleichen hier wirklich Äpfel mit Orangen. Ich denke, das Schlüsselwort, das Sie suchen, ist Data Structures Dieser Wiki-Link kann Ihnen mehr helfen
Ampt

Antworten:

20

Du musst ein wenig graben , um zu sehen , wie das Wörterbuch in C # implementiert ist - Es ist nicht so offensichtlich , wie HashMap (eine Hash - Tabelle) oder TreeMap (a sortierten Baum) (oder ConcurrentSkipListMap - eine Sprungliste ).

Wenn Sie in den Abschnitt "Bemerkungen" eintauchen:

Die generische Dictionary-Klasse bietet eine Zuordnung von einer Reihe von Schlüsseln zu einer Reihe von Werten. Jede Ergänzung des Wörterbuchs besteht aus einem Wert und dem zugehörigen Schlüssel. Das Abrufen eines Werts mithilfe seines Schlüssels erfolgt sehr schnell in der Nähe von O (1), da die Dictionary-Klasse als Hash-Tabelle implementiert ist.

Und da haben wir es. Es ist eine Hash-Tabelle . Beachten Sie, dass ich den Wikipedia-Artikel dort verlinkt habe - es ist eine ziemlich gute Lektüre. Vielleicht möchten Sie den Abschnitt zur Kollisionsauflösung lesen. Es ist möglich, einen pathologischen Datensatz abzurufen, bei dem die Suche auf O (N) verschoben wird (z. B. fällt alles, was Sie einfügen, aus irgendeinem Grund auf denselben Hashwert oder Index in der Hash-Tabelle und Sie haben keine lineare Prüfung mehr ).

Während das Wörterbuch eine Allzwecklösung ist, sollten Sie keine konkreten Typen (wie das Wörterbuch) weitergeben - Sie sollten die Schnittstellen weitergeben. In diesem Fall ist diese Schnittstelle IDictionary( docs ). Dazu sind Sie perfekt in der Lage, Ihre eigene Wörterbuchimplementierung zu schreiben, die die Daten optimal für Ihre Daten ausführt.

In Bezug auf die Effizienz verschiedener Lookup / enthält?

  • Eine unsortierte Liste durchgehen: O (N)
  • Binäre Suche eines sortierten Arrays: O (log N)
  • Sortierter Baum: O (log N)
  • Hash-Tabelle: O (1)

Für die meisten Menschen ist die Hash-Tabelle genau das, was sie wollen.

Möglicherweise stellen Sie fest, dass das SortedDictionary genau das ist, was Sie möchten:

Die SortedDictionary<TKey, TValue>generische Klasse ist ein binärer Suchbaum mit O-Abruf (log n), wobei n die Anzahl der Elemente im Wörterbuch ist. In dieser Hinsicht ähnelt es der SortedList<TKey, TValue>generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle und beide haben einen O (log n) -Abruf.

Wenn die Datenstruktur jedoch nicht optimal zu Ihren Daten passt, erhalten Sie die Tools (die Schnittstellen), mit denen Sie eine schreiben können, die für Ihre Daten am besten geeignet ist.

Das Wörterbuch selbst ist ein abstrakter Datentyp . Sie geben mir ein Wörterbuch und ich weiß, was ich damit machen kann und welche Tools ich dort verwenden kann, da es ein Wörterbuch ist. Wenn Sie mir eine ArrayList geben würden, würde ich meinen eigenen Code zum Suchen, Einfügen oder Löschen von Elementen aus der Liste schreiben. Dies verschwendet meine Zeit und bedeutet auch, dass die Wahrscheinlichkeit eines Fehlers größer ist, wenn ich den Code immer wieder von Ort zu Ort kopiere.

Robert Harvey
quelle
5
O (1) ist nicht unbedingt "schnell". Das Durchlaufen einer Liste kann immer noch schneller sein als eine Hashtabelle für die Sammlungsgrößen, mit denen sich die Anwendung befasst.
Whatsisname
5
@whatsisname zu keinem Zeitpunkt behaupte ich, dass O (1) schnell ist. Es hat sicherlich das Potenzial, das schnellste zu sein. Das Iterieren über die Schlüssel einer Hashtabelle ist langsamer als das einer ArrayList (es sei denn, Sie verwenden etwas wie die von Java bereitgestellte LinkedHashMap ). Es ist wichtig, Ihre Daten und deren Verhalten zu kennen und die entsprechende Sammlung dafür auszuwählen - und wenn diese nicht vorhanden ist, schreiben Sie sie. Vorausgesetzt natürlich, dass sich ein solches Unterfangen tatsächlich lohnt (Profil zuerst!).
In Ihrem Zitat heißt es: "Das Abrufen eines Werts mithilfe seines Schlüssels ist sehr schnell, in der Nähe von O (1), da die Dictionary-Klasse als Hash-Tabelle implementiert ist.", So dass das OP die beiden Konzepte verwechseln könnte. Mit anderen Worten, ich wollte klarstellen, dass Big O nicht die ganze Geschichte über "Geschwindigkeit" erzählt.
Whatsisname
3
@whatsisname, der direkt von Microsoft stammt. Die Verwendung eines Schlüssels zum Nachschlagen eines Werts, sofern Sie nicht über eine pathologische Hashtabelle verfügen (die Hash-Kollisionen mit einem anderen Mechanismus löst), ist schneller als das Nachschlagen in einem Baum oder einer sortierten Liste (oder einer unsortierten Liste). Java verwendet beispielsweise die lineare Prüfung (Schritt 1) ​​für die Kollisionsauflösung. Dies kann langsamer sein, wenn die Tabelle zu voll ist oder zu viele Hashes kollidieren. Für den allgemeinen Fall ist es jedoch gut genug.
Als relevantes Beispiel habe ich kürzlich Code in C ++ optimiert, der ursprünglich eine Hash-Tabelle für Datensätze mit etwa 20 Einträgen verwendete und dessen Fertigstellung etwa 400 ms dauerte. Durch das Wechseln zu einem Binärbaum wurde dieser Wert auf 200 ms gesenkt, da der Zugriff auf den Baum einfacher ist. Aber ich konnte es noch weiter reduzieren, indem ich ein Array von Name-Wert-Paaren und eine heuristische Suchfunktion verwendete, die anhand früherer Zugriffsmuster erraten, wo ich anfangen sollte. Es kommt also darauf an, wie viele Daten vorhanden sind und welche Muster in den Zugriffen vorhanden sind (z. B. Lokalität).
Jules