std :: vector插入的分期分析

Question

我们如何做一个std :: vector的后面插入分析（push_back）？它的分期时间是O（1）每次插入。特别是在video in channel9 by Stephan T Lavavej和in this (17:42 onwards)中，他表示为了获得最佳性能，微软采用这种方法将向量的容量提高了1.5左右。

这个常数是如何确定的？

Answer 1

假设你的意思是push_back而不是插入，我相信重要的部分是乘以某个常量（而不是每次抓取更多的元素），只要你这样做，你会得到摊销的恒定时间。更改因素会改变平均情况和最坏情况的表现。

具体而言： 如果您的常数因子太大，您将具有良好的平均案例性能，但是坏的最差情况下性能尤其是在阵列变大时。例如，想象仅仅因为您推送了第10001个元素而加倍（2x）10000大小的矢量。编辑：正如Michael Burr间接指出的那样，这里的真正成本可能是你的记忆力会比你想要的要大得多。我会补充说，如果你的因素太大，缓存问题会影响速度。只要说如果你的增长远大于你的需求，就会有真正的成本（内存和计算）。然而，如果你的常数因子太小，比如说（1.1x），那么你将会得到很好的最差情况表现，但糟糕的平均表现，因为你将不得不承担重新分配太多的成本倍。

Also, see Jon Skeet's answer to a similar question previously.（感谢@Bo佩尔松）

，稍微介绍一下分析：假设你有n项目你是推回去的M倍增因子。然后，重新分配的次数将大致以n（log_M(n)）的基数M为基数。并且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

呃，这个分析非常简单，当你熟悉数字系统时，比如我们通常的十进制。然后，为了简单起见，假设每次达到当前容量时，分配一个新的10x作为大缓冲区。

如果原始缓冲区大小为1，则第一次重新分配副本1元素，第二次（现在缓冲区大小为10）复制10个元素，依此类推。因此，有五次重新分配，例如，您执行1 + 10 + 100 + 1000 + 10000 = 11111个元素副本。乘以9，得到99999;现在加1，你有100000 = 10^5。或者换句话说，这样做后，为支持这5次重新分配而执行的元素副本的数量是（10^5-1）/ 9。

5次重新分配之后的缓冲区大小乘以5，乘以10，即为10^5。这大约比元素复制操作的数量大9倍。这意味着复制的时间在所得到的缓冲区大小上大致是线性的。

使用基数2而不是10可得（2^5-1）/ 1 = 2^5-1。

等等用于其他基地（或增加缓冲区大小的因素）。

干杯& hth。

Answer 3

你可以做数学来试图找出这种事情是如何工作的。

一种流行的渐近分析方法是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 

---

从这个

所以你可以得到一个粗略的数学家关于时间/记忆折衷如何解决这个问题的想法。当然有一些注意事项：当元素数量减少时，我没有重新缩小数组，这只涵盖了最糟糕的情况，即没有元素被删除，分配额外内存的时间成本没有考虑。

他们很可能跑了一堆实验测试，最终弄清楚了这些，尽管我写的大部分内容都是不相关的。