Qué colección .NET proporciona la búsqueda más rápida

Question

Tengo 60k elementos que deben verificarse en una lista de búsqueda de 20k. ¿Existe un objeto de recopilación (como List, HashTable) que proporcione un método excepcionalmente rápido Contains()? ¿O tendré que escribir el mío? En otras palabras, el método predeterminado Contains() es escanear cada elemento o utiliza un mejor algoritmo de búsqueda.

foreach (Record item in LargeCollection) 
{ 
    if (LookupCollection.Contains(item.Key)) 
    { 
     // Do something 
    } 
} 

Nota. La lista de búsqueda ya está ordenada.

Answer 1

En el caso más general, considere System.Collections.Generic.HashSet como su estructura de datos predeterminada "contiene" caballo de batalla, porque lleva un tiempo constante evaluar Contains.

La respuesta real a "¿Cuál es la recopilación más rápida de búsqueda?" Depende de su tamaño de datos específico, orden, frecuencia de búsqueda y frecuencia de búsqueda.

Answer 2

Si no es necesario ordenar, tratar HashSet<Record> (nuevo en .NET 3.5)

Si no, utiliza un List<Record> y llamar BinarySearch.

Answer 3

¿Has considerado List.BinarySearch(item)?

Dijiste que tu gran colección ya está ordenada, así que esta parece ser la oportunidad perfecta. Un hash definitivamente sería el más rápido, pero esto genera sus propios problemas y requiere mucho más sobrecarga para el almacenamiento.

Answer 4

Si no está preocupado por hacer sonar cada último bit de rendimiento, la sugerencia de utilizar una búsqueda HashSet o binaria es sólida. Sus conjuntos de datos simplemente no son lo suficientemente grandes como para que esto sea un problema el 99% del tiempo.

Pero si esto es solo una de miles de veces que lo hará y el rendimiento es crítico (y se ha demostrado que es inaceptable utilizando HashSet/búsqueda binaria), podría escribir su propio algoritmo que recorrió las listas ordenadas haciendo comparaciones como fuiste Cada lista se caminó a lo sumo una vez y en los casos patológicos no sería malo (una vez que seguiste esta ruta probablemente encontrarás que la comparación, suponiendo que es una cadena u otro valor no integral, sería el gasto real y esa optimización sería el siguiente paso).

Answer 5

Si es posible ordenar sus artículos, hay una forma mucho más rápida de hacerlo y luego realizar búsquedas de teclas en una tabla hash o b-tree. Aunque si tus objetos no son ordenables, no puedes ponerlos en un b-tree de todos modos.

De todos modos, si se pueden ordenar ambas listas, es solo cuestión de recorrer la lista de búsqueda en orden.

Walk lookup list 
    While items in check list <= lookup list item 
    if check list item = lookup list item do something 
    Move to next lookup list item 

Answer 6

Si está utilizando .Net 3.5, puede hacer que el código más limpio usando:

foreach (Record item in LookupCollection.Intersect(LargeCollection)) 
{ 
    //dostuff 
} 

no tengo Net 3.5 aquí y lo que esto no se ha probado. Se basa en un método de extensión. No es que LookupCollection.Intersect(LargeCollection) probablemente no sea lo mismo que LargeCollection.Intersect(LookupCollection) ... este último es probablemente mucho más lento.

Esto supone LookupCollection es un HashSet

Answer 7

mantener ambas listas X e Y en el orden establecido.

Si x = y, realice su acción, si x < y, avance x, si y < x, avance y hasta que cualquier lista esté vacía.

El tiempo de ejecución de esta intersección es proporcional a min (tamaño (x), el tamaño (y))

¿No ejecutar un bucle .Contains(), esta es proporcional a x * y que es mucho peor

Answer 8

Debe leer this blog que la velocidad probó varios tipos diferentes de colecciones y métodos para cada uno que utiliza técnicas de subprocesamiento único y de subprocesos múltiples.

De acuerdo con los resultados, un BinarySearch en una lista y SortedList fueron los mejores ejecutores constantemente corriendo cuello en cuello al buscar algo como un "valor".

Al utilizar una colección que permite "claves", Dictionary, ConcurrentDictionary, Hashset y HashTables obtuvieron el mejor resultado general.