对于一个类项目，我们需要找到一个基于循环动态数组的优先级队列的最优增长因子。我进行了一些测试，但没有结果。我们被告知有一种数学方法可以显示它，但我在任何地方都找不到。
我查了一下，发现 Java ArrayList 使用 3/2，pyhton 的列表也有 ac 实现，它使用 9/8 因子，基本上我认为它在不同的编程语言之间有所不同。
那么是否有任何数学方法可以找到动态数组的“最佳”增长因子？
问问题
247 次
1 回答
3
最简洁的答案是不”。
对于大多数应用程序，最佳增长因子将是在单个步骤中将阵列精确增长到其最大所需大小的因子。所以事后很容易确定，但通常很难预测。
因此缺乏关于最大大小的信息，优化内存需求的策略是在每个步骤中分配一个额外的单元格。优化重新分配次数的方法是在单个步骤中分配尽可能多的内存。对于大多数实际应用，这两个极端都不合理。通常需要在内存和重新分配之间进行权衡。
您可以用数学术语表达您对这种权衡的偏好。例如，通过将一些成本公式化为分配数量或频率、总分配空间量和实际使用百分比的函数。如果除此之外您还有典型使用模式的数学模型，那么您可以开始优化，即改变增长因子以最小化成本。
在实践中，成本和使用情况都不是很清楚，因为两者都取决于许多外部因素。因此，这一切都归结为直觉和经验。如果你注意到你的应用程序在浪费内存，你可能会降低增长因子，如果你注意到它在重新分配上花费了太多时间，你可能会增加这个因子。这两种变化都是非常临时的，没有涉及太多的数学建模。
于 2013-11-24T09:41:23.660 回答