动态分配数组的理想增长率是多少？

StackOverflow https://stackoverflow.com/questions/1100311

题

C++ 有 std::vector，Java 有 ArrayList，许多其他语言都有自己的动态分配数组形式。当动态数组空间不足时，它会被重新分配到更大的区域，并将旧值复制到新数组中。影响此类阵列性能的一个核心问题是阵列大小增长的速度有多快。如果你总是只增长到足以适应当前的推动，那么你最终每次都会重新分配。因此，将数组大小加倍或乘以 1.5 倍是有意义的。

有理想的生长因子吗？2x？1.5倍？我所说的理想是指数学上合理的、最佳的平衡性能和浪费的内存。我意识到，从理论上讲，考虑到您的应用程序可能具有任何潜在的推送分布，这在某种程度上取决于应用程序。但我很想知道是否有一个值“通常”是最好的，或者在某些严格的约束下被认为是最好的。

我听说某处有一篇关于此的论文，但我找不到它。

有帮助吗？

解决方案

这将完全取决于使用情况。你更在乎浪费的时间数据拷贝（并重新分配阵列）或额外的内存？阵列多久会持续下去？如果它不会是周围长，使用更大的缓冲也不失为一个好主意 - 刑罚是短命的。如果它要流连（例如在Java中，进入老了几岁）这显然更是一个点球的。

有没有这样的事情作为一个“理想的生长因子。”这不只是理论上的应用相关的，它的绝对的应用相关的。

2是一个很常见的生长因子 - 我敢肯定，这就是ArrayList和List<T>在.NET使用。 ArrayList<T>在Java使用1.5。

编辑：由于埃里希所指出的，在Dictionary<,> .NET使用“双尺寸然后增加至下一个质数”，使散列值可以合理桶之间进行分配。 （我敢肯定，我最近看到的文档表明素数实际上并没有分发散列桶很大，但那是另一种答案的理由。）

其他提示

我记得我读很多年前为什么1.5是首选的两个，至少因为适用C++(这可能不适用于托管语言，其运行系统可以搬迁对象在会)。

其理由是这样的：

  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-byte孔。
  5. 当你需要更多，分配81字节，然后免费了54,留下一个130字节的洞。
  6. 当你需要更多的，使用的122个字节(四舍五入)从130字节的洞。

理想情况下（在极限为名词→∞），它的黄金比例 ：在φ= 1.618 ...

在实践中，你想要的东西密切，像1.5。

原因是，你希望能够重复使用旧的内存块，采取缓存的优势，避免不断地使OS给你更多的内存页面。方程式你解决，以确保这降低到 X 名词 - 1 - 1 = X 名词 + 1 - X 名词 ，其溶液接近 X =φ为大名词的

回答此类问题的一种方法是“作弊”，看看流行的库做了什么，假设广泛使用的库至少不会做一些可怕的事情。

因此，只需快速检查一下，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, ，所以带有位移位和三元运算符的表达式实际上只是计算过度分配。

让我们假设你通过x增长数组的大小。所以，假设你开始与大小T。下一次你成长的数组的大小将T*x。然后，它会被T*x^2等。

如果你的目标是能够重新使用之前已经建立的内存，那么你要确保你分配新的内存小于以前的记忆，你释放的总和。因此，我们有这个不等式：

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个分配大于或等于内存需求，使我们可以重新使用先前释放的内存。

例如，如果我们希望能够在第3步骤，以执行此操作（即，n=3），那么我们有

x^3 <= 1 + x

此方程是对于所有的x真使得0 < x <= 1.3（粗略地）

看看x我们得到不同的n是下面：

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

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

这实际上取决于。有人分析常见的使用情况，以找到最佳的数量。

我看到1.5倍2.0倍披x和2的幂之前使用。

如果你有超过数组的长度分布，和你有一个效用函数，说你喜欢多大的浪费空间与浪费时间，那么你可以毫不犹豫地选择最佳的调整大小（与初始大小）的策略。

究其原因，简单的常数倍时，显然是使每一个追加已分期常量时间。但是，这并不意味着不能使用不同的（较大的）比对小尺寸。

在Scala中，可以覆盖loadFactor用于与着眼于电流大小的函数的标准库的哈希表。奇怪的是，可调整大小的数组只是翻一番，这是大多数人在实践中做。

我不知道任何加倍（或1.5 *荷兰国际集团）阵列实际上赶上内存不足的错误并生长在这种情况下更小。看来，如果你有一个巨大的单一阵列，你会想这样做。

我会进一步增加，如果你保持可调整大小的数组足够长的时间，你倾向于随着时间的推移空间，它可能是有意义的大幅overallocate（在大多数情况下）开始，然后重新分配给完全正确的大小时你就大功告成了。

我同意乔恩斯基特，甚至我的朋友theorycrafter坚持认为，这可以证明是O（1）设定的因素，当2倍。

CPU时间和存储器之间的比率是在每台机器上的不同，所以因子将变化一样多。如果您在使用RAM的千兆字节的机器，和一个缓慢的CPU，复制的元素到新阵列是很多比快速的机器，这可能反过来有较少的内存更昂贵。这是一个可以在理论上回答，一个统一的计算机，这在实际场景中犯规帮助你在所有的问题。

我知道这是一个老问题，但有几件事情，每个人都似乎缺少。

首先，这是乘以2：尺寸<< 1。这是乘以任何 1和2之间：INT（浮动（大小）* x），其中x是数量， *是浮点运算，并且所述处理器具有用于浮动和INT之间铸造运行的附加说明。换句话说，在机器的水平，加倍需要一个单一的，非常快速的指令找到新的大小。通过1和2之间的东西乘以要求的至少一个指令投尺寸为浮点数，一个指令乘以（这是浮动乘法，所以它可能需要至少两倍的周期，如果不是4许多甚至8倍），以及一个指令投退为int，并假定你的平台可以对通用寄存器执行，而不需要使用特殊寄存器浮点运算。总之，你应该期望每个分配算算至少要花10倍，只要一个简单的左移。如果您在重新分配过程中，虽然复制了大量的数据，这可能没有多大的差别。

二，也可能是大踢球者：每个人似乎都认为正在被释放的内存是都与本身连续的，以及与新分配的内存是连续的。除非你是预先分配所有的记忆自己，然后用它作为一个游泳池，这是几乎可以肯定不是这样的。操作系统的可能偶尔的最后这样做，但大部分时间，有将有足够的可用空间碎片，任何像样的内存管理系统将能够在您的记忆会找到一个小孔刚好吻合。一旦你真的咬块，你更有可能以连续的片结束了，但那时，你的分配是足够大，你没有做他们经常足以使它不再重要。总之，这是有趣的想象，使用一些理想的数字将允许最高效地利用可用内存空间，但在现实中，它是不会发生的，除非你的程序是在裸机上运行（如，没有OS下方它使所有的决定）。

我的问题的答案？不，没有理想的数字。它是如此的特殊应用，没有人真正甚至试图。如果你的目标是理想的内存使用情况，您是非常倒霉。对于性能，更低的频率分配是更好的，但如果我们与刚刚去了，我们可以通过4甚至8乘！当然，当从Firefox的一次性使用1GB到8GB跳跃，人们会抱怨，所以甚至没有任何意义。这里有一些经验法则，我会通过，虽然去：

如果你不能优化存储器使用，至少不浪费处理器周期。乘以2是至少一个数量级不是做浮点运算速度更快。它可能不会产生巨大的变化，但它会使一些差异至少（尤其是在早期，在更频繁和更小的分配）。

不要overthink它。如果你只花了4小时，试图找出如何做一些事情，已经完成了，你只是在浪费你的时间。完全说实话，如果有比* 2更好的选择，它会一直在C ++向量类（和许多其他地方）做几十年前。

最后，如果你的真正的要优化，不出汗的小东西。现在天，没有人关心的内存约4KB浪费，除非他们是在嵌入式系统的工作。当你到是1MB和10MB之间的每一个对象的1GB，翻番可能是太多（我的意思是，这是100个1000的对象之间）。如果你能估计预期扩张速度，你可以在某个点水平出来，以线性的增长速度。如果你希望大约每分钟10个对象，则在每步5至10的对象大小（每30秒到一分钟一次）为pr生长obably细

什么这一切归结为是，不要过度觉得，优化一下就可以了，如果你一定要自定义您的应用程序（和平台）。

另一个两分钱

  • 大多数计算机有虚拟存储器!在物理存储器可具有随机的网页无处不在，这都显示，作为一个单一连续的空间，在你的程序是虚拟存储器。该解决的间接通过的硬件。虚拟存储器的用尽问题上的32位系统，但这真的不是一个问题了。所以填充 孔 是不是一个问题了(除特殊环境).因为Windows7甚至微软支持64位没有额外的努力。@2011
  • O(1)达到任何 r >1的因素。同样的数学证明的工作原理不仅为2作为参数。
  • r =1.5可以计算与 old*3/2 因此，没有需要浮点运算。(我说 /2 因为编译器将取代它的位移在产生大会的代码如果他们认为合适的。)
  • MSVC去了 r =1.5，因此至少有一个主要编译器，不使用为2比率。

正如有人2的感觉真好于8。也2的感觉真好于1.1。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top