[解決済み] ダイナミックアロケーションアレイの理想的な成長率は？

質問

C++にはstd::vector、JavaにはArrayListがあり、その他多くの言語には独自の形式の動的割り当て配列があります。動的配列の容量が不足すると、より大きな領域に再割り当てされ、古い値が新しい配列にコピーされます。このような配列の性能の中心的な問題は、配列のサイズがどの程度の速さで大きくなるかということです。もし、常に現在のプッシュが収まるだけの大きさにしか成長しないのであれば、毎回再割り当てすることになります。ですから、配列のサイズを2倍にするか、あるいは1.5倍程度にするのが理にかなっています。

理想的な成長率はあるのでしょうか？2x? 1.5x? 理想的というのは、数学的に正当化され、パフォーマンスと無駄なメモリのバランスをとるのに最も適しているという意味です。理論的には、アプリケーションにはどのようなプッシュの分布もあり得るので、これは多少アプリケーションに依存するものだと理解しています。しかし、私は、最適な値があるかどうか、または何らかの厳密な制約の中で最適と見なされる値があるかどうかを知りたいと考えています。

このことに関する論文がどこかにあると聞いたことがありますが、見つけられませんでした。

どのように解決するのですか？

それは完全にユースケースに依存します。データをコピーして無駄になる時間 (および配列の再割り当て) と余分なメモリのどちらを気にしますか? 配列はどのくらいの期間使用されるのでしょうか。もし、長くは続かないのであれば、より大きなバッファを使用することは良いアイデアかもしれません。ペナルティは短時間で済みます。配列が長く続く場合 (たとえば Java では、ますます古い世代に移行します) は、明らかにより大きなペナルティになります。

理想的な成長因子というものはないのです。 理論的には