动态分配阵列的理想增长率是多少？

Question

C ++具有std :: vector，而Java具有ArrayList，许多其他语言都有其自己的动态分配数组形式。当动态数组空间不足时，它将重新分配到更大的区域中，并将旧值复制到新数组中。这种阵列性能的核心问题是阵列大小增长的速度。如果您总是只增长到足以容纳当前推送的大小，则最终每次都会重新分配。因此，将数组大小加倍或乘以1.5倍是有意义的。有理想的成长因素吗？2倍？1.5倍？理想情况下，我的意思是数学上合理的，最佳的平衡性能和浪费的内存。我意识到从理论上讲，鉴于您的应用程序可能具有任何潜在的推送分布，因此这在某种程度上取决于应用程序。但是我很想知道是否有一个值“通常”是最好的，或者在某些严格的约束条件下被认为是最好的。我听说某处有一篇论文，但我一直找不到。

Answer 1

在回答这样的问题时，一种方法是仅“欺骗”并查看流行的库所做的事情，前提是假定广泛使用的库至少没有做任何可怕的事情。

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