20

我们如何分析 std::vector 后面的插入（push_back）？每次插入的摊销时间是 O(1)。特别是在Stephan T Lavavej 在第 9 频道的一段视频中，在这段视频中（从 17:42 开始），他说，为了获得最佳性能，微软对这种方法的实现将向量的容量增加了大约 1.5。

这个常数是如何确定的？

4

3 回答 3

20

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

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

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

另外，请参阅 Jon Skeet 之前对类似问题的回答。 （感谢@Bo Persson）

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

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

于 2011-07-01T16:37:24.493 回答
8

你可以做数学来尝试弄清楚这种事情是如何工作的。

使用渐近分析的一种流行方法是银行家方法。您所做的是用额外的成本标记所有操作，“保存”它以供以后支付昂贵的操作。

让我们做一些转储假设来简化数学：

  • 写入数组成本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

因此，从中您可以大致了解数学家对时间/内存权衡如何解决此问题的想法。当然，有一些警告：当数组元素减少时，我没有过度缩小数组，这只涵盖了没有元素被删除并且没有考虑分配额外内存的时间成本的最坏情况。

他们很可能进行了一系列实验测试以最终弄清楚这一点，尽管我写的大部分内容都无关紧要。

于 2011-07-01T17:19:11.627 回答
1

嗯，当你熟悉数字系统时，分析真的很简单，比如我们通常的十进制。

为简单起见，假设每次达到当前容量时，都会分配一个新的 10 倍大的缓冲区。

如果原始缓冲区大小为 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。

于 2011-07-01T17:06:51.500 回答