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 

---

從這個

所以你可以得到一個粗略的數學家關於時間/記憶折衷如何解決這個問題的想法。當然有一些注意事項：當元素數量減少時，我沒有重新縮小數組，這隻涵蓋了最糟糕的情況，即沒有元素被刪除，分配額外內存的時間成本沒有考慮。

他們很可能跑了一堆實驗測試，最終弄清楚了這些，儘管我寫的大部分內容都是不相關的。