为什么矢量数组加倍？

Question

为什么Vector(ArrayList for Java people)的经典实现在每次扩展时将其内部数组大小加倍,而不是将其增加三倍或四倍？

Answer 1

计算插入矢量的平均时间时,需要允许不增长的插入和不断增长的插入.

调用操作的总数插入ñ项目Ø _总,平均Ò _平均.

如果插入Ñ项,并且你的因数增长甲根据需要,则有ø _总 = N +ΣA ^我 [0 <I <1 + LN _甲 n]的运算.在最坏的情况下,您使用分配存储的1/A.

直观地说,A = 2意味着在最坏的情况你有ø _总 = 2,所以ö _平均是O(1),以及最坏的情况下使用该分配的存储的50%.

对于较大的一个,你有一个较低的Ô _总,更浪费了存储空间.

对于较小的一个,Ø _总较大,但你就不会浪费那么多的存储.只要它几何增长,它仍然是O(1)摊销的插入时间,但常数会变高.

对于生长因子1.25(红色),1.5(青色),2(黑色),3(蓝色)和4(绿色),这些图表显示了点和平均尺寸效率(尺寸/分配空间的比率;越多越好)插入400,000项的权利的左和时间效率(插入/操作的比率;越多越好).在调整大小之前,所有生长因子都达到了100%的空间效率; A = 2的情况表明时间效率在25%到50%之间,空间效率约为50%,这对大多数情况来说是好的:

对于Java等运行时,数组是零填充的,因此要分配的操作数与数组的大小成正比.考虑到这一点,可以减少时间效率估算之间的差异:

Answer 2

任何倍数都是一种妥协。如果它太大，就会浪费太多内存。如果它太小，您会浪费大量时间进行重新分配和复制。我想之所以存在加倍，是因为它有效并且很容易实现。我还看到了一个类似 STL 的专有库，它使用 1.5 作为相同的乘数 - 我猜它的开发人员认为加倍浪费了太多内存。