c++ - std::vector 插入的摊销分析

Question

我们如何分析 std::vector 的后面插入(push_back)？每次插入的摊销时间是 O(1)。特别是在 video in channel9 by Stephan T Lavavej和 in this ( 17:42 onwards )他说，为了获得最佳性能，微软对这种方法的实现将 vector 的容量增加了大约 1.5。

这个常数是如何确定的？

Answer 1

假设你的意思是 push_back 而不是插入，我相信重要的部分是乘以某个常数(而不是每次抓取 N 个更多元素)，只要你这样做，你会得到摊销的常数时间。更改因子会更改平均情况和最差情况的性能。

具体来说:如果您的常数因子太大，您将获得良好的平均情况性能，但最坏情况下的性能较差，尤其是当阵列变大时。例如，假设仅仅因为您推送了第 10001 个元素，就将 10000 大小的 vector 加倍 (2x)。编辑:正如迈克尔伯尔间接指出的那样，这里的真正成本可能是你的内存力增长得比你需要的要大得多。我要补充一点，如果您的因素太大，缓存问题会影响速度。可以说，如果您的增长超出您的需要，就会产生实际成本(内存和计算)。

但是，如果您的常数因子太小，例如 (1.1x)，那么您将获得良好的最坏情况性能，但平均性能较差，因为您将不得不承担重新分配太多次的成本.

Also, see Jon Skeet's answer to a similar question previously. (感谢@Bo Persson)

关于分析的更多信息:假设您有 n 个要推回的项目和一个 M 的乘法因子。那么重新分配的数量将大致为 n 的 log base M (log_M(n))。并且第 i 次重新分配的成本与 M^i 成正比(M 的 i 次方)。那么所有推回的总时间将是M^1 + M^2 + ... M^(log_M(n))。推回的数量是n，因此你得到这个系列(这是一个几何系列，并且在限制中减少到大致(nM)/(M-1) ) 除以 n。这大致是一个常数，M/(M-1)。

对于较大的 M 值，您会超调很多，并且分配的数量会超出您合理经常需要的数量(我在上面提到过)。对于 M 的小值(接近 1)，这个常数 M/(M-1) 会变大。这个因素直接影响平均时间。