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. 通过在填充时分配的内存加倍来增加堆栈是最佳实践吗？
  4. 你对上面的代码有什么想法？
4

3 回答 3

3

标准技术是仅将大小增加 2 倍，并仅在有效内存使用量小于四分之一时缩小。

通过这种方式，您可以确保您使用的内存永远不会超过 O（您需要的内存），并且您还可以证明堆栈是摊销的常数时间。

（这样看：您为每个进入或退出堆栈的项目支付 3 美分。其中两个将在下一次复制时使用。）

链接到维基百科文章，详细解释

于 2009-08-06T15:23:55.497 回答
0

绝对不要一次增长和缩小 4 个字节。你的堆会变得非常碎片化，你会在分配器上花费太多时间。即使在内存有限的架构上，您也不希望像那样对内存进行微观管理。

选择“页面大小”，并按该数量递增。通常建议将尺寸加倍，但我不确定为什么会这样。您可能更了解如何使用堆栈来了解如何最好地增加大小。

于 2009-08-06T15:26:47.847 回答
0

流行库中实现的几乎每个可变大小结构都进行了一些小的优化，以避免一直重新分配。请记住，它通常必须复制数据以使其更大。

通常它会以更大的数量增长。一个常见的策略是将大小加倍，直到达到某个限制，然后在那里增长一个固定的数量。并且对于缩小，不要担心调整大小，直到它浪费了一半以上的大小。

OTOH，一些 realloc() 实现已经在幕后为您做到了。唉，我怀疑你的“晦涩的语言”能做到……

于 2009-08-06T15:26:52.793 回答