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

Question

我意识到一个可调整大小的索引集合,它使用一个数组来存储它的元素(比如List<T>在.NET或ArrayListJava中),在集合的末尾分配了O(1)插入时间.但是在关键接合点处总是有一个令人讨厌的插入,其中集合刚刚达到其容量,并且下一次插入需要将内部阵列中的所有元素的完整副本转换为新的元素(可能是两倍大).

一个常见的错误(在我看来)是使用链表来"修复"这个问题; 但我相信为每个元素分配一个节点的开销可能非常浪费,事实上,在极少数情况下阵列插入成本很高的情况下,保证O(1)插入的好处相形见绌 - 事实上,其他每一个阵列插入明显更便宜(也更快).

我认为可能有意义的是一种混合方法,它由一个链接的数组列表组成,每当当前的"head"数组达到其容量时,一个两倍大的新数组被添加到链表中.然后,由于链表仍然具有原始数组,因此不需要复制.从本质上讲,这似乎与我相似(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).

如果你很好奇,我在我的个人网站上有一个这种结构的Java实现. 我不知道你会发现它有多么有用,但我们非常欢迎您试一试.

希望这可以帮助!

编辑:如果你想花一点时间阅读研究论文并试图实现一个相当复杂的数据结构,你可以在O(√n)空间开销中得到相同的结果(最坏情况下O(1)追加) (顺便说一句,这可以证明是最佳的)使用本文中的想法. 我从来没有真正实现这个,但如果内存是一个超级稀缺的资源,它肯定值得阅读.有趣的是,它使用上面的结构作为子程序!