c - cにスタックを実装する

Question

動的メモリ割り当てで機能するスタックを作成したいのですが、どちらがより効率的かを知る必要が
あります。たとえば、初期サイズを10のようにし、さらに必要な場合は2倍にします。
または、初期サイズ= 1にして、新しい入力ごとに1つの場所を追加することもできます。！？！

int *tmp = malloc(sizeof(int) * 2 * dm->capacity); \* dm->capacity = 10 *\
int *tmp = malloc(sizeof(int));

Answer 1

必要なときに2倍にする方が、はるかに効率的です。

プッシュ操作ごとに新しい配列を割り当てる場合は、スタック要素の数の2乗に比例する量の作業を実行します（要素をプッシュするときは、前の要素を新しい配列にN+1コピーする必要があります）。N

必要に応じて配列を2倍にすると、コピーの数はNの対数に比例します。また、重要なサイズのスタックの場合、ご存知のとおり、これは大幅に小さくなります。

Answer 2

場合によります。通常、2倍にする方が効率的ですが、そのアプローチではかなりのスペースが無駄になる可能性があります（割り当てられたスペースの最大半分が未使用です）。1つずつ拡張するアプローチにはその欠点はありません。ただし、追加するたびに配列全体をコピーする必要があるのは実際には非効率的です。したがって、スペース効率が主な関心事である場合は、スタックをリンクリストとして表す方がよい場合があります。

Answer 3

それは壊れた質問です。どちらが「より効率的」かは、ドメインによって異なります。長さ3と4のスタックがたくさんある場合は、前もって10を割り当て、その後5年間寝ると、1から始めて2倍にするよりも速くなります。長さ1のスタックがたくさんある場合は、10を割り当てるのは無駄です。

もちろん、私が「無駄」と言うとき、私はあなたが二度と取り戻すことができないであろう数ナノ秒の無駄を意味します。あなたが「通常の」コンピュータを使用していて、コンウェイのライフゲームやその他の異常なものにCを実装していないと仮定すると、これらの割り当てが問題になる可能性があります。だから、それをプロファイリングして調べてください。

シンプルで効果的である可能性が高いものが必要な場合は、前もって10を割り当て、その後必要に応じて2倍にします。

Answer 4

必要に応じてスタックサイズを2倍にすることの償却コストは、1に初期化するよりもはるかに低くなります。したがって、2倍の方が優れています。そうは言っても、適切な削除スキームもお勧めします。現在のスタックの1/4が使用されているときに、スタックの半分を解放するという方針に沿った何か。このように、エッジの加算と減算は効率を損なうものではありません。