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

list find c#

Question

Tengo 60k elementos que deben verificarse en una lista de búsqueda de 20k. ¿Hay algún objeto de recopilación (como List , HashTable ) que proporcione un método de Contains() excepcionalmente rápido? ¿O tendré que escribir el mío? En otras palabras, ¿el método predeterminado de Contains() escanea cada elemento o usa 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

¿Has considerado List.BinarySearch(item) ?

¿Dijo que su gran colección ya está ordenada, por lo 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 2

Debes leer este blog que probó varios tipos diferentes de colecciones y métodos para cada uno con técnicas de subprocesamiento único y de subprocesos múltiples.

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

Al usar una colección que permite "claves", Dictionary, ConcurrentDictionary, Hashset y HashTables tuvieron el mejor rendimiento general.

Answer 3

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

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

Answer 4

Mantenga ambas listas xey en orden ordenado.

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), tamaño (y))

No ejecute un bucle .Contains (), esto es proporcional a x * y que es mucho peor.

Answer 5

Si es posible ordenar sus artículos, entonces hay una forma mucho más rápida de hacer esto 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, solo se trata 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 no está preocupado por hacer sonar cada último bit de rendimiento, la sugerencia de utilizar un HashSet o una búsqueda 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 esta es solo una de miles de veces que hará esto y el rendimiento es crítico (y ha demostrado ser inaceptable utilizando HashSet / búsqueda binaria), ciertamente podría escribir su propio algoritmo que recorrió las listas ordenadas haciendo comparaciones a medida que avanzaba. 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 7

Si no necesita ordenar, intente HashSet<Record> (nuevo en .Net 3.5)

Si lo hace, use un List<Record> y llame a BinarySearch .

Answer 8

Si usa .Net 3.5, puede crear un código más limpio usando:

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

No tengo .Net 3.5 aquí y esto no está 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 que LookupCollection es un HashSet