Com'è implementato l'elenco <T> .IndexOf() in C#?

Question

Stavo pensando all'andamento della chiamata allo List<T>.Indexof(item). Non sono sicuro che sarà una prestazione O (n) per un algoritmo sequenziale o prestazioni O (log (n)) per un albero binario ??

Answer 1

Utilizzando Riflettore per .NET possiamo vedere:

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

Dietro le quinte viene utilizzato un normale array, infatti il ​​metodo IndexOf chiama semplicemente Array.IndexOf. Poiché gli array non ordinano gli elementi, le prestazioni sono O (n).

Answer 3

E 'O(n) secondo i MSDN.

Questo metodo esegue una ricerca lineare; pertanto, questo metodo è un'operazione O (n), dove n è Count.

Answer 4

List<T> è supportato da un array piatto, quindi list.IndexOf(item) è O (n).

Answer 5

Se è necessario un rendimento più veloce, considerare HashSet<T>. È un compromesso tra velocità e memoria, ma ne vale la pena se si valuta il primo sul secondo.

(Non è esattamente la stessa di un List<T>, si comporta come un unico dizionario colonna, ma per i casi in cui si sta per avere una lista unica, è un modo per farlo.)

Answer 6

List<T>.IndexOf è O (n) che è in effetti ottimale per un insieme non ordinato di n elementi.

List<T>.BinarySearch è O (log n) ma funziona correttamente solo se l'elenco è ordinato.

Answer 7

Questa è una domanda vecchia, ma ho pensato che questo legame sarebbe stato interessante: Experiment: List internals and performance when adding new elements

Answer 8

La mia risposta in ritardo, ma penso che la pena ricordare che al giorno d'oggi è possibile accedere direttamente alle fonti MS: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

Non c'è più bisogno di riflessioni dal momento che il codice .NET BCL è ora disponibile online.

Implementa un elenco di dimensioni variabili che utilizza una serie di oggetti per memorizzare gli elementi . Un elenco ha una capacità, che corrisponde alla lunghezza allocata di dell'array interno. Quando gli elementi vengono aggiunti a un elenco, la capacità di l'Elenco viene aumentata automaticamente come richiesto riallocando l'array interno .

come implementata come un array ed esegue una ricerca lineare , si può facilmente dedurre che la complessità algoritmica del metodo IndexOf è O (n).

Come detto da altri le informazioni sono disponibili al pubblico su MSDN: https://msdn.microsoft.com/en-us/library/e4w08k17(v=vs.110).aspx

Questo metodo esegue una ricerca lineare; pertanto, questo metodo è un'operazione O (n) , dove n è Count.

Anche in questo caso, è possibile controllare le fonti e finiscono seing che il metodo di supporto statica IndexOf della classe Array è in realtà chiamato dietro le quinte:

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

Se l'elenco/array è già ordinato in anticipo è possibile allora piuttosto usare una ricerca binaria: https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

Questo metodo è un'operazione O (log n), dove n è il numero di elementi nell'intervallo.