algorithm - 用于更新值和查询过去某个时间值状态的数据结构

Question

假设您对一堆独立的时变值感兴趣，每个值都代表某事物的当前状态。这些值不会按任何固定的时间表更改，并且无法根据旧值预测新值。举一个具体的例子，假设您有一堆股票，并且有兴趣跟踪它们的值(value)，并且每当对某只股票进行交易时，您都会获得有关该股票的更新。 (我的实际问题不在于股票，但希望它们能让我的意思更容易理解。)

除了只知道每只股票的当前价格外，您还希望能够选择过去的任意点并获得“快照”，告诉您每只股票的最近交易价格是多少当时。因此，例如，您应该能够说“截至上周二下午 4:53，我跟踪的每只股票的最新值(value)是多少？”并高效地得到准确的答案。

我可以想到三种方法来做到这一点，但我对其中任何一种都不是很满意。

<强>1。记日记。按时间顺序维护所有交易的列表。更新只是添加到列表中，查询是从时间戳等于或早于指定时间戳的第一个条目开始的时间向后线性扫描。这将使更新成为一个恒定时间的操作，但您可能必须扫描整个日志才能找到所有交易的值，因此更新是 O(1)，快照是 O(u)，其中 u 是更新总数。由于显而易见的原因，所需内存为 O(u)。

<强>2。编写检查点。像以前一样维护一个日志，但不是每个条目只包含新的股票价格，更新包含每股票的当前价格(截至该更新)。计算起来很容易:因为上次更新也包含所有这些信息，所以除了价格实际发生变化的一只股票之外，你只需复制所有信息。现在快照可以通过 O(log u) 操作完成(在日志上使用二进制搜索来定位指定时间戳之前或之上的最后一个条目)。然而，更新变为 O(s)，其中 s 是系统中的股票数量，而且所需的总内存从第一个策略中的 O(u) 变为 O(s*u) ---如果s 和 u 都很大。

<强>3。独立的期刊。为每只股票维护一个单独的日志，并将每只股票的更新写入其自己的日志，再次按时间顺序排列。要快照，请查看每个日志并使用二进制搜索来查找正确的更新。它需要 O(u) 内存，Update 是一个 O(1) 操作，Snapshot 可以在 O(s * log u) 时间内完成。这是三种方法中我最喜欢的方法，但我觉得它可能会得到改进，因为它忽略了不同股票的更新时间之间的任何关系。

有没有更好的方法我想念？这是一个已经研究过并有普遍接受的解决方案的问题吗？

Answer 1

查看关于持久数据结构的文献。特别是，this early paper描述了维持对数运算但可以在任何版本(例如时间点)访问的持久二叉搜索树的构造。对某些特定版本中未更新的结构部分的访问自然会查看上一个先前版本。因此，您将在 O(log s) 时间内进行自然操作，如果您预先知道所有 key 并且永远不必重新平衡，则该结构可能占用 O(u) 空间，或者 O(u * log s) 空间，如果每次更新修改 O(log s) 指针。

These class notes似乎用相当简单的术语描述了您需要实现的内容。