什么是最有效的数据结构存储的时间序列的部分改变阵列？

Question

我的问题是我有大小为N的对象的每一个时刻（t + 1）之后的阵列，一些数组的值的可能或可能不改变。因此，可以说T + 1个指数15层的变化，但一切保持不变。

什么是存储像这样（在存储器中）除了只具有当然数组的数组的最有效的方法是什么？我希望能够获得阵列中所有的值的任何时间，说的GetValues（长时间）的最有效的方式。

说4个阵列

1时 空值 空值 空值 XYZ

2时间 空值 空值 ABC XYZ

（请注意，只有农行在这里改变了），但我们仍然保持过去的指数值从时间1。

Answer 1

你所要求的在学术CS领域被称为“部分执着阵列”。有关持久性的更多信息，请参见卡普兰

一种简单的解决方案是使用搜索树，而不是阵列。您可以使用纯功能性的平衡搜索树，以保证每个读或写操作O（LG n）的最坏情况下的时间（其中n是数组的大小），而不是O（1）时间。 （如果保持在可延伸的阵列的时间标记的版本中，添加一个新的版本是O（1）摊销和访问的旧版本是O（1）的最坏情况。）

如果你不熟悉的纯粹功能查找树，你可能会读的此介绍Clojure的持久性阵列的。它们是纯粹的索引固定宽度的整数（在线索的形式）功能性树，并且因此具有固定深度。这可能是最快的解决您的问题，无论是最坏情况和现实世界的。

唯一的其他部分持久阵列，我知道的可能需要较长时间在最坏的情况下。一些有更好的摊销复杂并且一些好于预期的复杂性，如果阵列被以各种方式受限访问。