SortedList vs. SortedDictionary vs. Sort ()
Dies ist eine Fortsetzung der Fragen, wie diese eine.
Gibt es irgendwelche Richtlinien für die Feinabstimmung der Leistung? Ich meine nicht, dass Gewinne in big-O, nur sparen einige lineare Zeit.
Zum Beispiel, wie viel kostet Vorsortierung sparen entweder SortedList oder SortedDictionary?
Sagen, dass ich eine person-Klasse mit 3 Eigenschaften Sortieren, einer von Ihnen wird das Alter in Jahren. Soll ich Eimer die Objekte auf das Alter der ersten?
Sollte ich das erste Art auf eine Eigenschaft, verwenden Sie dann die resultierende Liste/dictionary Sortieren auf zwei Eigenschaften und so weiter?
Alle anderen Optimierungen, die in den Sinn?
InformationsquelleAutor der Frage Martin | 2010-01-10
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gut, es ist ein leichter Sieg auf der SortedList. Einfügen eines Artikels erfordert eine binäre Suche (O(log(n)) zu finden, die Einfügemarke, dann eine Liste.Insert (O(n)) zum einfügen des Elements. Die Insert() dominiert, das Auffüllen der Liste benötigt O(n^2). Wenn die input-Elemente bereits sortiert, dann die Insert bricht auf O(1) aber nicht auf der Suche. Das Auffüllen ist jetzt O(nlog(n)). Sie nicht sorgen, wie groß die Oh -, Sortier-zuerst wird immer effizienter. Vorausgesetzt, Sie können es sich leisten, die verdoppelt Lagerung Anforderung.
SortedDictionary ist anders, verwendet es eine rot-schwarz-Baum. Finden Sie die Einfügemarke erfordert O(log(n)). Neugewichtung der Baum sein könnte, Bedarf danach, dass auch in O(log(n)). Füllen Sie das Wörterbuch somit in O(nlog(n)). Mit sortierten Daten nicht ändern, die Bemühungen um die Einfügemarke oder rebalancing, ist es immer noch O(nlog(n)). Jetzt den Oh-Angelegenheiten jedoch, einfügen sortiert Eingabe benötigt der Baum, um Konstanten Gleichgewicht selbst. Es funktioniert besser, wenn der Eingang zufällig ist, wollen Sie nicht sortiert-Eingang.
So Auffüllen SortedList mit sortierter Eingabe und füllen SortedDictionary mit unsortierten Eingabe ist sowohl in O(nlog(n)). Das ignorieren der Kosten für die Bereitstellung von sortierten Daten, die Oh von SortedList ist kleiner als die Oh von SortedDictionary. Das ist eine Implementierung detail, aufgrund der Art und Weise Liste werden, Speicher richtig zuweist. Es nur zu tun hat, also O(log(n)) - Zeit, eine rot-schwarz-Baum zuordnen muss O(n) Zeit. Sehr kleine ach btw.
Bemerkenswert ist, dass weder ein Vergleich über einfach Auffüllen einer Liste, dann Aufruf von Sort(). Das ist auch O(nlog(n)). In der Tat, wenn der Eingang ist schon zufällig sortiert umgehen kann man die Sort () - Aufruf, dieser bricht auf O(n). Die Kosten-Analyse nun bewegen muss, um die Anstrengung, die es dauert, bis die Eingabe sortiert. Es ist schwer zu umgehen, die grundsätzliche Komplexität von Sort(), O(nlog(n)). Es ist vielleicht nicht ohne weiteres zu sehen ist, erhalten Sie möglicherweise die Eingabe sortiert von, sagen wir, eine SQL-Abfrage. Es wird nur länger dauern.
Den Punkt, entweder die SortedList oder SortedDictonary ist, damit die Sammlung sortiert nach Einsätze. Wenn Sie sich sorgen sich nur um das Auffüllen aber nicht mutiert, dann sollten Sie nicht verwenden diesen Sammlungen.
InformationsquelleAutor der Antwort Hans Passant