Filtern einer Untergruppe von (potentiell) 1.000.000+ Artikeln

Question

Ich habe eine große dataset mit möglicherweise über einer Million Einträge. Alle Elemente haben einen zugewiesenen Zeitstempel und Elemente werden zur Laufzeit zur Gruppe hinzugefügt (normalerweise, aber nicht immer, mit einem neueren Zeitstempel). Ich muss eine Untermenge dieser Daten in einem bestimmten Zeitbereich anzeigen. Dieser Zeitbereich ist üblicherweise ziemlich klein im Vergleich zu dem Gesamtdatensatz, d. H. Von den 1.000.000+ Elementen, die nicht mehr als etwa 1000 sind, in diesem gegebenen Zeitbereich. Dieser Zeitbereich bewegt sich mit einer konstanten Geschwindigkeit, z. jede Sekunde wird der Zeitbereich um eine Sekunde verschoben. Zusätzlich kann der Benutzer den Zeitbereich jederzeit anpassen (durch den Datensatz "bewegen") oder zusätzliche Filter einstellen (z. B. nach Text filtern).

Bis jetzt war ich nicht besorgt über die Leistung, versuchte, die anderen Dinge richtig zu machen, und arbeitete nur mit kleineren Test-Sets. Ich bin mir nicht sicher, wie ich dieses Problem effizient angehen kann und würde mich über jeden Input freuen. Vielen Dank.

Edit: Gebrauchte Sprache ist C# 4.

Update: Ich bin jetzt ein Intervallbaum verwendet wird, kann die Umsetzung hier: https://github.com/mbuchetics/RangeTree

Es kommt auch mit einer asynchronen Version, die den Baum neu erstellt mit die Task Parallel Library (TPL).

Answer 1

Neue Artikel in eine sortierte Liste einfügen. Auf diese Weise können Sie einen Bereich ziemlich einfach auswählen. Sie können möglicherweise auch linq verwenden, wenn Sie damit vertraut sind.

Answer 2

Verwenden Sie SortedList sortiert nach Zeitstempel.

Alles, was Sie tun müssen, ist eine binäre Suche auf die sortierten Schlüssel in der sortierten Liste zu implementieren, um die Grenze Ihrer Auswahl zu finden, die ziemlich einfach ist.

Answer 3

Wir hatten ein ähnliches Problem in unserer Entwicklung - musste mehrere Millionen Artikel nach einem Schlüssel sortiert sammeln und dann eine Seite auf Abruf daraus exportieren. Ich sehe, dass dein Problem irgendwie ähnlich ist.

Zu diesem Zweck haben wir an die red-black tree Struktur, auf folgende Weise:

• wir den Iterator zu ihm hinzugefügt werden, so könnten wir 'next' Artikel in o (1)
• wir bekommen hinzugefügt der Iterator aus dem 'Index' zu finden, und schaffte es zu tun, dass in O (log n)

RB Tree O (log n) Einsetzen Komplexität hat, also denke ich, dass Ihr Einfügungen schön dort passen.

next() auf dem Iterator wurde durch Hinzufügen und Verwalten der verknüpften Liste aller Blattknoten implementiert - unsere ursprüngliche angenommene RB Tree Implementierung enthielt dies nicht.

RB Tree ist auch cool, weil es Ihnen ermöglicht, die Knotengröße nach Ihren Bedürfnissen zu optimieren. Durch das Experimentieren werden Sie in der Lage sein, richtige Zahlen zu finden, die genau zu Ihrem Problem passen.