19

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

4

7 回答 7

21

在计算插入向量的平均时间时，您需要考虑非增长插入和增长插入。

调用操作总数来插入n项o总计，平均o平均值。

如果您插入n 个项目，并按要求增长A倍，则有o total = n + ΣA i [ 0 < i < 1 + ln A n ]操作。在最坏的情况下，您使用1/A分配的存储空间。

直观地说，A = 2意味着在最坏的情况下你有o total = 2n，所以o平均值是 O(1)，最坏的情况是你使用了 50% 的分配存储空间。

对于较大的 A，您的o total会降低，但会浪费更多的存储空间。

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

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

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

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

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

于 2009-09-15T09:12:20.650 回答
5

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

于 2009-09-15T05:58:39.107 回答
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 次 - 重新分配的运行时命中是这几次足够小，可以担心，但你更有可能完全超过所需的大小。

于 2009-09-15T02:27:43.680 回答
3

如果您要分配一个不寻常大小的内存块，那么当该块被释放时（因为您正在调整它的大小或它被 GC'd），内存中会出现一个不寻常大小的洞，这可能会导致头痛内存管理器。因此，通常首选以 2 的幂次方分配内存。在某些情况下，底层内存管理器只会给你特定大小的块，如果你请求一个奇怪的大小，它会四舍五入到下一个更大的大小。因此，与其要求 470 个单位，还是要取回 512 个，然后在用完所有要求的 470 个单位后再次调整大小，不如只要求 512 个开始。

于 2009-09-15T02:51:41.627 回答
2

如果您询问的是 Java 特定的Vector和ArrayList实现，那么它不一定在每次扩展时加倍。

来自 Vector 的 Javadoc：

每个向量都试图通过维护 acapacity和 a 来优化存储管理capacityIncrement。容量总是至少与向量大小一样大；它通常更大，因为随着组件被添加到向量中，向量的存储以块的大小增加capacityIncrement. 应用程序可以在插入大量组件之前增加向量的容量；这减少了增量重新分配的数量。

Vector 的构造函数之一允许您指定 Vector 的初始大小和容量增量。Vector 类还提供ensureCapacity(int minCapacity)和setSize(int newSize)，用于手动调整 Vector 的最小大小并自行调整 Vector 的大小。

ArrayList 类非常相似：

每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它总是至少与列表大小一样大。随着元素被添加到 ArrayList，它的容量会自动增长。除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有指定增长策略的细节。

应用程序可以在ArrayList使用 ensureCapacity 操作添加大量元素之前增加实例的容量。这可以减少增量重新分配的数量。

如果您要询问向量的一般实现，那么选择增加大小和增加多少是一种权衡。通常，向量由数组支持。数组是固定大小的。调整向量的大小，因为它已满意味着您必须将数组的所有元素复制到一个新的更大的数组中。如果您使新数组太大，那么您分配的内存将永远不会使用。如果它太小，则将旧数组中的元素复制到新的更大的数组中可能需要很长时间 - 您不希望经常执行此操作。

于 2009-09-15T02:38:20.727 回答
2

就个人而言，我认为这是一个随意的选择。我们可以使用基数 e 而不是基数 2（而不是将倍数大小加倍 (1+e)。）

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

Base 2 是一种折衷方案。

于 2009-09-15T05:50:44.910 回答
-1

没有将性能提高一倍、三倍或四倍的原因，因为它们都具有相同的大 O 性能配置文件。然而，在正常情况下，绝对值加倍往往会更节省空间。

于 2009-09-15T02:42:39.173 回答