C# HashSet <T> rendimiento de búsqueda (en comparación con un ObservableCollection <T>)?

Question

El C# el HashSet genérico < El rendimiento de búsqueda T> debe ser O (1), y el rendimiento de búsqueda de un ObservableCollection < T> debe ser O (n).

Tengo una gran cantidad de elementos únicos, cada elemento tiene una propiedad DateTime que no es única.

Cada elemento calcula su HashCode simplemente devolviendo su DateTime.GetHashCode().

Ahora quiero obtener un subconjunto de mis datos, p. todos los elementos que tienen una fecha que es entre marzo de 2012 y junio de 2012.

var result = from p in this.Elements 
       where p.Date >= new DateTime(2012, 03, 01) && 
         p.Date <= new DateTime(2012, 30, 06 
       select p; 

Si me quedo esta consulta LINQ en una colección de 300.000 elementos, se tarda unos 25 ms para volver 80 elementos que se encuentran dentro del rango dado - No importa si uso un HashSet < T> o un ObservableCollection < T>.

Si recorro todos los elementos manualmente y los reviso, tarda el mismo tiempo, ~ 25 ms.

Pero conozco el HashCode de todas las fechas que están dentro del rango dado. ¿Es posible obtener todos los elementos con los HashCodes dados desde mi HashSet < T>? Creo que eso sería mucho más rápido ...

¿Es posible acelerar la consulta LINQ? Supongo que no hace uso de las habilidades especiales de mi HashSet < T>?

Answer 1

Como se ha señalado, un conjunto de hash es muy eficiente para determinar si un hash determinado está en el conjunto. Su consulta solo utiliza el hecho de que el hashset implementa IEnumerable para iterar en todo el conjunto y hacer la comparación de fechas. No usará los hash en absoluto. Esta es la razón por la cual el modo manual toma el mismo tiempo que la consulta.

No se puede obtener un elemento basado en un hash de un hashset, solo se puede probar la existencia del elemento en el conjunto. Un diccionario es lo que desea si necesita obtenerlo (lo que parece que no es)

Decida qué es lo que necesita hacer con sus datos y use una estructura que esté optimizada para eso. Esta puede ser su propia clase que mantiene múltiples estructuras internas, cada una de las cuales es eficiente en una cosa (como una para buscar rangos y otra para verificar por existencia en múltiples campos), o puede haber una estructura existente que se ajuste a sus necesidades. Pero sin saber qué es lo que quieres hacer con tus datos es difícil de aconsejar.

La otra cosa a considerar es si está optimizando prematuramente. Si 25ms para buscar manualmente es lo suficientemente rápido, entonces tal vez cualquier estructura que implemente IEnumerable sea lo suficientemente buena. En ese caso, puede elegir uno según los otros criterios que necesite.

Answer 2

No está utilizando la estructura de datos correcta. Debería utilizar algo así como una lista ordenada (ordenada en la propiedad Date) donde puede realizar una búsqueda binaria para el principio y el final del rango.