Angenommen, Sie interessieren sich für eine Reihe unabhängiger zeitvariabler Werte, von denen jeder den aktuellen Zustand von etwas darstellt. Die Werte ändern sich bei keinem festen Zeitplan und neue Werte können nicht aus alten vorhergesagt werden. Um ein konkretes Beispiel zu nennen: Nehmen wir an, Sie haben eine Menge Aktien, und Sie sind daran interessiert, ihre Werte im Auge zu behalten, und Sie erhalten ein Update über eine einzelne Aktie, sobald ein Handel mit dieser Aktie getätigt wird. (Mein tatsächliches Problem ist nicht über Aktien, aber hoffentlich machen sie das, was ich verstehe, verständlicher.)
Sie sollten nicht nur den aktuellen Preis jeder Aktie wissen, sondern auch einen beliebigen Punkt in der Vergangenheit auswählen und einen "Schnappschuss" erhalten, der Ihnen den letzten Handelspreis für jede Aktie anzeigt zu dieser Zeit. Zum Beispiel sollten Sie in der Lage sein zu sagen "Was war der jüngste Wert von jeder Aktie, die ich am letzten Dienstag um 16:53 Uhr verfolgt habe?" und bekomme eine präzise Antwort effizient.
Ich kann mir drei Möglichkeiten vorstellen, aber ich bin nicht sehr glücklich mit ihnen.
1. Führen Sie ein Journal. Pflegen Sie eine Liste aller Geschäfte in der Reihenfolge der Zeitfolge. Das Update fügt nur der Liste hinzu, und die Abfrage ist ein linearer Scan rückwärts in der Zeit beginnend mit dem ersten Eintrag, dessen Zeitstempel auf oder vor dem angegebenen Zeitstempel liegt. Dies würde das Update zu einer konstanten Zeitoperation machen, aber Sie müssen möglicherweise das gesamte Journal scannen, um einen Wert für alle Trades zu finden, also Update ist O (1) und Snapshot ist O (u) wobei u die Gesamtzahl der Updates ist. Der erforderliche Speicher ist O (u) aus offensichtlichen Gründen.
2. Schreiben Sie Checkpoints. Pflegen Sie ein einzelnes Journal wie zuvor, aber statt jedes Eintrags, der nur den neuen Aktienkurs enthält, enthält das Update den aktuellen Preis (ab diesem Update) für jeden Stock. Dies ist billig zu berechnen: Da das letzte Update auch alle diese Informationen enthält, kopieren Sie es einfach mit Ausnahme der einen Aktie, deren Preis sich tatsächlich geändert hat. Jetzt kann Snapshot mit einer O (logu) -Operation durchgeführt werden (mithilfe der binären Suche im Journal, um den letzten Eintrag zu finden, der vor oder am angegebenen Zeitstempel liegt). Allerdings wird Update zu O (s), wobei s die Anzahl der Stocks im System ist und außerdem der gesamte erforderliche Speicher von O (u) in der ersten Strategie zu O (s * u) geht - beides Probleme, wenn beide s und du bist groß.
3. Getrennte Zeitschriften. Pflegen Sie für jeden Bestand ein eigenes Journal und schreiben Sie für jedes Lager in chronologischer Reihenfolge Aktualisierungen in sein eigenes Journal. Um einen Schnappschuss zu erstellen, gehen Sie über jedes Journal und verwenden Sie eine binäre Suche, um das richtige Update zu finden. Es benötigt O (u) Speicher, Update ist eine O (1) Operation und Snapshot kann in O (s * log u) Zeit erfolgen. Dies ist meine bevorzugte Methode der drei, aber ich denke, dass es wahrscheinlich verbessert werden könnte, da es keine Beziehung zwischen dem Zeitpunkt der Updates über verschiedene Aktien hinweg ignoriert.
Gibt es einen besseren Weg, den ich vermisse? Ist das ein Problem, das untersucht wurde und eine allgemein akzeptierte Lösung hat?
Sehen Sie sich die Literatur zu Persistente Datenstrukturen an. Insbesondere dieses frühe Papier beschreibt die Konstruktion eines dauerhaften binären Suchbaums, der unterhält logarithmische Operationen, kann aber in jeder Version (zB Zeitpunkt) aufgerufen werden. Zugriffe auf Teile der Struktur, die in einer bestimmten Version nicht aktualisiert wurden, sehen natürlich auf die letzte Vorgängerversion aus. Also hätten Sie Ihre natürlichen Operationen in O (log s) Zeit, und die Struktur könnte O (u) Raum belegen, wenn Sie alle Ihre Schlüssel im Voraus kennen und nie wieder ausbalancieren müssen, oder O (u * log s) Leerzeichen if Jedes Update hat O (log s) -Zeiger modifiziert.
Diese Klasse Notizen scheinen zu beschreiben, was Sie in ziemlich einfach implementieren müssen Begriffe.
Ich bezweifle, dass Sie eine Lösung finden, die in allen Maßen ausgezeichnet ist. Was Sie wählen, hängt weitgehend davon ab, welche Kompromisse Sie eingehen möchten. Wenn Snapshots selten sind, ist # 3 großartig; wenn sie häufig sind, wahrscheinlich nicht: O ( S log U ) könnte beispielsweise für ein Quellcodeverwaltungs-Repository ein Mörder sein.
Hier sind ein paar andere Ideen von oben:
4. Regelmäßige Prüfpunkte. In einem bestimmten Intervall (alle x Stunden, jede y Aktualisierungen, was auch immer) machen einen Prüfpunkt, der den aktuellen Preis für jeden Bestand enthält. Das Herausfinden der Daten zu einem vergangenen Zeitpunkt bedeutet, den aktuellsten Snapshot vor dieser Zeit zu finden und anschließend die einzelnen Updates hinzuzufügen. Dies hätte die gleiche asymptotische Leistung wie # 2, aber die Multiplikationskonstante für Updates und Speichernutzung wäre viel niedriger, da Sie viel weniger Snapshots aufnehmen würden.
5. Nur-Delta-Checkpoints. Wie # 4, aber keine Momentaufnahme des gesamten Systems. Speichern Sie stattdessen nur die Elemente, die sich seit dem letzten Prüfpunkt geändert haben. Die unveränderten Einträge werden an früheren Checkpoints nachgeschlagen. Dies spart beim Schreiben eines Checkpoints viel Zeit und reduziert die Speicherauslastung erheblich. Wenn Δ U die durchschnittliche Anzahl von Aktualisierungen zwischen Prüfpunkten ist, dann sind beide jetzt O (Δ U <). Dies wäre effektiv ein fester Betrag; Die Datenbank würde mit der Zeit wachsen, aber nicht die durchschnittliche Anzahl der Aktualisierungen pro Prüfpunkt. Sie könnten die Aktualisierungszeit als amortisierten O (1) und die Speichernutzung als O ( U ) betrachten, dann.
Was es wert ist, vor einigen Jahren habe ich einen Wiki-Klon geschrieben. Eines der Probleme, denen ich begegnete, war, wie man die Seitendeltas speichert. Speichere ich nur die Diffs oder speichere ich den vollständigen Seitentext bei jedem Update? Wie kann ich Geschwindigkeit und Speichernutzung ausgleichen? Das Anwenden von Dutzenden oder Hunderten von Diffs in einer Reihe, um eine Seite zu rekonstruieren, könnte zu langsam sein, aber das Speichern der gesamten Seite, wenn jemand nur einen Satz ändert, wäre ziemlich verschwenderisch.
Ich wollte etwas, das auch für große, häufig aktualisierte Seiten gut skaliert.
Ich endete mit einem hybriden Ansatz ähnlich wie # 5. Ich speichere Diffs mit periodischen Ganzseiten-Snapshots. Um herauszufinden, wann die Schnappschüsse erstellt werden, vergleiche ich den Text der neuen Seite mit dem Text des letzten Schnappschusses. Wenn die Diff-Größe mehr als halb so groß ist wie ein Ganzseiten-Text, speichere ich den ganzen Seitentext statt des Diff. Auf diese Weise kann ich, wenn die Leute kleine Updates machen, Diffs speichern, aber wenn sich die Seite einmal genug geändert hat, nehme ich einen neuen Snapshot.
Ich bezweifle, dass Sie eine Lösung finden, die in allen Maßen ausgezeichnet ist. Was Sie wählen, hängt weitgehend davon ab, welche Kompromisse Sie eingehen möchten. Wenn Snapshots selten sind, ist # 3 großartig; wenn sie häufig sind, wahrscheinlich nicht: O ( S log U ) könnte beispielsweise für ein Quellcodeverwaltungs-Repository ein Mörder sein.
Hier sind ein paar andere Ideen von oben:
4. Regelmäßige Prüfpunkte. In einem bestimmten Intervall (alle x Stunden, jede y Aktualisierungen, was auch immer) machen einen Prüfpunkt, der den aktuellen Preis für jeden Bestand enthält. Das Herausfinden der Daten zu einem vergangenen Zeitpunkt bedeutet, den aktuellsten Snapshot vor dieser Zeit zu finden und anschließend die einzelnen Updates hinzuzufügen. Dies hätte die gleiche asymptotische Leistung wie # 2, aber die Multiplikationskonstante für Updates und Speichernutzung wäre viel niedriger, da Sie viel weniger Snapshots aufnehmen würden.
5. Nur-Delta-Checkpoints. Wie # 4, aber keine Momentaufnahme des gesamten Systems. Speichern Sie stattdessen nur die Elemente, die sich seit dem letzten Prüfpunkt geändert haben. Die unveränderten Einträge werden an früheren Checkpoints nachgeschlagen. Dies spart beim Schreiben eines Checkpoints viel Zeit und reduziert die Speicherauslastung erheblich. Wenn Δ U die durchschnittliche Anzahl von Aktualisierungen zwischen Prüfpunkten ist, dann sind beide jetzt O (Δ U <). Dies wäre effektiv ein fester Betrag; Die Datenbank würde mit der Zeit wachsen, aber nicht die durchschnittliche Anzahl der Aktualisierungen pro Prüfpunkt. Sie könnten die Aktualisierungszeit als amortisierten O (1) und die Speichernutzung als O ( U ) betrachten, dann.
Was es wert ist, vor einigen Jahren habe ich einen Wiki-Klon geschrieben. Eines der Probleme, denen ich begegnete, war, wie man die Seitendeltas speichert. Speichere ich nur die Diffs oder speichere ich den vollständigen Seitentext bei jedem Update? Wie kann ich Geschwindigkeit und Speichernutzung ausgleichen? Das Anwenden von Dutzenden oder Hunderten von Diffs in einer Reihe, um eine Seite zu rekonstruieren, könnte zu langsam sein, aber das Speichern der gesamten Seite, wenn jemand nur einen Satz ändert, wäre ziemlich verschwenderisch.
Ich wollte etwas, das auch für große, häufig aktualisierte Seiten gut skaliert.
Ich endete mit einem hybriden Ansatz ähnlich wie # 5. Ich speichere Diffs mit periodischen Ganzseiten-Snapshots. Um herauszufinden, wann die Schnappschüsse erstellt werden, vergleiche ich den Text der neuen Seite mit dem Text des letzten Schnappschusses. Wenn die Diff-Größe mehr als halb so groß ist wie ein Ganzseiten-Text, speichere ich den ganzen Seitentext statt des Diff. Auf diese Weise kann ich, wenn die Leute kleine Updates machen, Diffs speichern, aber wenn sich die Seite einmal genug geändert hat, nehme ich einen neuen Snapshot.
Die Idee von persistenten Datenstrukturen, die von Novelocrat präsentiert wird, scheint die beste Lösung für den allgemeinen Fall zu sein. Ich nehme an, es wird in Ihrem Fall gut funktionieren.
Ich habe gerade an eine Variation von (2) gedacht. Verwalten Sie ein dynamisches Array, das nach Modifikationszeitstempeln geordnet ist. Jeder Eintrag entspricht einer Version und besteht aus einem Array von s Elementen. Anstatt alle Bestandsdatensätze pro Version zu speichern, tun Sie es lazilly; Wenn die Version erstellt wird, wird nur einem Lagerartikel, dessen Wert sich geändert hat, ein neuer Datensatz zugewiesen. Die anderen s-1-Elemente zeigen auf null.
Wenn Sie eine Suche nach der Zeit T und der Aktie S durchführen, sollten Sie die Versionen rückwärts beginnend mit der letzten vor der Zeit T linear absuchen. Der Scan wird fortgesetzt, bis Sie einen Wert ungleich Null für S finden alle Nullzeiger für S, die Sie auf Ihrem Weg gefunden haben, sodass die nächsten Abfragen effizient sind.
Diese Lösung bietet O (1) Additionszeit und eine amortisierte Abfragezeit von O (log u). Komplette Snapshot-Abfragen benötigen O (s + logu), was besser ist als die Implementierung (4). Der Raum ist immer noch O (u * s).
Die amortisierten Kosten von Abfragen ergeben sich aus der Tatsache, dass bei jeder Abfrage von Element S der Version V alle S-Werte der Versionen & lt; = V fest sind. Daher führt eine Folge von eindeutigen Abfragen zwei Besuche in den Arrays durch (unabhängig von ihrer Reihenfolge!), Was zu durchschnittlich zwei Abfragen pro Abfrage führt. Daher bleiben wir bei der anfänglichen Nachschlagezeit von O (log u).
Angenommen, Sie interessieren sich für eine Reihe unabhängiger zeitvariabler Werte, von denen jeder den aktuellen Zustand von etwas darstellt. Die Werte ändern sich bei keinem festen Zeitplan und neue Werte können nicht aus alten vorhergesagt werden. Um ein konkretes Beispiel zu nennen: Nehmen wir an, Sie haben eine Menge Aktien, und Sie sind daran interessiert, ihre Werte im Auge zu behalten, und Sie erhalten ein Update über eine einzelne Aktie, sobald ein Handel mit dieser Aktie getätigt wird. (Mein tatsächliches Problem ist nicht über Aktien, aber hoffentlich machen sie das, was ich verstehe, verständlicher.)
Sie sollten nicht nur den aktuellen Preis jeder Aktie wissen, sondern auch einen beliebigen Punkt in der Vergangenheit auswählen und einen "Schnappschuss" erhalten, der Ihnen den letzten Handelspreis für jede Aktie anzeigt zu dieser Zeit. Zum Beispiel sollten Sie in der Lage sein zu sagen "Was war der jüngste Wert von jeder Aktie, die ich am letzten Dienstag um 16:53 Uhr verfolgt habe?" und bekomme eine präzise Antwort effizient.
Ich kann mir drei Möglichkeiten vorstellen, aber ich bin nicht sehr glücklich mit ihnen.
1. Führen Sie ein Journal. Pflegen Sie eine Liste aller Geschäfte in der Reihenfolge der Zeitfolge. Das Update fügt nur der Liste hinzu, und die Abfrage ist ein linearer Scan rückwärts in der Zeit beginnend mit dem ersten Eintrag, dessen Zeitstempel auf oder vor dem angegebenen Zeitstempel liegt. Dies würde das Update zu einer konstanten Zeitoperation machen, aber Sie müssen möglicherweise das gesamte Journal scannen, um einen Wert für alle Trades zu finden, also Update ist O (1) und Snapshot ist O (u) wobei u die Gesamtzahl der Updates ist. Der erforderliche Speicher ist O (u) aus offensichtlichen Gründen.
2. Schreiben Sie Checkpoints. Pflegen Sie ein einzelnes Journal wie zuvor, aber statt jedes Eintrags, der nur den neuen Aktienkurs enthält, enthält das Update den aktuellen Preis (ab diesem Update) für jeden Stock. Dies ist billig zu berechnen: Da das letzte Update auch alle diese Informationen enthält, kopieren Sie es einfach mit Ausnahme der einen Aktie, deren Preis sich tatsächlich geändert hat. Jetzt kann Snapshot mit einer O (logu) -Operation durchgeführt werden (mithilfe der binären Suche im Journal, um den letzten Eintrag zu finden, der vor oder am angegebenen Zeitstempel liegt). Allerdings wird Update zu O (s), wobei s die Anzahl der Stocks im System ist und außerdem der gesamte erforderliche Speicher von O (u) in der ersten Strategie zu O (s * u) geht - beides Probleme, wenn beide s und du bist groß.
3. Getrennte Zeitschriften. Pflegen Sie für jeden Bestand ein eigenes Journal und schreiben Sie für jedes Lager in chronologischer Reihenfolge Aktualisierungen in sein eigenes Journal. Um einen Schnappschuss zu erstellen, gehen Sie über jedes Journal und verwenden Sie eine binäre Suche, um das richtige Update zu finden. Es benötigt O (u) Speicher, Update ist eine O (1) Operation und Snapshot kann in O (s * log u) Zeit erfolgen. Dies ist meine bevorzugte Methode der drei, aber ich denke, dass es wahrscheinlich verbessert werden könnte, da es keine Beziehung zwischen dem Zeitpunkt der Updates über verschiedene Aktien hinweg ignoriert.
Gibt es einen besseren Weg, den ich vermisse? Ist das ein Problem, das untersucht wurde und eine allgemein akzeptierte Lösung hat?
Sehen Sie sich die Literatur zu Persistente Datenstrukturen an. Insbesondere dieses frühe Papier beschreibt die Konstruktion eines dauerhaften binären Suchbaums, der unterhält logarithmische Operationen, kann aber in jeder Version (zB Zeitpunkt) aufgerufen werden. Zugriffe auf Teile der Struktur, die in einer bestimmten Version nicht aktualisiert wurden, sehen natürlich auf die letzte Vorgängerversion aus. Also hätten Sie Ihre natürlichen Operationen in O (log s) Zeit, und die Struktur könnte O (u) Raum belegen, wenn Sie alle Ihre Schlüssel im Voraus kennen und nie wieder ausbalancieren müssen, oder O (u * log s) Leerzeichen if Jedes Update hat O (log s) -Zeiger modifiziert.
Diese Klasse Notizen scheinen zu beschreiben, was Sie in ziemlich einfach implementieren müssen Begriffe.
Tags und Links algorithm