假设您对一堆独立的时变值感兴趣，每个值都代表某事物的当前状态。这些值不会按任何固定的时间表更改，并且无法从旧值预测新值。举一个具体的例子，假设您有一堆股票，并且您有兴趣跟踪它们的价值，并且每当对该股票进行交易时，您都会获得有关该股票的更新。 （我的实际问题与股票无关，但希望它们能让我的意思更容易理解。）
除了只知道每只股票的当前价格之外，您还希望能够选择过去的任意点并获得“快照”，告诉您当时每只股票的最新交易价格是多少。例如，您应该能够说“截至上周二下午 4:53，我跟踪的每只股票的最新价值是多少？”并高效地得到准确的答案。
我可以想到三种方法来做到这一点，但我对其中任何一种都不太满意。
1. 写日记。按时间顺序维护所有交易的列表。更新只是添加到列表中，查询是从时间戳等于或早于指定时间戳的第一个条目开始向后线性扫描。这将使更新成为一个恒定时间操作，但您可能必须扫描整个日志才能找到所有交易的值，因此更新为 O(1)，快照为 O(u)，其中 u 是更新总数。出于显而易见的原因，所需的内存为 O(u)。
2. 编写检查点。像以前一样维护一个日记帐，但更新包含当前价格（截至该更新），而不是每个条目仅包含新股票价格every库存。这计算起来很便宜：由于最后一次更新也包含了所有这些信息，因此您只需将其全部复制，除了价格实际发生变化的一只股票之外。现在可以通过 O(log u) 操作来完成快照（在日志上使用二分搜索来定位指定时间戳之前或之后的最后一个条目）。然而，更新变成了 O(s)，其中 s 是系统中的股票数量，此外，所需的总内存从第一个策略中的 O(u) 变为 O(s*u)——如果s 和 u 都很大。
3.独立期刊。为每只股票维护一个单独的日记帐，并将每只股票的更新写入其自己的日记帐中，同样按时间顺序排列。要生成快照，请检查每个日志并使用二分搜索来查找正确的更新。它需要 O(u) 内存，更新是 O(1) 操作，快照可以在 O(s * log u) 时间内完成。这是这三种方法中我最喜欢的方法，但我觉得它可能还可以改进，因为它忽略了不同股票更新时间之间的任何关系。
我失踪了还有更好的方法吗？这是一个已经被研究过并有普遍接受的解决方案的问题吗？
看看相关文献持久数据结构。尤其，这篇早期论文 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.4630描述了维护对数运算的持久二叉搜索树的构造，但可以在任何版本（例如时间点）访问。对某些特定版本中未更新的结构部分的访问自然会查找最后一个先前版本。因此，您将在 O(log s) 时间内进行自然操作，并且如果您预先知道所有密钥并且无需重新平衡，则该结构可以占用 O(u) 空间，或者如果您知道 O(u * log s) 空间，每次更新都会修改 O(log s) 指针。
似乎用相当简单的术语描述了您需要实现的内容。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
