Dez*_*zue 5 time core-data time-series series data-structures
我的问题是我有一个大小为 N 的对象数组。每次 (t+1) 之后，数组的某些值可能会也可能不会改变。所以假设 t+1 索引 15 发生变化，但其他一切都保持不变。
除了当然只有一组数组之外，存储这样的东西（在内存中）的最有效方法是什么？我希望能够在任何时间以最有效的方式获取数组的所有值，比如 getValues(long time)。
说 4 个数组
时间 1 null null null xyz
时间 2 null null abc xyz
（注意这里只有 abc 发生了变化）但我们仍然保留了从时间 1 开始的最后一个索引的值。
您所要求的在学术 CS 领域被称为“部分持久数组”。有关持久性的更多信息，请参阅Kaplan 的调查。
一种简单的解决方案是使用搜索树而不是数组。您可以使用纯功能平衡搜索树来保证每次读取或写入在最坏情况下花费 O(lg n) 时间（其中 n 是数组的大小），而不是 O(1) 时间。（如果将带时间戳的版本保留在可扩展数组中，则添加新版本的时间复杂度为 O(1)，而访问旧版本的最坏情况为 O(1)。）
如果您不熟悉纯函数式搜索树，您可以阅读这篇关于 Clojure 持久数组的介绍。它们是纯功能树，索引固定宽度整数（以 trie 的形式），因此具有固定深度。这可能是解决您的问题的最快解决方案，无论是最坏的情况还是现实世界。
我所知道的唯一其他部分持久数组在最坏的情况下可能需要更长的时间。如果以各种受限方式访问数组，有些具有更好的摊销复杂性，有些则具有更好的预期复杂性。