arrays - スタック容量を固定量だけ増やすのではなく、なぜ2倍にするのですか？

Question

スタックの配列実装を使用しています。エラーをスローする代わりにスタックがいっぱいの場合は、配列サイズを2倍にし、要素をコピーし、スタック参照を変更して、新しい要素をスタックに追加しています。（私は自分自身にこのことを教えるために本をフォローしています）。

私が完全に理解していないのは、なぜそれを2倍にする必要があるのか​​、なぜそれを一定量だけ増やすのか、なぜそれを3倍にするのかということです。

時間計算量と関係があると思いますか？

説明をいただければ幸いです！

Answer 1

ダブリングは、配列リスト（バックグラウンドで実行していることを実際に実行する「動的」サイズの配列）や、配列に裏打ちされた最も動的なサイズのデータ​​型などの一般的な実装の標準になりました。シナリオを知っていて、カスタムスタック/配列リストの実装を作成する時間と意志があれば、より最適なソリューションを作成できます。

最初の配列が構築された後、アイテムが信じられないほど頻繁に追加されないことがソフトウェアでわかっている場合は、特定のサイズで初期化し、メモリを保持するために追加されたサイズだけ増やすことができます。

一方、リストが頻繁に拡張されることがわかっている場合は、スペースが不足したときにリストのサイズを3倍以上増やすことを選択できます。

共通ライブラリの一部である一般的な実装の場合、実装の詳細と要件は不明であるため、2倍にすることは単なる幸せな媒体です。

Answer 2

理論的には、実際にはさまざまな時間計算量に到達します。一定のサイズだけ増やすと、再割り当ての数（したがって、O（n）コピー）を定数で除算しますが、追加する場合でもO（n）時間計算量が得られます。それらを2倍にすると、追加の時間計算量が向上し（armortized O（1）IIRC）、最大で必要な2倍のメモリを消費するため、同じ空間計算量が得られます。

実際には、それほど深刻ではありませんが、それでも実行可能です。コピーは高価ですが、通常は少しのメモリで問題はありません。これはトレードオフですが、別の戦略を選択するには、メモリをかなり少なくする必要があります。多くの場合、実際に必要なスペースの量が事前にわからない（またはAPIの制限のためにスタックに通知できない）。たとえば、1つの要素から始めて1024要素のスタックを構築すると、1024 / Kから10回の再割り当てになります（K = 3と仮定すると、約34倍になります）。少しのメモリを節約するためだけに、多くの再割り当て。

他の要因についても同じことが言えます。2は、整数以外のサイズになることはなく、それでも非常に小さいため、無駄なスペースを50％に制限できるので便利です。特定のユースケースは他の要因によってより適切に提供される可能性がありますが、通常、ROIは小さすぎて、一部のライブラリですでに利用可能なものを再実装および最適化することを正当化できません。

Answer 3

固定金額の問題は、その固定金額を選択することです。たとえば、固定金額として100アイテムを選択した場合、スタックのサイズが現在100アイテム以下であれば意味があります。ただし、スタックのサイズがすでに10,000アイテムである場合は、11,000アイテムに増える可能性があります。スタックのサイズを10％増やすために、10回の再割り当て/移動を実行する必要はありません。

2xと3xについては、それはかなり恣意的です。3xを選択しても問題はありません。どちらが「より良い」かは、正確なユースケースと「より良い」をどのように定義するかによって異なります。

Answer 4

2倍のスケーリングは簡単で、平均して2回以下のアイテムがコピーされます[拡張すると、最初にアイテムの半分、2番目に4分の1、3番目に8分の1などがコピーされます]代わりに一定量増加した後、たとえば20回目の拡張を実行すると、アイテムの半分が10回目にコピーされます。

2倍以上に成長すると、平均的な「永続的な」たるみスペースが増加します。係数を小さくすると、割り当てられて放棄されるストレージの量が増えます。恒久的および放棄された割り当ての相対的な認識された「コスト」に応じて、最適な成長因子は大きくなることも小さくなることもありますが、最適に近い成長因子は、一般に、最適な成長因子よりもパフォーマンスがそれほど悪くなることはありません。最適な成長因子が何であるかに関係なく、2倍の成長因子はまともなパフォーマンスを生み出すのに十分に近いでしょう。