Dlaczego push_back w wektorach C ++ jest stale amortyzowany?

Uczę się C ++ i zauważyłem, że czas działania funkcji push_back dla wektorów jest stały „amortyzowany”. Dokumentacja zauważa ponadto, że „Jeśli nastąpi realokacja, sama realokacja jest liniowa w całym rozmiarze”.

Czy nie powinno to oznaczać, że funkcją push_back jest , gdzie jest długością wektora? W końcu interesuje nas analiza najgorszego przypadku, prawda?$O(n)$$n$

Chyba przede wszystkim nie rozumiem, w jaki sposób przymiotnik „zamortyzowany” zmienia czas działania.

Ważnym słowem jest tutaj „amortyzowane”. Amortyzowana analiza to technika analizy, która bada sekwencję operacji. Jeśli cała sekwencja działa w czasie T ( n ) , wówczas każda operacja w sekwencji przebiega w T ( n ) / n . Chodzi o to, że chociaż kilka operacji w sekwencji może być kosztownych, nie mogą się zdarzyć wystarczająco często, aby obciążyć program. Należy zauważyć, że różni się ona od analizy średnich przypadków w przypadku niektórych rozkładów danych wejściowych lub analizy losowej. Analiza zamortyzowana wykazała najgorszy przypadek$n$$T(n)$$T(n)/n$związany z wydajnością algorytmu niezależnie od danych wejściowych. Najczęściej służy do analizy struktur danych, które mają trwały stan w całym programie.

$k$$O(n)$$n$$O(n)$$O(1)$

$m$

$n$$m$$\log_m(n)$$i$$m^i$$n$$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$$\frac{m}{m-1}$$m$$1$$m$$1.5$

Chociaż @Marc dał (moim zdaniem) doskonałą analizę, niektórzy ludzie wolą rozważać sprawy z nieco innej perspektywy.

Jednym z nich jest rozważenie nieco innego sposobu dokonania realokacji. Zamiast natychmiastowego kopiowania wszystkich elementów ze starej pamięci do nowej pamięci, rozważ skopiowanie tylko jednego elementu na raz - tzn. Za każdym razem, gdy wykonujesz push_back, dodaje on nowy element do nowej przestrzeni i kopiuje dokładnie jeden istniejący element ze starej przestrzeni do nowej przestrzeni. Zakładając współczynnik wzrostu 2, jest całkiem oczywiste, że gdy nowa przestrzeń jest pełna, skończymy kopiowanie wszystkich elementów ze starej przestrzeni do nowej przestrzeni, a każde push_back ma dokładnie taki sam czas. W tym momencie odrzucilibyśmy starą przestrzeń, przydzieliliśmy nowy blok pamięci, który był dwa razy większy, i powtórzyliśmy ten proces.

Całkiem wyraźnie możemy kontynuować to w nieskończoność (lub tak długo, jak długo jest dostępna pamięć), a każde push_back wymagałoby dodania jednego nowego elementu i skopiowania jednego starego elementu.

Typowa implementacja wciąż ma dokładnie taką samą liczbę kopii - ale zamiast kopiować pojedynczo, kopiuje wszystkie istniejące elementy naraz. Z jednej strony masz rację: oznacza to, że jeśli spojrzysz na poszczególne wywołania push_back, niektóre z nich będą znacznie wolniejsze niż inne. Jeśli jednak spojrzymy na średnią długoterminową, ilość kopiowania wykonanego na wywołanie push_back pozostaje stała, niezależnie od wielkości wektora.

Chociaż nie ma to znaczenia dla złożoności obliczeniowej, myślę, że warto wskazać, dlaczego warto robić takie rzeczy, jak to robią, zamiast kopiować jeden element na push_back, więc czas na push_back pozostaje stały. Są co najmniej trzy powody do rozważenia.

Pierwszy to po prostu dostępność pamięci. Starą pamięć można zwolnić do innych zastosowań dopiero po zakończeniu kopiowania. Jeśli skopiowałeś tylko jeden element na raz, stary blok pamięci pozostałby przydzielony znacznie dłużej. W rzeczywistości miałbyś cały stary jeden i jeden nowy blok. Jeśli zdecydujesz się na czynnik wzrostu mniejszy niż dwa (który zwykle chcesz), będziesz potrzebować jeszcze więcej pamięci przydzielanej przez cały czas.

Po drugie, jeśli skopiowałeś tylko jeden stary element na raz, indeksowanie do tablicy byłoby nieco trudniejsze - każda operacja indeksowania musiałaby dowiedzieć się, czy element o danym indeksie znajduje się obecnie w starym bloku pamięci, czy nowy. Nie jest to wcale skomplikowane, ale dla elementarnej operacji, takiej jak indeksowanie do tablicy, prawie każde spowolnienie może być znaczące.

Po trzecie, kopiując wszystko naraz, znacznie lepiej wykorzystujesz buforowanie. Kopiując wszystko naraz, możesz spodziewać się, że zarówno źródło, jak i miejsce docelowe będą w pamięci podręcznej w większości przypadków, więc koszt braku pamięci podręcznej jest amortyzowany przez liczbę elementów, które zmieszczą się w linii pamięci podręcznej. Jeśli kopiujesz jeden element na raz, możesz łatwo mieć brak pamięci podręcznej dla każdego kopiowanego elementu. To tylko zmienia stały współczynnik, a nie złożoność, ale wciąż może być dość znaczący - dla typowej maszyny można łatwo oczekiwać współczynnika od 10 do 20.

Prawdopodobnie warto też na chwilę zastanowić się nad innym kierunkiem: jeśli projektujesz system z wymaganiami w czasie rzeczywistym, warto skopiować tylko jeden element na raz zamiast wszystkich naraz. Chociaż ogólna prędkość może (lub nie musi) być niższa, nadal będziesz mieć górną granicę czasu potrzebnego na jedno wykonanie push_back - zakładając, że masz alokator w czasie rzeczywistym (choć oczywiście wiele w czasie rzeczywistym systemy po prostu zabraniają w ogóle dynamicznego przydzielania pamięci, przynajmniej w częściach z wymaganiami w czasie rzeczywistym).