C# HashSet <T> Suchleistung (im Vergleich zu einer ObservableCollection <T>)?

Question

C# das generische HashSet < T> Suchleistung sollte O (1), und die Suchleistung einer ObservableCollection < T> sollte O (n) sein wird.

ich eine große Menge an einzigartigen Elementen haben, hat jedes Element eine Datetime-Eigenschaft, die nicht eindeutig ist.

Jedes Element berechnet seine HashCode einfach durch seine Rückkehr DateTime.GetHashCode().

Jetzt möchte ich eine Teilmenge meiner Daten, z. alle Elemente, die ein Datum haben, die zwischen März 2012 und Juni 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; 

Wenn ich ausführen, um diese LINQ-Abfrage auf einer Sammlung von 300.000 Elementen ist, dauert es ca. 25 ms 80 Elemente zurück, die innerhalb des angegebenen Bereichs sind - Es spielt keine Rolle, ob ich ein HashSet < T> oder eine ObservableCollection < T> verwende.

Wenn ich Schleife durch alle Elemente manuell und überprüfen sie, es die gleiche Zeit in Anspruch nimmt, ~ 25 ms.

Aber ich tun, um die HashCode aller Daten kennen, die innerhalb des angegebenen Bereichs liegen. Ist es möglich, alle Elemente mit den gegebenen HashCodes von meinem HashSet < T> zu bekommen? Ich denke, das wäre viel schneller ...

Ist es möglich, die LINQ-Abfrage zu beschleunigen? Ich nehme an, dass es die speziellen Fähigkeiten meines HashSet < T> nicht nutzt?

Answer 1

Wie bereits erwähnt wurde, ist ein Hash-Satz sehr effizient, um zu bestimmen, ob ein bestimmter Hash im Satz ist. Ihre Abfrage verwendet nur die Tatsache, dass das Hashset IEnumerable implementiert, um über den gesamten Satz zu iterieren und den Datumsvergleich durchzuführen. Es wird die Hashes überhaupt nicht verwenden. Deshalb nimmt der manuelle Weg die gleiche Zeit in Anspruch wie die Abfrage.

Sie können kein Element basierend auf einem Hash von einem Hashset abrufen, Sie können nur auf die Existenz des Elements in der Menge testen. Ein Wörterbuch ist, was Sie wollen, wenn Sie es haben müssen (was Sie nicht scheint)

Entscheiden Sie, was Sie brauchen, um mit Ihren Daten zu tun und verwenden Sie eine Struktur, die dafür optimiert ist. Dies kann Ihre eigene Klasse sein, die mehrere interne Strukturen verwaltet, von denen jede in einer Sache effizient ist (wie eine für die Suche nach Bereichen und eine andere für die Überprüfung durch Existenz durch mehrere Felder), oder es kann eine existierende Struktur geben, die Ihren Bedürfnissen entspricht. Aber ohne zu wissen, was Sie mit Ihren Daten machen wollen, ist es schwer zu beraten.

Die andere Sache zu prüfen ist, ob Sie vorzeitig optimieren. Wenn 25ms für die manuelle Suche schnell genug sind, dann ist vielleicht jede Struktur, die IEnumerable implementiert, gut genug. In diesem Fall können Sie eines basierend auf den anderen Kriterien auswählen, die Sie benötigen.

Answer 2

Sie verwenden nicht die richtige Datenstruktur. Sie sollten so etwas wie eine sortierte Liste verwenden (sortiert nach der Date Eigenschaft), wo Sie dann binär nach Anfang und Ende des Bereichs suchen können.