什么是dynamic分配数组的理想增长率？

C ++有std :: vector，Java有ArrayList，许多其他语言都有自己的dynamic分配数组forms。 当dynamic数组空间不足时，会将其重新分配到更大的区域，并将旧值复制到新数组中。 这种arrays的性能问题主要在于arrays的大小有多快。 如果你总是变得足够大，以适应当前的推动，那么你将最终每次重新分配。 因此，将数组大小加倍或将其乘以1.5倍是有意义的。

有一个理想的增长因素吗？ 2倍？ 1.5倍？ 理想的意思是math上合理的，最佳的平衡performance和浪费的记忆。 我意识到理论上，考虑到你的应用程序可能有任何潜在的推送分布，这是有些依赖于应用程序。 但是我很想知道是否有一个“通常”最好的价值，或者在一些严格的约束条件下被认为是最好的。

我听说有这方面的文章，但我一直无法find它。

Answer 1

这完全取决于用例。 你是否更关心浪费时间复制数据（并重新分配数组）或额外的内存？ arrays要持续多久？ 如果不会长期存在，那么使用更大的缓冲区可能是一个好主意 – 惩罚是短暂的。 如果它将会stream行起来（例如在Java中，进入老一代和老一代），那显然更多的是惩罚。

没有什么是“理想的增长因素”。 这不仅仅是理论上依赖于应用程序，而是绝对依赖于应用程序。

2是一个相当常见的增长因素 – 我敢肯定这就是.NET中的ArrayList和List<T>使用的。 Java中的ArrayList<T>使用1.5。

编辑：正如Erich指出的，.NET中的Dictionary<,>使用“大小加倍，然后增加到下一个素数”，以便散列值可以在桶之间合理分配。 （我相信我最近看到的文档暗示素数对散布散列桶并不是那么好，但这是另一个答案的论点。）

Answer 2

我记得很多年前，为什么1.5比2更好，至less应用于C ++（这可能不适用于运行时系统可以随意重定位对象的托pipe语言）。

推理是这样的：

1. 假设你从一个16字节的分配开始。
2. 当你需要更多的时候，你分配32个字节，然后释放16个字节。 这在内存中留下了一个16字节的漏洞。
3. 当你需要更多的时候，你分配64个字节，释放32个字节。 这留下了一个48个字节的洞（如果16和32是相邻的）。
4. 当你需要更多的时候，你分配128个字节，释放64个字节。 这留下了一个112字节的漏洞（假设所有以前的分配是相邻的）。
5. 等等等等。

这个想法是，在2倍扩展的情况下，没有时间点，所产生的空洞将会足够大，以便重新用于下一个分配。 使用1.5倍分配，我们有这个：

1. 从16个字节开始。
2. 当你需要更多的时候，分配24个字节，然后释放16个，留下一个16字节的漏洞。
3. 当你需要更多的时候，分配36个字节，然后释放24个字节，留下一个40字节的漏洞。
4. 当你需要更多的时候，分配54个字节，然后释放36个，留下76个字节的漏洞。
5. 当你需要更多的时候，分配81个字节，然后释放54个字节，留下一个130字节的漏洞。
6. 当你需要更多的时候，从130个字节的洞中使用122个字节（四舍五入）。

Answer 3

理想情况下（极限为n →∞）， 它是黄金比例 ：φ= 1.618 …

在实践中，你想要接近一些，比如1.5。

原因在上面的链接中解释 – 它涉及求解方程x ^{n – 1} = x ^{n + 1} – x ⁿ ，其正解是x =φ。

Answer 4

回答这样的问题时，一个方法就是“欺骗”，看看stream行的图书馆在做什么，假设一个广泛使用的图书馆至less不会做可怕的事情。

所以只要检查得非常快，Ruby（1.9.1-p129）在追加数组时使用1.5x，Python（2.6.2）使用1.125x加上一个常量:(在Objects / listobject.c中）：

 /* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* check for integer overflow */ if (new_allocated > PY_SIZE_MAX - newsize) { PyErr_NoMemory(); return -1; } else { new_allocated += newsize; } 

上面的newsize是数组中元素的个数。 注意， newsize被添加到new_allocated ，所以使用new_allocated和ternary运算符的expression式实际上只是计算过度分配。

Answer 5

假设你用x增长数组的大小。 所以假设你以大小T开始。 下一次你增长数组的大小将是T*x 。 那么它将是T*x^2等等。

如果您的目标是能够重新使用之前创build的内存，那么您要确保分配的新内存小于先前分配的内存的总和。 因此，我们有这样的不平等：

 T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2) 

我们可以从两边删除T. 所以我们得到这个：

 x^n <= 1 + x + x^2 + ... + x^(n-2) 

非正式地讲，我们所说的是，在nth分配时，我们希望先前的所有释放的内存大于或等于第n个分配的内存需求，以便我们可以重新使用先前释放的内存。

例如，如果我们想在第三步（即n=3 ）做到这一点，那么我们有

 x^3 <= 1 + x 

这个方程对于所有的x是成立的，使得0 < x <= 1.3 （粗略地）

看看我们得到什么样的不同的n的下面：

 n maximum-x (roughly) 3 1.3 4 1.4 5 1.53 6 1.57 7 1.59 22 1.61 

注意， x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2因为x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2生长因子必须小于x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2 。

Answer 6

这真的取决于。 有些人分析常见的用例来find最佳的数字。

我已经看到1.5x 2.0x phi x，以及之前使用的2次幂。

Answer 7

如果你有一个数组长度的分布，而且你有一个效用函数，说明你喜欢浪费空间和浪费时间，那么你肯定可以select一个最佳的resize（和初始大小）策略。

使用简单常数倍数的原因，显然是每个追加都有一个摊销常量。 但是，这并不意味着你不能在小尺寸上使用不同的（更大的）比例。

在Scala中，你可以用一个查看当前大小的函数来覆盖标准库哈希表的loadFactor。 奇怪的是，可resize的arrays只是双倍，这是大多数人在实践中所做的。

我不知道任何双倍（或1.5 *）的数组，实际上可以捕捉到内存错误，并在这种情况下减less。 看起来，如果你有一个巨大的单一arrays，你会想这样做。

我进一步补充说，如果你将可resize的数组保持足够长的时间，并且随着时间的推移你会倾向于使用空间，那么在开始时可能会大大超出（大多数情况下），然后重新分配到合适的大小完成。

Answer 8

我知道这是一个古老的问题，但有几件事情似乎每个人都失踪了。

首先，乘以2：size << 1.这是乘以1和2之间的任何东西 ：int（float（size）* x），其中x是数字，*是浮点math，处理器有在float和int之间运行额外的指令。 换句话说，在机器级别，加倍需要一个非常快速的指令来find新的大小。 乘以1和2之间的东西需要至less一条指令将大小转换为浮点数，一条乘法指令（这是浮点乘法，所以它可能至less需要两倍的周期，如果不是4倍甚至8倍） ，一条指令返回到int，假设你的平台可以在通用寄存器上执行浮点运算，而不需要使用特殊的寄存器。 简而言之，您应该期望每个分配的math计算至less需要十倍于简单的左移。 如果您在重新分配期间复制大量数据，这可能没有多大区别。

其次，可能是最大的踢球者：每个人似乎都假设正在被释放的内存既是连续的，也是与新分配的内存连续的。 除非你自己预先分配所有的内存，然后把它作为一个池，否则几乎肯定不是这样。 操作系统可能偶尔会这样做，但大多数情况下，将有足够的空间碎片，任何一半体面的内存pipe理系统将能够find一个你的内存将适合的小洞。 一旦你真的有点大块，你很可能会结束连续的片断，但到那时，你的分配是足够大的，你不会经常做足够的事情了。 简而言之，想象一下，使用理想的数字可以最有效地利用空闲的内存空间是很有趣的，但实际上，除非你的程序运行在裸机上，否则不会发生这种情况（因为没有OS在它下面作出所有的决定）。

我对这个问题的回答是？ 不，没有理想的数字。 这是特定应用程序，甚至没有人甚至尝试。 如果你的目标是理想的内存使用情况，那么你几乎不走运。 对于业绩来说，分配的频率越低越好，但如果我们这样做，我们可以乘以4甚至8！ 当然，当Firefox一次性跳过1GB到8GB的时候，人们会抱怨，所以甚至没有意义。 这里有一些经验法则，我会去：

如果你不能优化内存使用，至less不要浪费处理器周期。 乘以2至less比浮点运算快一个数量级。 它可能没有什么大的不同，但至less会有一些变化（特别是在更频繁和更小的分配期间）。

不要过度想办法。 如果你花了4个小时试图弄清楚如何去做已经完成的事情，那么你就浪费了时间。 说实话，如果有比* 2更好的select，几十年前就可以在C ++vector类（以及许多其他地方）中完成。

最后，如果你真的想优化，不要为了小事而stream汗。 现在，没有人关心浪费4KB的内存，除非他们在embedded式系统上工作。 当你达到1GB到1MB之间的每个1MB的对象时，加倍可能太多了（我的意思是说，在100到1000个对象之间）。 如果您可以估算预期的扩张速度，则可以在某个点上将其平稳增长至线性增长率。 如果您预计每分钟大约10个物体，那么每个步长（每30秒到一分钟一次）增长5到10个物体大小可能没有问题。

最重要的是，不要过多考虑，优化你的能力，并且如果你必须定制到你的应用程序（和平台）。

Answer 9

我同意Jon Skeet的观点，即使我的理论工匠朋友坚持认为当将因子设置为2x时，这可以被certificate是O（1）。

每台机器的CPU时间与内存的比例是不同的，因此这个因素也会变化很多。 如果你有一台内存为千兆字节的机器，而且CPU速度较慢，那么把这些元素拷贝到一个新的arrays上要比在一台快速的机器上花费要多得多，而这个机器可能会减less内存。 这是一个理论上可以回答的问题，一个统一的电脑，在真实的情况下，根本不帮你。

Answer 10

另外两分钱

• 大多数电脑都有虚拟内存！ 在物理内存中，随机页面可以随处显示为程序虚拟内存中的单个连续空间。 间接的解决是由硬件完成的。 虚拟内存耗尽在32位系统上是一个问题，但实际上不再是问题了。 所以填补这个洞不再是一个问题（除了特殊的环境）。 由于Windows 7甚至微软都支持64位而没有额外的努力。 @ 2011
• O（1）达到任何r > 1因素。 同样的mathcertificate不仅以2为参数起作用。
• r = 1.5可以用old*3/2 3/2来计算，所以不需要浮点运算。 （我说/2因为编译器会在生成的汇编代码中用位移代替它，如果他们认为合适的话）。
• MSVC的r = 1.5，所以至less有一个主要的编译器不使用2作为比例。

正如有人提到的2感觉比8好。而且2感觉比1.1好。

我的感觉是，1.5是一个很好的默认值。 除此之外，这取决于具体情况。