Ich habe in letzter Zeit über Skip-Listen gelesen.
Ich habe eine Webanwendung, die recht komplexe Sql-Abfragen für statische Datasets ausführt.
Ich möchte ein Caching-System implementieren, bei dem ich einen md5-Hash der SQL-Abfrage erzeuge und dann ein zwischengespeichertes Dataset für die Abfrage zurückgeben kann, falls es in der Sammlung vorhanden ist.
Welcher Algorithmus wäre besser, Wörterbuch oder eine SkipList? Warum?
Dictionary , definitiv. Zwei Gründe:
Dictionary<TKey, TValue> verwendet eine Hash-Tabelle, die das Abrufen von O (1) (dh konstante Zeit) im Vergleich zu O (log n ) in einer Überspringungsliste ermöglicht.
Dictionary<TKey, TValue> existiert bereits und ist gut getestet und optimiert, während eine Skip-List-Klasse meines Wissens nicht existiert, also müssten Sie Ihre eigene implementieren, die Mühe braucht, um es richtig zu machen und zu testen es gründlich.
Der Speicherverbrauch ist für beide ungefähr gleich (sicherlich die gleiche Komplexität, nämlich O ( n )).
Der Grund, warum Sie SkipList<T> vs Dictionary<TKey,TValue> verwenden würden, ist, dass eine Überspringungsliste ihre Elemente in der richtigen Reihenfolge hält. Wenn Sie die Elemente regelmäßig der Reihe nach aufzählen müssen, ist eine Überspringen-Liste gut, da sie in O (n) aufzählen kann.
Wenn Sie in der Lage sein möchten, in der Reihenfolge aufzuzählen, aber es ist mir egal, ob die Aufzählung O (n lg n) ist, a SortedSet<T> (oder eher ein SortedDictionary<TKey, TValue> ) wäre das, was Sie wollen, weil sie rot-schwarze Bäume (balancierte Binärbäume) verwenden und sie bereits in der Standardbibliothek sind.
Da es äußerst unwahrscheinlich ist, dass Sie Ihren Cache in der Reihenfolge (oder überhaupt) aufzählen wollen, ist eine Überspringungsliste (und ebenso ein Binärbaum) unnötig.
Überspringen-Liste gibt einen Durchschnitt von Log (n) für alle Wörterbuchoperationen an. Wenn die Anzahl der Elemente fest ist, wird eine Locked-Striped-Hash-Tabelle gut funktionieren. Ein im Speicher gespreizter Baum ist auch gut, da Cache das Wort ist. Splay-Bäume geben schneller für den zuletzt aufgerufenen Gegenstand. Als solche in einer Wörterbuchoperation wie finden; [Skip-Listen waren langsam im Vergleich zu Splay-Tree, die wiederum im Vergleich zu Hash-Tabellen langsam waren.] [1] [1]: Ссылка
Wenn eine Lokalisierung in der Datenstruktur benötigt wird, können Ausblendungslisten nützlich sein. Zum Beispiel, Flüge um ein Datum usw. zu finden. Aber ein Cache ist im Speicher, so dass eine Spreizung in Ordnung ist. Hashtable und Splay-Bäume bieten keine Lokalisierung.
Tags und Links c# generics skip-lists