arrays - 动态分配数组的理想增长率是多少？

Question

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

有理想的生长因子吗？ 2x？ 1.5倍？我所说的理想是指数学上合理的、最佳的平衡性能和浪费的内存。我意识到，从理论上讲，考虑到您的应用程序可能具有任何潜在的推送分布，这在某种程度上取决于应用程序。但我很好奇是否有一个值“通常”是最好的，或者在某些严格的约束下被认为是最好的。

我听说某处有一篇关于此问题的论文，但我找不到它。

Answer 1

我记得很多年前读过为什么 1.5 比 2 更好，至少在应用于 C++ 时是如此(这可能不适用于托管语言，因为运行时系统可以随意重新定位对象)。

理由是这样的:

1. 假设您从 16 字节分配开始。
2. 当您需要更多时，您可以分配 32 个字节，然后释放 16 个字节。这会在内存中留下 16 字节的漏洞。
3. 当您需要更多时，您可以分配 64 字节，从而释放 32 字节。这会留下一个 48 字节的空洞(如果 16 和 32 相邻)。
4. 当您需要更多时，您可以分配 128 字节，从而释放 64 字节。这会留下一个 112 字节的漏洞(假设所有先前的分配都是相邻的)。
5. 等等。

这个想法是，通过 2 倍扩展，所产生的空洞永远不会大到足以重新用于下一次分配。使用 1.5 倍分配，我们有这样的:

1. 从 16 个字节开始。
2. 当您需要更多字节时，分配 24 个字节，然后释放 16 个字节，留下 16 字节的空位。
3. 当您需要更多字节时，分配 36 个字节，然后释放 24 个字节，留下 40 字节的空间。
4. 当您需要更多字节时，分配 54 个字节，然后释放 36 个字节，留下 76 字节的空间。
5. 当您需要更多字节时，分配 81 字节，然后释放 54 字节，留下 130 字节的空间。
6. 当您需要更多时，请使用 130 字节孔中的 122 字节(向上舍入)。