findindex - list indexof c#

¿Cómo se implementa List<T>.IndexOf() en C#?

Question

Estaba pensando en el rendimiento de llamar a List<T>.Indexof(item) . No estoy seguro si será un rendimiento O (n) para un algoritmo secuencial o el rendimiento O (log (n)) para un árbol binario?

Answer 1

Detrás de las escenas se usa una array regular, de hecho el método IndexOf simplemente llama a Array.IndexOf . Como las matrices no clasifican los elementos, el rendimiento es O (n).

Answer 2

Es O(n) según MSDN .

Este método realiza una búsqueda lineal; por lo tanto, este método es una operación O (n), donde n es Count.

Answer 3

Si necesita un ejecutante más rápido, considere HashSet<T> . Es una compensación de velocidad vs. memoria, pero vale la pena si valoras el primero sobre el segundo.

(No es exactamente lo mismo que una List<T> , se comporta como un diccionario de una sola columna, pero para casos en los que va a tener una lista única, es una forma de hacerlo).

Answer 4

Usando Reflector para .NET podemos ver:

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 5

List<T>.IndexOf es O (n) que, de hecho, es óptima para un conjunto desordenado de n elementos.

List<T>.BinarySearch es O (log n) pero solo funciona correctamente si la lista está ordenada.

Answer 6

List<T> está respaldado por una matriz plana, por lo que list.IndexOf(item) es O (n).

Answer 7

Esta es una vieja pregunta, pero pensé que este enlace sería interesante: Experimento: enumerar las funciones internas y el rendimiento al agregar nuevos elementos

Answer 8

Mi última respuesta, pero creo que vale la pena mencionar que hoy en día se puede acceder directamente a las fuentes de MS: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

No más necesidad de reflexión ya que el código .NET BCL ahora está disponible en línea.

Implementa una lista de tamaño variable que usa una matriz de objetos para almacenar los elementos. Una lista tiene una capacidad, que es la longitud asignada de la matriz interna. A medida que los elementos se agregan a una lista, la capacidad de la lista aumenta automáticamente según sea necesario reasignando la matriz interna.

Implementado como una matriz y realizando una búsqueda lineal , puede deducir fácilmente que la complejidad algorítmica del método IndexOf es O (n) .

Como mencionaron otros, la información está disponible públicamente en el msdn: https://msdn.microsoft.com/en-us/library/e4w08k17(v=vs.110).aspx

Este método realiza una búsqueda lineal; por lo tanto, este método es una operación O (n), donde n es Count.

De nuevo, puede verificar las fuentes y terminar viendo que el método estático auxiliar IndexOf de la clase Array se llama realmente detrás de escena:

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

Si la lista / matriz ya está ordenada de antemano, puede utilizar una búsqueda binaria: https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

Este método es una operación O (log n), donde n es el número de elementos en el rango.