C ++ ma std :: vector, a Java ma ArrayList, a wiele innych języków ma własną formę dynamicznie przydzielanej tablicy. Gdy w dynamicznej tablicy zabraknie miejsca, zostanie ona ponownie przydzielona do większego obszaru, a stare wartości zostaną skopiowane do nowej tablicy. Kluczową kwestią dla wydajności takiej tablicy jest szybkość powiększania się tablicy. Jeśli zawsze będziesz wystarczająco duży, aby zmieścić się w bieżącym pchnięciu, za każdym razem zostaniesz ponownie przydzielony. Dlatego warto podwoić rozmiar tablicy lub pomnożyć ją przez powiedzmy 1,5x.

Czy istnieje idealny czynnik wzrostu? 2x? 1,5x? Idealnie rozumiem matematycznie uzasadnioną, najlepszą równowagę wydajności i zmarnowaną pamięć. Zdaję sobie z tego sprawę teoretycznie, biorąc pod uwagę, że twoja aplikacja może mieć dowolną potencjalną dystrybucję popchnięć, co jest w pewnym stopniu zależne od aplikacji. Ale jestem ciekawy, czy istnieje wartość, która jest „zwykle” najlepsza lub jest uważana za najlepszą w ramach pewnego rygorystycznego ograniczenia.

Słyszałem, że gdzieś jest na ten temat artykuł, ale nie mogłem go znaleźć.