1

ネイティブスタックタイプを持たないあいまいな言語を使用しているので、独自の言語を実装しました。今、ネットで読んで、私はこれを行うためのいくつかの異なるアプローチを見つけました。

これは私の実装です（疑似コード）

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

値をポップした後にrealloc（）呼び出しを使用してスタックのサイズを変更すると、パフォーマンスが低下すると言う人もいるので、いくつか質問があります。

  1. mallocを使用してスタックを拡張し、プログラムの最後に解放するのが最善ですか？
  2. スタックのサイズを変更（プッシュ）するには、4バイト以上増やすのが最適ですか？
  3. いっぱいになったときに割り当てられたメモリを2倍にして、スタックを増やすのがベストプラクティスですか？
  4. 上記のコードについてどう思いますか？
4

3 に答える 3

3

標準的な手法では、サイズを2倍に拡大し、メモリの有効使用量が4分の1未満の場合にのみ縮小します。

このようにして、O（必要なメモリ）を超えて使用しないことを確認できます。また、スタックが一定時間償却されていることを証明することもできます。

（このように見てください。スタックに出入りするアイテムごとに3セントを支払います。そのうちの2つは、次に行われるコピー時に使用されます。）

詳細を説明しているウィキペディアの記事へのリンク

于 2009-08-06T15:23:55.497 に答える
0

一度に4バイトずつ拡大および縮小しないでください。ヒープは非常に断片化され、アロケータで多くの時間を費やします。メモリが制限されたアーキテクチャであっても、そのようなメモリを細かく管理することは望ましくありません。

「ページサイズ」を選択し、その量だけインクリメントします。サイズを2倍にすることをお勧めするのが一般的ですが、それがなぜであるかはわかりません。サイズをインクリメントするのに最適な方法を理解するために、スタックがどのように使用されるかについては、おそらくもっと知っているでしょう。

于 2009-08-06T15:26:47.847 に答える
0

人気のあるライブラリに実装されているほとんどすべての可変サイズの構造は、常に再割り当てを回避するためにいくつかの小さな最適化を行います。通常、データを大きくするにはデータをコピーする必要があることに注意してください。

通常、それはより大きな量で成長します。一般的な戦略は、ある限界に達するまでサイズを2倍にしてから、そこで一定量だけ成長させることです。縮小する場合は、サイズの半分以上が無駄になるまでサイズを変更する必要はありません。

OTOH、いくつかのrealloc（）実装は、すでにカーテンの後ろでそれを行っています。悲しいかな、私はあなたの「あいまいな言語」がそれをするのではないかと疑っています...

于 2009-08-06T15:26:52.793 に答える