为什么矢量数组加倍？ [英] Why is vector array doubled?

问题描述

为什么Vector（ArrayList for Java人）的经典实现在每个扩展上加倍其内部数组大小，而不是三倍或四倍？

Why does the classic implementation of Vector (ArrayList for Java people) double its internal array size on each expansion instead of tripling or quadrupling it?

推荐答案

在计算插入向量的平均时间时，您需要允许不增长的插入和不断增长的插入。

When calculating the average time to insert into a vector, you need to allow for the non-growing inserts and the growing inserts.

调用总数

Call the total number of operations to insert n items o_total, and the average o_average.

如果您插入 n 项目，并且根据需要以 A 的因子增长，那么有 o _total = n +Σ A ⁱ [0 < i< 1 + ln 操作。在最坏的情况下，您使用已分配存储的 1 / A 。

If you insert n items, and you grow by a factor of A as required, then there are o_total = n + ΣAⁱ [ 0 < i < 1 + ln_An ] operations. In the worst case you use 1/A of the allocated storage.

直观地， A = 2 最坏的是你有 o _total = 2n ，所以 o _average 是O（1），最糟糕的情况是你使用分配的存储空间的50％。

Intuitively, A = 2 means at worst you have o_total = 2n, so o_average is O(1), and the worst case you use 50% of the allocated storage.

对于较大的 A ，您有较低的 o _total ，但存储空间更多。

For a larger A, you have a lower o_total, but more wasted storage.

对于较小的 A ， o _total 较大，但您不会浪费太多的存储空间。只要它几何增长，它仍然是O（1）的摊销插入时间，但常数会变高。

For a smaller A, o_total is larger, but you don't waste so much storage. As long as it grows geometrically, it's still O(1) amortised insertion time, but the constant will get higher.

对于生长因子1.25（红色），1.5（青色），2（黑色），3（蓝色）和4（绿色），这些图显示了左边的点和平均尺寸效率（大小/分配空间的比例越多越好）和时间效率（插入/操作的比例）更多更好）在插入40万项目的权利。在调整大小之前，所有生长因子达到100％的空间效率; A = 2 的情况显示时间效率在25％至50％之间，空间效率约为50％，这对大多数情况是有利的：

For growth factors 1.25 ( red ), 1.5 ( cyan ), 2 ( black ), 3 ( blue ) and 4 ( green ), these graphs show point and average size efficiency ( ratio of size/allocated space; more is better ) on the left and time efficiency ( ratio of insertions / operations; more is better ) on the right for inserting 400,000 items. 100% space efficiency is reached for all growth factors just prior to resizing; the case for A = 2 shows time efficiency between 25% and 50%, and space efficiency about 50%, which is good for most cases:

对于运行时（如Java），数组为零填充，因此要分配的操作数与数组的大小成比例。考虑到这一点，减少了时间效率估计之间的差异：

For runtimes such as Java, arrays are zero filled, so the number of operations to allocate is proportional to the size of the array. Taking account of this gives reduces the difference between the time efficiency estimates:

这篇关于为什么矢量数组加倍？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！