Wie wird die Liste <T> .IndexOf() in C# implementiert?

Question

Ich dachte über die Leistung des Anrufs List<T>.Indexof(item) nach. Ich bin nicht sicher, ob es eine O (n) Leistung für einen sequentiellen Algorithmus oder O (log (n)) Leistung für einen binären Baum ist.

Answer 1

Mit Reflektor für .NET können wir sehen:

public int IndexOf(T item) 
{ 
    return Array.IndexOf<T>(this._items, item, 0, this._size); 
} 

public static int IndexOf<T>(T[] array, T value, int startIndex, int count) 
{ 
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count); 
} 

internal virtual int IndexOf(T[] array, T value, int startIndex, int count) 
{ 
    int num = startIndex + count; 
    for (int i = startIndex; i < num; i++) 
    { 
     if (this.Equals(array[i], value)) 
      return i; 
    } 
    return -1; 
} 

Answer 2

Hinter den Kulissen wird ein normaler array verwendet, tatsächlich ruft die IndexOf Methode einfach Array.IndexOf auf. Da Arrays keine Elemente sortieren, ist die Leistung O (n).

Answer 3

Es ist O(n) nach MSDN.

Diese Methode führt eine lineare Suche aus; Daher ist diese Methode eine O (n) -Operation, wobei n die Anzahl ist.

Answer 4

List<T> wird durch ein flaches Array unterstützt, so list.IndexOf(item) ist O (n).

Answer 5

Wenn Sie eine schnellere Leistung benötigen, betrachten Sie HashSet<T>. Es ist ein Kompromiss zwischen Geschwindigkeit und Speicher, aber es ist es wert, wenn Sie Ersteres gegenüber Letzterem bewerten.

(es ist nicht genau das gleiche wie ein List<T>, es wie eine einzige Spalte Wörterbuch verhält, sondern auch für Fälle, in denen Sie eine einzigartige Liste gehen zu müssen, ist es eine Möglichkeit, es zu tun.)

Answer 6

List<T>.IndexOf ist O (n) was tatsächlich optimal für einen ungeordneten Satz von n Elementen ist.

List<T>.BinarySearch ist O (log n) aber funktioniert nur korrekt, wenn die Liste sortiert ist.

Answer 7

Dies ist eine alte Frage, aber ich dachte, dieser Link interessant wäre: Zugang zu Ihnen, dass heute Experiment: List internals and performance when adding new elements

Answer 8

Meine verstorbenen Antwort, aber ich denke, es ist erwähnenswert, können direkt die Quellen MS: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

Kein Nachdenken mehr nötig, da der .NET BCL-Code jetzt online verfügbar ist.

Implementiert eine Liste variabler Größe, die ein Array von Objekten zum Speichern der Elemente verwendet. Eine Liste hat eine Kapazität, die dem internen Array zugewiesen ist. Wenn Elemente zu einer Liste hinzugefügt werden, wird die Kapazität von die Liste automatisch nach Bedarf erhöht, indem das interne Array erneut zugewiesen wird.

Wie als Array implementiert und man lineare Suche, ausführung kann leicht ableiten, dass die algorithmische Komplexität des Verfahrens IndexOfO (n) ist.

Wie von anderen die genannten Informationen sind auf der Msdn öffentlich zugänglich: https://msdn.microsoft.com/en-us/library/e4w08k17(v=vs.110).aspx

Dieses Verfahren eine lineare Suche durchführt; Daher ist diese Methode eine O (n) -Operation, wobei n Count ist.

Auch hier können Sie die Quellen überprüfen und seing am Ende, dass die statische Hilfsmethode IndexOf der Array-Klasse tatsächlich hinter den Kulissen genannt wird:

http://referencesource.microsoft.com/#mscorlib/system/array.cs

Wenn die Liste/Array bereits sortiert vorher kann man dann eher eine binäre Suche verwenden: https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

Diese Methode ist eine O-Operation (n log), Dabei steht n für die Anzahl der Elemente im Bereich.