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

C ++具有std :: vector,而Java具有ArrayList,许多其他语言都有其自己的动态分配数组形式。当动态数组空间不足时,它将重新分配到更大的区域中,并将旧值复制到新数组中。这种阵列性能的核心问题是阵列大小增长的速度。如果您总是只增长到足以容纳当前推送的大小,则最终每次都会重新分配。因此,将数组大小加倍或乘以1.5倍是有意义的。

有理想的成长因素吗?2倍?1.5倍?理想情况下,我的意思是数学上合理的,最佳的平衡性能和浪费的内存。我意识到从理论上讲,鉴于您的应用程序可能具有任何潜在的推送分布,因此这在某种程度上取决于应用程序。但是我很想知道是否有一个值“通常”是最好的,或者在某些严格的约束条件下被认为是最好的。

我听说某处有一篇论文,但我一直找不到。


撒科打诨
浏览 621回答 3
3回答

侃侃无极

在回答这样的问题时,一种方法是仅“欺骗”并查看流行的库所做的事情,前提是假定广泛使用的库至少没有做任何可怕的事情。因此,只需快速检查一下,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&nbsp;* for additional growth.&nbsp; The over-allocation is mild, but is&nbsp;* enough to give linear-time amortized behavior over a long&nbsp;* sequence of appends() in the presence of a poorly-performing&nbsp;* system realloc().&nbsp;* The growth pattern is:&nbsp; 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...&nbsp;*/new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);/* check for integer overflow */if (new_allocated > PY_SIZE_MAX - newsize) {&nbsp; &nbsp; PyErr_NoMemory();&nbsp; &nbsp; return -1;} else {&nbsp; &nbsp; new_allocated += newsize;}newsize以上是数组中元素的数量。请注意,它newsize已添加到new_allocated,因此具有位移和三元运算符的表达式实际上只是在计算超额分配。
打开App,查看更多内容
随时随地看视频慕课网APP