为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

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

3 回答

?
侃侃无极

TA贡献2051条经验 获得超10个赞

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


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

查看完整回答
反对 回复 2019-11-25
  • 3 回答
  • 0 关注
  • 617 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信