什么是动态分配的数组理想的增长速度？ [英] What is the ideal growth rate for a dynamically allocated array?

问题描述

C ++有性病:: 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是pretty共同生长因子 - 我是pretty肯定这是什么的ArrayList 和列表＆LT; T＆GT; 在.NET使用。 的ArrayList＆LT; T＆GT; 在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.

编辑：埃里希指出，词典＆LT;，＆GT; 在.NET使用双然后尺寸增大到下一个素数，这样的哈希值可以是桶之间合理分配。 （我敢肯定，我最近看到的文档表明素数实际上并没有分发散列桶很大，但那是另一种答案的理由。）

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屋！