beste Datenstruktur für sortierte Zeitreihendaten, die Sub-Arrays schnell zurückgeben können?

Question

Ich brauche eine Datenstruktur, die im Grunde eine Liste von Datenpunkten ist, wobei jeder Datenpunkt einen Zeitstempel und einen doppelten [] Datenwert hat. Ich möchte in der Lage sein, den nächsten Punkt zu einem bestimmten Zeitstempel oder zu allen Punkten innerhalb eines angegebenen Bereichs von Zeitstempeln abzurufen.

Ich benutze C#. Ich dachte, eine reguläre Liste wäre möglich, wobei "Datenpunkt" eine Klasse ist, die die Zeitstempel und doppelte [] Felder enthält. Dann, um einzufügen, würde ich die integrierte binarysearch() verwenden, um zu finden, wo die neuen Daten eingefügt werden, und ich könnte es wieder verwenden, um die Start-/Ende-Indizes für eine Bereichssuche zu finden.

Ich habe zuerst Sortedlists versucht, aber es scheint, als ob Sie nicht durch die Indizes i = 0,1,2, ..., n, nur durch Tasten durchlaufen können, so war ich nicht sicher, wie die Reichweitensuche zu tun ohne irgendeine gewundene Funktion.

aber dann habe ich gelernt, dass die Liste <> 's einfügen() ist o (n) ... könnte ich nicht besser als das, ohne woanders zu opfern?

alternativ, gibt es eine nette linq-anfrage, die alles in einer Zeile erledigt?

Answer 1

Wenn Sie bereit sind, nicht-BCL-Bibliotheken zu verwenden, hat die C5.SortedArray<T> immer ganz gut für mich gearbeitet.

Es hat eine großartige Methode, RangeFromTo, die ziemlich gut mit dieser Art von Problem funktioniert.

Answer 2

Sie haben die Wahl zwischen Kosten für die Einsetz-, Abruf- oder Entfernungszeit. Für jeden dieser Fälle sind verschiedene Datenstrukturen optimiert. Bevor Sie sich für einen entscheiden, würde ich die Gesamtgröße Ihrer Strukturen schätzen, wie viele Datenpunkte generiert werden (und mit welcher Häufigkeit) und welche häufiger verwendet werden: Einfügen oder Abrufen.

Wenn Sie viele neue Datenpunkte mit hoher Frequenz einfügen, würde ich vorschlagen, eine LinkedList <> zu suchen. Wenn Sie häufiger abrufen, würde ich eine Liste <> verwenden, obwohl die Einfügezeit langsamer ist.

Natürlich könnten Sie dies in einer LINQ-Abfrage tun, aber denken Sie daran, dies ist nur Zuckerguss: Die Abfrage wird jedes Mal und für jede Ausführung die gesamte Reihe von Datenpunkten suchen, um eine Übereinstimmung zu finden. Dies kann teurer sein, als die richtige Sammlung für den Job überhaupt zu verwenden.

Answer 3

Wie wäre es mit einer tatsächlichen Datenbank, um Ihre Daten zu speichern und Abfragen dagegen auszuführen? Dann könnten Sie LINQ-to-SQL verwenden.

Answer 4

Wenn Sie nur statische Daten haben, dann sollte jede Struktur, die IList implementiert, in Ordnung sein. Sortieren Sie es einmal und stellen Sie dann Abfragen mit BinarySearch. Dies sollte auch funktionieren, wenn Ihre eingefügten Zeitstempel immer zunehmen, dann können Sie einfach List.Add() in O (1) ausführen und es wird immer noch sortiert.

List<int> x = new List<int>(); 
    x.Add(5); 
    x.Add(7); 
    x.Add(3); 

    x.Sort(); 

    //want to find all elements between 4 and 6 
    int rangeStart = x.BinarySearch(4); 

    //since there is no element equal to 4, we'll get the binary complement of an index, where 4 could have possibly been found 
    //see MSDN for List<T>.BinarySearch 
    if (rangeStart < 0) 
     rangeStart = ~rangeStart; 

    while (x[rangeStart] < 6) 
    { 
     //do you business 
     rangeStart++; 
    } 

Wenn Sie an beliebigen Stellen auf Einsatzdaten müssen in Ihrer Struktur, halten sie sortiert und in der Lage sein, Bereiche schnell abzufragen, müssen Sie eine Struktur namens B+ tree. Es ist nicht im Framework implementiert, Sie müssen es irgendwo selbst finden.

einen Datensatz einfügen erfordert O (log n) Operationen im schlimmsten Fall

einen Datensatz zu finden erfordert O (log n) Operationen im schlimmsten Fall

a (vorher entfernt) Entfernen Satz benötigt O (log n) -Operationen im schlechtesten Fall

Die Ausführung einer Bereichsabfrage mit k Elementen innerhalb des Bereichs erfordert im schlimmsten Fall O ((log n) + k) Operationen.

P.S. „gibt es einige nette Linq-Abfrage, die alles, was ich möchte in einer einzigen Zeile tun“

Ich wünsche ich eine so schöne Linq-Abfrage wusste, dass alles tun, könnte ich in einer Linie wollen :-)