クラス プロジェクトの場合、巡回動的配列に基づいて優先キューの最適な成長係数を見つける必要があります。いくつかのテストを実行しましたが、決定的ではありませんでした。それを示す数学的な方法があると言われましたが、どこにも見つかりませんでした。
少し調べてみたところ、Java ArrayList が 3/2 を使用していることがわかりました。また、9/8 係数を使用する pyhton のリストの ac 実装もあり、基本的には異なるプログラミング言語間で異なると思います。
では、動的配列の「最適な」成長率を見つける数学的な方法はありますか?
短い答えは「いいえ」です。
ほとんどのアプリケーションでは、最適な成長係数は、アレイを 1 つのステップで最大に必要なサイズまで正確に成長させるものです。したがって、後知恵で判断するのは簡単ですが、通常、予測するのは困難です。
その最大サイズに関する情報が不足しているため、メモリ要件を最適化する戦略は、各ステップで 1 つの追加セルを割り当てるものです。再割り当ての数を最適化するものは、単一のステップで必要になる可能性があるだけのメモリを割り当てるものです。ほとんどの実用的なアプリケーションでは、どちらの極端も合理的ではありません。通常、メモリと再割り当ての間のトレードオフが必要です。
そのトレードオフに関する好みを数学的に表現できます。たとえば、割り当ての数または頻度、割り当てられたスペースの合計量、および実際に使用されたパーセンテージの関数としてコストを定式化することによって。これに加えて、典型的な使用パターンの数学的モデルがあれば、最適化を開始できます。つまり、成長係数を変更してコストを最小限に抑えることができます。
実際には、コストも使用量も多くの外的要因に依存するため、よくわかっていません。したがって、それはすべて直感と経験に帰着します。アプリがメモリを浪費していることに気付いた場合は、成長係数を減らし、再割り当てに多くの時間を費やしていることに気付いた場合は、係数を増やす可能性があります。どちらの変更も、数学的モデリングがあまり関係していないため、非常にアドホックです。