Asymptotische Komplexität von .NET Collection-Klassen

StackOverflow https://stackoverflow.com/questions/851949

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).

War es hilfreich?

Lösung

MSDN Listen diese:

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:

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

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.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top