Asymptotische Komplexität von .NET Collection-Klassen
-
21-08-2019 - |
Frage
Gibt es irgendwelche Ressourcen über die asymptotische Komplexität (big-O und den Rest) von Methoden der .NET-Collection-Klassen (Dictionary<K,V>
, List<T>
etc ...)?
Ich weiß, dass die Dokumentation der C5 Bibliothek einige Informationen über sie enthält ( Beispiel ), aber ich bin auch in Standard-.NET-Auflistungen interessiert ... (und PowerCollections' Information wäre auch schön).
Lösung
MSDN Listen diese:
-
Dictionary<,>
-
List<>
-
SortedList<,>
(edit: falscher Link, hier ist die generische Version ) -
SortedDictionary<,>
usw. Zum Beispiel:
Die SortedList (TKey, TValue) generic Klasse ist ein binärer Suchbaum mit O (log n) Retrieval, wobei n die ist Anzahl der Elemente im Wörterbuch. Dabei ist es ähnlich wie die SortedDictionary (TKey, TValue) generic Klasse. Die beiden Klassen haben ähnliche Objektmodelle, und beide haben O (log n) Retrieval. Wo die beiden Klassen unterscheiden, ist in der Speichernutzung und Geschwindigkeit von Einsetzen und Entfernen:
SortedList (TKey, TValue) verbraucht weniger Speicher als SortedDictionary (TKey, TValue).
SortedDictionary (TKey, TValue) hat schnelleres Einsetzen und Entfernen Operationen für unsortierte Daten, O (log n) zu O (N) im Gegensatz zum SortedList (TKey, TValue).
Wenn die Liste wird auf einmal bevölkert aus sortierten Daten, SortedList (TKey, TValue) schneller als SortedDictionary (TKey, TValue).
Andere Tipps
Diese Seite fasst einige der Zeit comlplexities für verschiedene collection-Typen mit Java, obwohl sie genau für .NET gleich sein sollten.
ich die Tabellen von dieser Seite genommen haben und verändert / erweitert sie für das .NET Framework. Siehe auch die MSDN-Seiten für SortedDictionary und SortedList , die detailliert die Zeit Komplexität für verschiedene Operationen erforderlich.
Suchen
Type of Search/Collection Types Complexity Comments Linear search Array/ArrayList/LinkedList O(N) Unsorted data. Binary search sorted Array/ArrayList/ O(log N) Requires sorted data. Search Hashtable/Dictionary<T> O(1) Uses hash function. Binary search SortedDictionary/SortedKey O(log N) Sorting is automated.
Hol- und Einbringungs
Operation Array/ArrayList LinkedList SortedDictionary SortedList Access back O(1) O(1) O(log N) O(log N) Access front O(1) O(1) N.A. N.A. Access middle O(1) O(N) N.A. N.A. Insert at back O(1) O(1) O(log N) O(N) Insert at front O(N) O(1) N.A. N.A. Insert in middle O(N) O(1) N.A. N.A.
Das Löschen sollte die gleiche Komplexität wie Einfügung für die zugehörige Sammlung hat.
SortedList hat einige bemerkenswerte Besonderheiten zum Einsetzen und Retrieval.
Einfügen (Add-Methode):
Diese Methode ist eine O (n) für den Betrieb unsortierten Daten, wobei n Count. Es ist eine O (lügen n) Operation, wenn die neuen Element am Ende der addierte Liste. Wenn das Einfügen eines Resize verursacht, der Betrieb ist O (n).
Retrieval (Item-Eigenschaft):
Suchen Sie den Wert dieser Eigenschaft eine O (lügen n) -Operation, wobei n Anzahl. die Eigenschaft Einstellung ist ein O (log n) Operation, wenn der Schlüssel ist, bereits in der SortedList <(Of <(TKey, TValue>)>). Wenn der Schlüssel nicht in der Liste, die Eigenschaft Einstellung ist eine O (n) Betrieb für unsortierte Daten oder O (log n), falls das neue Element wird auf dem zugegebenen Ende der Liste. Wenn eine Insertion verursacht die Größe, die Operation ist O (n).
Beachten Sie, dass ArrayList
zu List<T>
im Hinblick auf die Komplexität aller Operationen entspricht.
Ich weiß nicht, in der Regel (die andere Antwort vielleicht gerade gebucht haben Sie genau, was Sie nach) - aber Sie können diese und andere Methoden natürlich reflektieren mit ILSpy (ein wenig umständlich mit FSharp Code, true) und dies schließlich ergibt diese Funktion als C #:
internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
while (true)
{
SetTree<a> setTree = s;
if (setTree is SetTree<a>.SetOne)
{
break;
}
if (setTree == null)
{
return n;
}
SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
SetTree<a> arg_23_0 = setNode.item3;
n = setNode.item1;
s = arg_23_0;
}
return ((SetTree<a>.SetOne)s).item;
return n;
}
Okay, so ist dies nicht genau ‚richtiger‘ Code in C # Bedingungen - aber die Gegenwart der while(true)
Schleife impliziert, kann es nicht O (1) mindestens sein; wie für das, was es tatsächlich ist ... na ja, mein Kopf schmerzt zu sehr, um herauszufinden:)
Auf dieser Seite finden kurze Notizen über einige der wichtigsten Vor-und Nachteile für die meisten .NET Kollektionen:
Es gibt nicht so etwas wie „Komplexität der Collection-Klassen“. Vielmehr haben verschiedene Operationen auf diesen Sammlungen unterschiedlicher Komplexität. Zum Beispiel das Hinzufügen eines Elements zu einem Dictionary<K, V>
...
... nähert sich ein O (1) Betrieb. Wenn die Kapazität erhöht werden muss, das neue Element, wobei dieses Verfahren wird zu einem O (n) Betrieb aufzunehmen, wo
n
Count
ist.
Während ein Element aus einem Abrufen Dictionary<K, V>
...
... nähert sie einen O (1) -Operation.
Die Dokumentation sagt sie baut auf einem binären Baum ist, und erwähnt nicht das maximale Element verfolgt. Wenn die Dokumentation richtig ist, bedeutet, dass es O (log n) sein sollte. Früher gibt es mindestens einen Fehler in der Sammlung Dokumentation sein (in Bezug auf eine Array-backed Datenstruktur als einen binären Suchbaum), aber das wurde korrigiert.