假设您对一堆独立的时变值感兴趣,每个值都代表某些事物的当前状态.这些值不会在任何固定的时间表上发生变化,并且无法从旧值中预测新值.为了一个具体的例子,假设您有一堆股票,并且您有兴趣跟踪它们的价值,并且只要对该股票进行交易,您就会获得有关个别股票的更新.(我的实际问题不是关于股票,而是希望他们能让我更容易理解.)
除了了解每只股票的当前价格之外,您还希望能够在过去选择一个任意点并获得一个"快照",告诉您当时每只股票的最新交易价格是多少.因此,举例来说,你应该可以说"我上周二下午4点53分跟踪的每股股票的最近价值是多少？" 并有效地得到准确的答案.
我可以想到三种方法,但我对它们中的任何一种都不满意.
1.记日记.按时间顺序维护所有交易的清单.更新只是添加到列表中,并且查询是向后的线性扫描,从时间戳开启或早于指定时间戳的第一个条目开始.这将使更新成为一个恒定时间操作,但您可能必须扫描整个日志以查找所有交易的值,因此Update为O(1),Snapshot为O(u),其中u是更新总数.由于显而易见的原因,所需的内存是O(u).
2.写检查点. 像以前一样维护单个日记帐,但更新包含每个股票的当前价格(截至该更新),而不是每个条目仅包含新股票价格.计算起来很便宜:由于上次更新也包含所有这些信息,因此除了价格实际发生变化的股票外,您只需将其全部复制.现在可以使用O(log u)操作完成快照(使用日志上的二进制搜索来查找指定时间戳之前或之后的最后一个条目).然而,更新变为O(s),其中s是系统中的股票数量,此外,所需的总内存从第一个策略中的O(u)变为O(s*u)---两者都是问题,如果你和你都很大.
3.分开的期刊. 为每个股票维护一个单独的期刊,并按时间顺序将每个股票的更新写入其自己的期刊.要快照,请检查每个日记并使用二进制搜索来查找正确的更新.它需要O(u)内存,Update是O(1)操作,快照可以在O(s*log u)时间内完成.这是我最喜欢的三种方法,但我觉得它可能会有所改进,因为它忽略了不同股票更新时间之间的任何关系.
有没有更好的方法让我失踪？这是一个已经研究过并且具有普遍接受的解决方案的问题吗？
我怀疑您是否会找到一个在所有方面都表现出色的解决方案。您的选择很大程度上取决于您愿意做出哪些权衡。如果快照不频繁，#3 就很好；如果它们很频繁，则可能不会：例如， O( S log U ) 可能是源代码控制存储库的杀手。
以下是我的一些其他想法：
4. 定期检查点。以指定的时间间隔（每x小时，每y更新，等等）创建一个包含每只股票当前价格的检查点。找出过去某个时间点的数据意味着找到该时间之前的最新快照，然后添加之后的各个更新。这将具有与 #2 相同的渐近性能，但更新和内存使用的乘法常数会低很多，因为您拍摄的快照会少得多。
5. 仅限达美航空的检查站。与 #4 相同，但不要拍摄整个系统的快照。相反，仅存储自上一个检查点以来已更改的项目。未更改的条目将在之前的检查点中查找。这在编写检查点时节省了大量时间，并大大减少了内存使用。如果 Δ U是检查点之间的平均更新次数，那么这两个现在都是 O(Δ U )。这实际上是一个固定金额；数据库会随着时间的推移而增长，但每个检查点的平均更新次数不会增长。那么，您可以将更新时间视为摊销 O(1)，将内存使用视为 O( U )。
无论如何，几年前我写了一个 wiki 克隆版。我遇到的问题之一是如何存储页面增量。我是只存储差异，还是每次更新时都存储整页文本？如何平衡速度与内存使用？连续应用数十或数百个差异来重建页面可能会非常慢，但如果有人只更改一个句子，则存储整个页面将非常浪费。
我想要的东西即使对于大型、频繁更新的页面也能很好地扩展。
我最终采用了类似于#5 的混合方法。我使用定期全页快照存储差异。为了确定何时拍摄快照，我将新页面文本与最新快照的文本进行比较。如果差异大小超过整页文本的一半，我将存储整页文本而不是差异。这样，如果人们进行小的更新，那么我可以存储差异，但最终一旦页面发生足够的变化，我将拍摄新的快照。