C# HashSet <T> prestazioni di ricerca (rispetto a ObservableCollection <T>)?

Question

Il C# il generico HashSet < T> prestazioni di ricerca dovrebbe essere O (1), e le prestazioni di ricerca di una ObservableCollection < T> dovrebbe essere O (n).

Ho una grande quantità di elementi unici, ogni elemento ha una proprietà DateTime che non è univoca.

Ogni elemento calcola il proprio HashCode semplicemente restituendo il suo DateTime.GetHashCode().

Ora voglio ottenere un sottoinsieme dei miei dati, ad es. tutti gli elementi che hanno una data che si trova tra marzo 2012 e giugno 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; 

Se corro questa query LINQ su una collezione di 300.000 elementi, ci vuole ~ 25 ms per tornare 80 elementi che si trovano all'interno della gamma data - Non importa se utilizzo un HashSet < T> o ObservableCollection < T>.

Se faccio scorrere tutti gli elementi manualmente e li controllo, richiede lo stesso tempo, ~ 25 ms.

Ma conosco il codice hash di tutte le date che rientrano nell'intervallo specificato. È possibile ottenere tutti gli elementi con gli HashCode forniti dal mio HashSet < T>? Penso che sarebbe molto più veloce ...

È possibile velocizzare la query LINQ? Suppongo che non sfrutti le abilità speciali del mio HashSet < T>?

Answer 1

Come è stato sottolineato, un set di hash è molto efficiente nel determinare se un determinato hash è nell'insieme. La tua query utilizza semplicemente il fatto che l'hashset implementa IEnumerable per iterare sull'intero insieme e fare il confronto della data. Non userà affatto gli hash. Questo è il motivo per cui la modalità manuale ha lo stesso tempo della query.

Non è possibile ottenere un elemento basato su un hash da un hashset, è possibile solo verificare l'esistenza dell'elemento nel set. Un dizionario è quello che vuoi se hai bisogno di ottenerlo (che sembra che tu non lo sia)

Decidi cosa devi fare con i tuoi dati e usa una struttura che sia ottimizzata per quello. Questa potrebbe essere la tua classe che mantiene più strutture interne ognuna delle quali è efficiente in una cosa (come una per la ricerca di intervalli e un'altra per la verifica dell'esistenza di più campi), oppure potrebbe esserci una struttura esistente che si adatta alle tue esigenze. Ma senza sapere cosa vuoi fare con i tuoi dati è difficile da consigliare.

L'altra cosa da considerare è se si sta ottimizzando prematuramente. Se 25 ms per la ricerca manuale è abbastanza veloce allora forse qualsiasi struttura che implementa IEnumerable sarà abbastanza buono. Nel qual caso puoi sceglierne uno in base agli altri criteri di cui hai bisogno.

Answer 2

Non stai utilizzando la giusta struttura dati. Dovresti usare qualcosa come una lista ordinata (ordinata sulla proprietà Date) dove puoi quindi effettuare una ricerca binaria per l'inizio e la fine dell'intervallo.