动态分配数组的理想增长率是多少? [英] What is the ideal growth rate for a dynamically allocated array?

问题描述

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

C++ has std::vector and Java has ArrayList, and many other languages have their own form of dynamically allocated array. When a dynamic array runs out of space, it gets reallocated into a larger area and the old values are copied into the new array. A question central to the performance of such an array is how fast the array grows in size. If you always only grow large enough to fit the current push, you'll end up reallocating every time. So it makes sense to double the array size, or multiply it by say 1.5x.

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

Is there an ideal growth factor? 2x? 1.5x? By ideal I mean mathematically justified, best balancing performance and wasted memory. I realize that theoretically, given that your application could have any potential distribution of pushes that this is somewhat application dependent. But I'm curious to know if there's a value that's "usually" best, or is considered best within some rigorous constraint.

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

I've heard there's a paper on this somewhere, but I've been unable to find it.

推荐答案

这完全取决于用例.您更关心在复制数据(和重新分配数组)上浪费的时间还是额外的内存?阵列将持续多久?如果它不会持续很长时间，使用更大的缓冲区可能是一个好主意 - 惩罚是短暂的.如果它会继续存在(例如在 Java 中，进入老一代和老一代)，这显然是一种惩罚.

It will entirely depend on the use case. Do you care more about the time wasted copying data around (and reallocating arrays) or the extra memory? How long is the array going to last? If it's not going to be around for long, using a bigger buffer may well be a good idea - the penalty is short-lived. If it's going to hang around (e.g. in Java, going into older and older generations) that's obviously more of a penalty.

没有理想的生长因子"这样的东西.它不仅理论上依赖于应用程序，而且绝对依赖于应用程序.

There's no such thing as an "ideal growth factor." It's not just theoretically application dependent, it's definitely application dependent.

2 是一个非常常见的增长因素 - 我很确定这就是 .NET 中的 ArrayList 和 List 所使用的.ArrayList 在 Java 中使用 1.5.

2 is a pretty common growth factor - I'm pretty sure that's what ArrayList and List<T> in .NET uses. ArrayList<T> in Java uses 1.5.

正如 Erich 指出的那样，.NET 中的 Dictionary<,> 使用将大小加倍然后增加到下一个质数"，以便可以在存储桶之间合理分配哈希值.(我敢肯定我最近看到的文档表明素数对于分发哈希桶实际上并不是那么好，但这是另一个答案的论据.)

As Erich points out, Dictionary<,> in .NET uses "double the size then increase to the next prime number" so that hash values can be distributed reasonably between buckets. (I'm sure I've recently seen documentation suggesting that primes aren't actually that great for distributing hash buckets, but that's an argument for another answer.)

这篇关于动态分配数组的理想增长率是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！