性病的摊销分析::载体插入 [英] Amortized analysis of std::vector insertion

问题描述

我们怎么做插入的分析，在一个std :: vector的后面（的push_back）？它的摊销时间是每次插入O（1）。特别是在一个<一href="http://channel9.msdn.com/Shows/Going+Deep/STL-Some-Underlying-Algorithms-Data-Structures-and-More-with-Stephan-T-Lavavej">video在Channel9的史蒂芬牛逼Lavavej 和<一href="http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Introduction-to-STL-with-Stephan-T-Lavavej">in这个（17:42以后）他说，以获得最佳性能微软的此方法的实现约1.5增加了向量的能力。

How do we do the analysis of insertion at the back (push_back) in a std::vector? It's amortized time is O(1) per insertion. In particular in a video in channel9 by Stephan T Lavavej and in this ( 17:42 onwards ) he says that for optimal performance Microsoft's implementation of this method increases capacity of the vector by around 1.5.

这是怎么常数决定？

推荐答案

假设你的意思是的push_back ，而不是插入，我认为重要的部分是乘以某个常数（而不是抓住每一次N多的元素），只要你这样做，你会得到分期常量时间。改变的因素改变了一般情况和最坏情况下的性能。

Assuming you mean push_back and not insertion, I believe that the important part is the multiply by some constant (as opposed to grabbing N more elements each time) and as long as you do this you'll get amortized constant time. Changing the factor changes the average case and worst case performance.

具体： 如果你的常数因子太大，你就会有不错的平均情况下的性能，但糟糕的最坏情况下的性能尤其是作为数组弄大。例如，假设增加一倍（2个），只是因为你有10001th元素推了10000大小的矢量。编辑：正如迈克尔·伯尔间接地指出，真正的成本可能是，你会增加你的记忆远远大于你需要它。我想补充一点，有一些影响速度，如果你的因素太大的缓存问题。我只想说，有实际成本（存储和计算），如果你的成长远远大于你所需要的。

Concretely: If your constant factor is too large, you'll have good average case performance, but bad worst case performance especially as the arrays get big. For instance, imagine doubling (2x) a 10000 size vector just because you have the 10001th element pushed. As Michael Burr indirectly pointed out, the real cost here is probably that you'll grow your memory much larger than you need it to be. I would add to this that there are cache issues that affect speed if your factor is too large. Suffice it to say that there are real costs (memory and computation) if you grow much larger than you need.

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

However if your constant factor is too small, say (1.1x) then you're going to have good worst case performance, but bad average performance, because you're going to have to incur the cost of reallocating too many times.

<一个href="http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array">Also,看到乔恩斯基特的回答类似的问题previously。（感谢@Bo佩尔松）

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

一个稍微介绍一下分析：假设你有 N 你推背项目和米乘系数。然后重新分配的数量将大致将基准站的 M N （ log_M（N） ）。而我次重新分配的费用比例立方公尺我（ M 到我次方）。然后，所有的回送的总时间为平方公尺1 + M ^ 2 + ... M ^（log_M（N））。回送的数量是 N ，这样的话你得到这个系列（这是一个几何级数，并减少了约（NM）/（M- 1）的限制）除以 N 。这是大致恒定的， M /（M-1）。

A little more about the analysis: Say you have n items you are pushing back and a multiplication factor of M. Then the number of reallocations will be roughly log base M of n (log_M(n)). And the ith reallocation will cost proportional to M^i (M to the ith power). Then the total time of all the pushbacks will be M^1 + M^2 + ... M^(log_M(n)). The number of pushbacks is n, and thus you get this series (which is a geometric series, and reduces to roughly (nM)/(M-1) in the limit) divided by n. This is roughly a constant, M/(M-1).

有关的米的大型值您将冲过了很多，拨出远远超过你合理地经常（我上面提到的）需要。对于 M （接近1）小的值这个常量 M /（M-1）变大。这一因素直接影响的平均时间。

For large values of M you will overshoot a lot and allocate much more than you need reasonably often (which I mentioned above). For small values of M (close to 1) this constant M/(M-1) becomes large. This factor directly affects the average time.

这篇关于性病的摊销分析::载体插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！