logo标签列表

为什么向量数组会被加倍？

algorithmdata-structuresvectorarraylist
20

为什么经典的向量实现（Java人使用的ArrayList）在每次扩展时将其内部数组大小加倍，而不是三倍或四倍？

你可能会想，为什么不乘以1.5? 或者1.8等等呢？（你可以乘以1.5然后四舍五入到下一个最大的整数，比如说。） - Peter
7个回答
21

计算向量插入的平均时间时，需要考虑非扩展插入和扩展插入。

将插入n项的总操作数称为ototal，平均值为oaverage。

如果插入n项，并根据需要增长A倍，则有 ototal = n + ΣAi [ 0 < i < 1 + lnAn ]个操作。在最坏情况下，你使用了分配存储的1/A。

直观地说，A=2表示最坏情况下有ototal=2n，因此oaverage是O(1)，并且最坏情况下使用了50%的已分配存储。

对于更大的A，你拥有更低的ototal，但浪费的存储空间更多。

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

对于增长因子为1.25（红色）、1.5（青色）、2（黑色）、3（蓝色）和4（绿色）的情况，这些图表显示了在插入400,000项时左侧的点和平均大小效率（大小/分配空间比率；数字越大表示更好），右侧的时间效率（插入操作/总操作比率；数字越大表示更好）。所有增长因子在重新调整大小之前都达到了100%的空间效率；对于A=2的情况，时间效率在25%至50%之间，空间效率约为50%，这对于大多数情况而言是不错的：

空间和时间效率图-C语言实现

对于像Java这样的运行时环境，数组是零填充的，因此分配操作的数量与数组大小成正比。考虑到这一点可以减少时间效率估计之间的差异：

空间和时间效率图-Java实现类似

1
我赞同你的答案，但建议检查一下当集合中的每个项在几乎达到扩展所需级别时会移动多少次。以增长因子k为例，只有1/k的项会移动至少一次，1/k^2会至少移动两次，1/k^3会移动三次等等，因此在'n'次扩展中，每个数据项平均移动的次数将是1/k+1/k^2+1/k^3+...1/k^n，这是一个有界的几何级数。 - supercat
看起来作为答案附带的图片现在变成了imageshack的广告。你还有它们吗？ - CCovey
5

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

4
指数级地将数组（或字符串）的大小加倍是在拥有足够的数组单元和浪费过多内存之间取得平衡的好方法。
假设我们从10个元素开始：
1 - 10 2 - 20 3 - 40 4 - 80 5 - 160
当我们将大小增加三倍时，增长速度太快了：
1 - 10 2 - 30 3 - 90 4 - 270 5 - 810
在实践中，您可能会增长10或12次。如果您将其增加三倍，则可能只需要增长7或8次。重新分配的运行时间开销这么少，不值得担心，但您更有可能完全超出所需的大小。
1
好的，但是你可以争论说向量可以扩展到一个更多的元素，或者扩展一半的元素。 这样做有什么特别的原因吗？ - TheOne
1
当你倍增时，你保证最多浪费你想要使用的内存量。指数增长的目的是为了在接近目标大小时不必增长。 - Igor Zevaka
3
实际上，需求可以保证事情的实现。如果您的要求是从文件中处理输入，每个文件包含50条记录，那么您可以在开始读取文件之前添加50个新元素，例如......除此之外，这所有的都是在内存和性能之间的权衡。您需要确保始终有足够的空间而无需复制吗？还是您需要更小的内存占用并且可以承担复制的成本呢？ - Thomas Owens
@Ramin：不添加一个元素的原因是，如果只添加一个元素，则添加N个元素将需要与N^2成比例的时间，因为您每次都需要调整大小。使用指数增长，它需要与N成比例的时间。 - Steve Jessop
太对了。我已经把我的数学工作外包给计算机太久了 :) - Igor Zevaka
显示剩余3条评论
3
如果你分配了一个非常规大小的内存块，那么当该块被释放（因为你正在调整其大小或它被垃圾回收）时，内存中会有一个非常规大小的空洞，这可能会给内存管理器带来麻烦。因此，通常最好将内存分配为2的幂次方。在某些情况下，底层内存管理器只会给你一些特定大小的块，如果你请求一个奇怪的大小，它会向上取整到下一个较大的大小。因此，与其请求470个单位，最终得到512个单位，然后在使用完所有470个单位后再调整大小，不如一开始就请求512个单位。
我不同意这个答案。我不确定它是否回答了“为什么不用3、4或5的增长率”的问题。它回答了一个稍微不同的问题（为什么要在2的幂边界上分配内存？）。 - Jeremy Powell
1
这绝对不是我会选择的答案。我认为它更像是一个补充性的答案。除了其他解释增长率的原因之外，如果新数组不是2的幂次方，你就浪费了资源。所以考虑到其他关于更大乘数不好的论点，唯一适合的幂次方是2。当然，这假设初始大小也是2的幂次方，但我认为大多数向量类都会尽力安排这样做。 - kwatford
没错，“不同意”可能有点过了 :) 另外，你肯定可以设计一个算法，让你的增长大约为1.5，同时确保你的字对齐。如果一个字节数组长度为64个字节，你肯定可以添加32个字节并仍然保持字对齐。 - Jeremy Powell
2
在Java或C#中，元素数量为2的幂次方的数组将是一个带有头和长度的对象，因此内存管理器的最差尺寸是2的幂次方再加上几个字节。如果malloc使用头文件，对于C或C++也是如此。 - Pete Kirkham
2
如果你询问的是Vector和ArrayList的Java特定实现，那么它不一定会在每次扩展时都翻倍。
从Vector的Javadoc中可以看到：
每个向量都尝试通过维护容量和capacityIncrement来优化存储管理。容量始终至少与向量大小相同；通常情况下，容量更大，因为当组件添加到向量时，向量的存储以容量增量大小的块增加。应用程序可以在插入大量组件之前增加向量的容量；这减少了递增的重新分配量。
Vector的一个构造函数允许您指定Vector的初始大小和容量增量。Vector类还提供了ensureCapacity（int minCapacity）和setSize（int newSize），用于手动调整Vector的最小大小并自行调整Vector的大小。
ArrayList类非常相似：
每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终至少与列表大小一样大。当元素被添加到ArrayList中时，其容量会自动增长。增长策略的具体细节未指定，除了添加元素具有恒定的摊销时间成本之外。
应用程序可以在使用ensureCapacity操作添加大量元素之前增加ArrayList实例的容量。这可能会减少递增重新分配的数量。
如果您询问向量的一般实现方式，那么增加大小和增加多少是一种权衡。通常，向量由数组支持。数组是固定大小的。要调整向量大小因为它已满意味着您必须将数组的所有元素复制到一个新的、更大的数组中。如果您的新数组太大，那么您就分配了永远不会使用的内存。如果太小，从旧数组复制元素到新的、更大的数组可能需要太长时间，这是您不想经常执行的操作。
2

个人认为这是任意选择。我们可以使用自然对数e作为底数，而不是2的底数（不是加倍，而是将大小乘以(1+e)。）

如果您要向向量添加大量变量，则具有高基数将是有利的（以减少您将要复制的数量）。另一方面，如果您只需要存储平均数很少的成员，则较低的基数就可以了，并减少开销，从而加快速度。

二进制是一种折中方案。

-1

在大 O 性能方面，将数量翻倍、三倍或四倍没有性能上的区别。然而，在绝对值方面，翻倍通常在正常情况下更节省空间。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接