arrays - 支持 O(1) 随机访问和最坏情况 O(1) 附加的数据结构？

Question

我意识到一个可调整大小的索引集合使用数组来存储其元素(例如 .NET 中的 List<T> 或 Java 中的 ArrayList)有 amortized O(1) insertion time在集合的最后。但是，在关键时刻总会出现一次令人讨厌的插入，即集合刚刚达到其容量，并且下一次插入需要将内部数组中的所有元素完整复制到一个新的(大概是两倍大)。

(在我看来)一个常见的错误是使用链表来“解决”这个问题；但我相信为每个元素分配一个节点的开销可能非常浪费，事实上，在数组插入成本高昂的罕见情况下，保证 O(1) 插入的好处实际上会相形见绌——事实上，每个 < em>其他数组插入要便宜得多(而且更快)。

我认为可能有意义的是一种由数组链接列表组成的混合方法，每次当前“头”数组达到其容量时，都会将两倍大的新数组添加到链接列表中。那么就不需要复制，因为链表仍然具有原始数组。本质上(对我来说)这似乎类似于 List<T>或ArrayList方法，除了之前在任何地方都会产生复制内部数组所有元素的成本，而在这里，您只需要分配一个新数组加上单个节点插入的成本。

当然，如果需要的话，这会使其他功能变得复杂(例如，在集合中间插入/删除)；但正如我在标题中所表达的，我实际上只是在寻找一个仅添加(和迭代)集合。

是否有任何数据结构非常适合此目的？或者，你自己能想到一个吗？

Answer 1

有一种称为可扩展数组的美丽结构，它具有最坏情况 O(1) 插入和 O(n) 内存开销(也就是说，它与动态数组渐近可比，但最坏情况为 O(1)插入)。诀窍是采用向量使用的方法——加倍和复制——但要让复制变得懒惰。例如，假设您有一个包含四个元素的数组，如下所示:

[1] [2] [3] [4]

如果你想添加一个新数字，比如 5，你首先要分配一个两倍大的数组:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

接下来，将 5 插入到新数组中:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

最后，将旧数组中的 4 拉到新数组中:

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

从现在开始，每次执行插入操作时，都将元素添加到新数组中，并从旧数组中再拉出一个元素。例如，添加 6 后，我们会得到

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

再插入两个值后，我们会得到这里:

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

如果我们现在需要再添加一个元素，我们会丢弃现在为空的旧数组，并分配一个两倍于当前数组的数组(能够容纳 16 个元素):

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

并重复此过程。扣除内存分配的成本(通常与数组大小呈次线性)，每次插入最多执行 O(1) 工作。

查找仍然是 O(1)，因为您只需决定要查找两个数组中的哪一个，而由于混排，中间的插入是 O(n)。

如果你好奇，我有 a Java implementation of this structure on my personal site.我不知道您会发现它有多大用处，但非常欢迎您尝试一下。

如果您想花一些时间阅读研究论文并尝试实现相当复杂的数据结构，您可以在 O(√n) 空间中获得相同的结果(最坏情况 O(1) 追加)使用 the ideas in this paper. 的开销(顺便说一句，这被证明是最佳的)我从未抽出时间来实际实现这一点，但如果内存是一种 super 稀缺的资源，那么它肯定值得一读。有趣的是，它使用上面的构造作为子例程!