Angenommen, Sie interessieren sich für eine Reihe unabhängiger, zeitlich variierender Werte, von denen jeder den aktuellen Status von etwas darstellt. Die Werte ändern sich nicht nach einem festen Zeitplan und neue Werte können nicht aus alten vorhergesagt werden. Nehmen wir als konkretes Beispiel an, Sie haben eine Reihe von Aktien und möchten deren Werte verfolgen. Sie erhalten ein Update über eine einzelne Aktie, wenn ein Handel mit dieser Aktie durchgeführt wird. (Bei meinem eigentlichen Problem geht es nicht um Aktien, aber hoffentlich machen sie das, was ich erhalte, verständlicher.)

Sie möchten nicht nur den aktuellen Kurs jeder Aktie kennen, sondern auch einen beliebigen Punkt in der Vergangenheit auswählen und einen "Schnappschuss" erhalten, aus dem hervorgeht, zu welchem Zeitpunkt der letzte Handelspreis für jede Aktie lag Zeit. So sollten Sie beispielsweise sagen können: "Was war der letzte Wert jeder Aktie, die ich letzten Dienstag um 16:53 Uhr nachverfolge?" und erhalten Sie eine präzise Antwort effizient.

Ich kann mir drei Möglichkeiten vorstellen, um dies zu tun, aber ich bin mit keiner von ihnen sehr zufrieden.

1. Führen Sie ein Tagebuch. Führen Sie eine Liste aller Geschäfte in zeitlicher Reihenfolge. Die Aktualisierung wird lediglich zur Liste hinzugefügt, und die Abfrage beginnt mit dem ersten Eintrag, dessen Zeitstempel auf oder vor dem angegebenen Zeitstempel liegt. Dies würde die Aktualisierung zu einer konstanten Zeitoperation machen, aber Sie müssen möglicherweise das gesamte Journal durchsuchen, um einen Wert für alle Trades zu finden. Update ist also O (1) und Snapshot ist O (u), wobei u die Gesamtzahl der Aktualisierungen ist. Erforderlicher Speicher ist aus offensichtlichen Gründen O (u).

2. Schreibe Checkpoints. Führen Sie wie bisher ein einzelnes Journal, aber anstelle jedes Eintrags, der nur den neuen Aktienkurs enthält, enthält das Update den aktuellen Preis (ab diesem Update) fürjede Lager. Dies ist günstig zu berechnen: Da das letzte Update auch alle diese Informationen enthält, kopieren Sie sie einfach vollständig, mit Ausnahme der einen Aktie, deren Preis sich tatsächlich geändert hat. Jetzt kann die Momentaufnahme mit einer O-Operation (log u) ausgeführt werden (mithilfe der binären Suche im Journal wird der letzte Eintrag gesucht, der vor oder nach dem angegebenen Zeitstempel eingeht). Update wird jedoch zu O (s), wobei s die Anzahl der Bestände im System ist, und außerdem geht der gesamte erforderliche Speicher von O (u) in der ersten Strategie zu O (s * u) - beides sind Probleme, wenn beide s und u sind groß.

3. Getrennte Zeitschriften. Pflegen Sie für jeden Bestand ein separates Journal und schreiben Sie Aktualisierungen für jeden Bestand in ein eigenes Journal, wiederum in chronologischer Reihenfolge. Um einen Schnappschuss zu erstellen, durchsuchen Sie jedes Journal und verwenden Sie eine binäre Suche, um das richtige Update zu finden. Es erfordert O (u) -Speicher, Update ist eine O (1) -Operation und Snapshot kann in O (s * log u) -Zeit ausgeführt werden. Dies ist meine Lieblingsmethode der drei, aber ich bin der Meinung, dass sie möglicherweise verbessert werden könnte, da sie jede Beziehung zwischen dem Zeitpunkt der Aktualisierung für verschiedene Bestände ignorier

Gibt es einen besseren Weg, den ich vermisse? Ist das ein Problem, das untersucht wurde und eine allgemein akzeptierte Lösung hat?