std :: vector插入的摊销分析

Question

我们如何分析std :: vector中后面的插入(push_back)？它的摊销时间是每次插入O(1).特别是在史蒂芬牛逼Lavavej在Channel9的视频,并在此(17:42以后),他说,以获得最佳性能微软的这个方法的实现由大约1.5增加了向量的能力.

这个常数如何确定？

Answer 1

假设你的意思push_back,而不是插入,我认为重要的部分是由多重一些不变(而不是抓住每一次N多元素),只要你这样做你会得到分期常量时间.更改因子会改变平均情况和最差情况.

具体来说:如果你的常数因子过大,你将获得良好的平均大小写性能,但是最糟糕的情况下表现不佳,尤其是当阵列变大时.例如,想象一下,加倍(2x)10000大小的向量只是因为你推送了第10001个元素.编辑:正如迈克尔伯尔间接指出的那样,这里真正的成本可能是你的记忆力比你需要的要大得多.我想补充一点,如果你的因素太大,就会有影响速度的缓存问题.我只想说,如果你的成长比你需要的大得多,那就有实际成本(记忆和计算).

但是,如果你常数因子太小,说(1.1倍),那么你将有良好的最坏情况下的性能,但糟糕的表现平平,因为你将不得不承担重新分配的次数太多的成本.

此外,请参阅Jon Skeet先前对类似问题的回答. (谢谢@Bo Persson)

关于分析的更多信息:假设你有n推回的物品和倍增系数M.然后,重新分配的数量将大致M为n(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)变大.这个因素直接影响平均时间.

Answer 2

你可以做数学试图弄清楚这种事情是如何起作用的.

使用渐近分析的一种流行方法是Bankers方法.你所做的是用额外的费用标记你的所有操作,"保存"它以便以后支付昂贵的操作费用.

让我们做一些转储假设来简化数学运算:

• 写入数组成本1.(在数组之间插入和移动相同)
• 分配更大的阵列是免费的.

我们的算法看起来像:

function insert(x){
    if n_elements >= maximum array size:
         move all elements to a new array that
         is K times larger than the current size
    add x to array
    n_elements += 1

显然,当我们必须将元素移动到新数组时,会发生"最坏情况".让我们尝试通过d为插入成本添加一个常量标记来分摊这个,使其达到(1 + d)每个操作的总和.

在调整阵列大小之后,我们已经填充了(1/K)并且没有省钱.当我们填满阵列时,我们肯定至少可以d * (1 - 1/K) * N保存起来.由于这笔钱必须能够支付所有被移动的N个元素,我们可以找出K和之间的关系d:

d*(1 - 1/K)*N = N
d*(K-1)/K = 1
d = K/(K-1)

一张有用的表:

k    d     1+d(total insertion cost)
1.0  inf   inf
1.1  11.0  12.0
1.5  3.0   4.0
2.0  2.0   3.0
3.0  1.5   2.5
4.0  1.3   2.3
inf  1.0   2.0

因此,你可以得到一个粗略的数学家关于时间/内存权衡如何适用于这个问题的想法.当然有一些注意事项:当元素数量减少时,我没有过度缩小数组,这只能解决最糟糕的情况,即没有删除任何元素,并且没有考虑分配额外内存的时间成本.

他们最有可能进行了大量的实验测试,最终弄清楚这一点,尽管我写的大部分内容都无关紧要.