IndexOf demasiado lento en la lista. Una solución más rápida?

Question

Tengo una lista genérica que debe ser un orden conservado para que pueda recuperar el índice de un objeto en la lista. El problema es que IndexOf es demasiado lento. Si comento el IndexOf out, el código se ejecuta rápido como puede ser. ¿Hay una manera mejor, como preservada ordenó la lista de hash para C#?

Gracias, Nate

• Editar - El orden en que se añaden los artículos/introducido es el orden que tiene que ser. No es necesario ordenarlos. También esta lista tiene el potencial de ser actualizada a menudo, agregar, eliminar, insertar. Básicamente, necesito traducir el objeto a un índice debido a que están representados en un control de cuadrícula para que pueda realizar operaciones en el control de la cuadrícula en función del índice.

Answer 1

Si no está ordenado, pero el pedido debe conservarse, entonces podría tener un Dictionary<YourClass, int> que contenga el índice para cada elemento.

Si desea una lista ordenada, luego verifique las publicaciones anteriores: puede usar SortedList<Tkey, TValue> en .Net 3.5, o ordenarla y usar BinarySearch en versiones anteriores de .Net.

[Editar] Puede encontrar ejemplos similares en la web, e.g .: OrderedList. Éste utiliza internamente una ArrayList y una HashTable, pero puede hacerla genérica fácilmente.

[Edit2] Ooops ... el ejemplo que te di no implementa IndexOf como describí al principio ... Pero entiendes el punto: una lista debe pedirse, la otra debe usarse para una búsqueda rápida.

Answer 2

Bueno, no hay razón para que tengas que pedir una lista hash ... ese es el punto. Sin embargo, una lista de hash debe hacer el truco con bastante facilidad.

Answer 3

Quizás esté buscando SortedList<TKey, TValue>?

Answer 4

Ordenar usando List<T>.Sort, a continuación, utilizar el List<T>.BinarySearch método: "Busca la totalidad ordenada List(T) para un elemento de [...] Este método es una O (log n) operación, donde n es el número de elementos en el distancia."

Answer 5

Si está utilizando la clase List, puede usar el método Sort para ordenarla una vez que se haya rellenado inicialmente, luego use el Método BinarySearch para encontrar el elemento apropiado.

Answer 6

Sugiero usar la clase SortedList<TKey, TValue> o SortedDictionary<TKey, TValue> si necesita los artículos ordenados. Las diferencias son las siguientes.

• SortedList<TKey, TValue> utiliza menos memoria que SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> tiene operaciones más rápidas de inserción y extracción para datos no ordenados: O (log n) en contraposición a O (n) para SortedList<TKey, TValue>.

• Si la lista se llena a la vez de datos ordenados, SortedList<TKey, TValue> es más rápido que SortedDictionary<TKey, TValue>.

Si lo que desea es preservar el orden, sólo se puede utilizar un Dictionary<TKey, TValue> y almacenar el elemento como clave y el índice como valor. El inconveniente es que reordenar los elementos, inserciones o eliminación son bastante caros de hacer.

Answer 7

No estoy seguro acerca de los detalles en C#, pero es posible que pueda ordenarlo (QuickSort?) Y luego usar una búsqueda binaria (el rendimiento de BinarySearch es O (log2 (N)), frente a Sequential, tal como indexOf, que es O (n)). (IMPORTANTE: para una búsqueda binaria, su estructura debe ordenarse)

Cuando inserta elementos en su estructura de datos, puede intentar una búsqueda binaria modificada para encontrar también el punto de inserción, o si está agregando un grupo grande , deberías agregarlos y luego ordenarlos.

El único problema es que la inserción será más lenta.

Answer 8

Si el orden de los objetos en la lista tiene para preservar, entonces la única manera que puedo pensar de dónde obtendrá el acceso más rápido posible es decirle al objeto cuál es su posición de índice cuando se se agregó etc. a la lista. De esta manera puede consultar el objeto para obtener su índice en la lista. La desventaja, y es un gran inconveniente en mi opinión, es que los objetos insertados ahora tienen una dependencia en la lista.

Answer 9

Ver la parte inferior de this article here.

Parece que escribir su propio método para recuperar el índice es mucho más rápido que usar el método IndexOf, debido a que llama a un método virtual según el tipo.

Algo así puede por tanto mejorar tu rendimiento. Escribí una prueba de unidad pequeña para verificar que esto mejora el rendimiento de la búsqueda, y lo hizo, alrededor de 15 veces en una lista con 10.000 elementos.

static int GetIndex(IList<Item> list, Item value) 
{ 
    for (int index = 0; index < list.Count; index++) 
    { 
     if (list[index] == value) 
     { 
      return index; 
     } 
    } 
    return -1; 
}