假设您对一堆独立的时变值感兴趣,每个值都代表某些事物的当前状态.这些值不会在任何固定的时间表上发生变化,并且无法从旧值中预测新值.为了一个具体的例子,假设您有一堆股票,并且您有兴趣跟踪它们的价值,并且只要对该股票进行交易,您就会获得有关个别股票的更新.(我的实际问题不是关于股票,而是希望他们能让我更容易理解.)
除了了解每只股票的当前价格之外,您还希望能够在过去选择一个任意点并获得一个"快照",告诉您当时每只股票的最新交易价格是多少.因此,举例来说,你应该可以说"我上周二下午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)时间内完成.这是我最喜欢的三种方法,但我觉得它可能会有所改进,因为它忽略了不同股票更新时间之间的任何关系.
有没有更好的方法让我失踪？这是一个已经研究过并且具有普遍接受的解决方案的问题吗？
algorithm ×1