实现动态堆栈类型的最佳方法？ 或者我滥用 realloc 吗？
我使用的是一种晦涩的语言，没有本地堆栈类型，所以我实现了自己的。 现在，在网上阅读时，我发现了几种不同的方法来做到这一点。
这是我的实现（伪代码）
//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() 调用来调整堆栈大小对性能不利，所以我有几个问题：
- 最好是使用 malloc 然后 free 来增加堆栈在程序结束时吗？
- 要调整堆栈大小（推送），最好增加 4 个字节或更多吗？
- 最佳实践是通过在填充时分配的内存加倍来增加堆栈吗？
- 您对上面的代码有何看法？
I'm using an obscure language that doesn't have a native stack type so I've implemented my own. Now, reading on the net i've found a few different approaches to do this.
This is my implementation (psuedo code)
//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;
}
Now some people say that using a realloc() call to resize the stack after popping a value is bad for performance so i have a few questions:
- Is it best to just grow the stack using malloc then free it at program end?
- To resize the stack (push) is it best to increase by 4 bytes or more?
- Is it best practise to increase the stack by doubling the memory allocated when it's filled?
- What are your thoughts of the above code?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
标准技术是仅将大小增加 2 倍，并且仅当有效内存使用量小于四分之一时才缩小大小。
这样你就可以确保你使用的内存永远不会超过O（你需要的内存），并且你还可以证明堆栈是摊销常数时间的。
（这样看：您为进入或退出堆栈的每个项目支付三美分。其中两个将在下一次复制时使用。）
链接到维基百科文章，详细解释
The standard technique is to only grow the size by factor of 2, and to shrink it only when the effective memory use is less than quarter.
This way you can be sure that you never use more than O(the memory you need), and you can also prove that the stack is amortized constant time.
(look at it this way: You pay three cents for each item entering or exiting the stack. Two of them will be used during the next copying that will occur.)
Link to wikipedia article explaining in more details
绝对不要一次增加和缩小 4 个字节。 您的堆将变得非常分散，并且您将在分配器上花费太多时间。 即使在内存有限的体系结构上，您也不希望像这样对内存进行微观管理。
选择“页面大小”，然后按该值递增。 通常建议将大小加倍，但我不确定为什么会这样。 您可能更了解如何使用堆栈，以了解如何最好地增加大小。
Definitely don't grow and shrink 4 bytes at a time. Your heap will become very fragmented, and you'll spend too much time in the allocator. Even on a memory-limited architecture, you don't want to be micro-managing memory like that.
Choose a "page size", and increment by that amount. It's common to recommend doubling the size, but I'm not sure why that is. You probably know more about how the stack will be used to understand how best to increment the size.
流行库中实现的几乎每个可变大小结构都会进行一些小的优化，以避免一直重新分配。 请记住，它通常必须复制数据才能使其更大。
通常它的增长量会更大。 一个常见的策略是将大小加倍，直到达到某个限制，然后再以固定的量增长。 对于缩小，不必担心调整大小，直到浪费了一半以上的大小。
OTOH，一些 realloc() 实现已经在幕后为您做到了这一点。 唉，我怀疑你的“晦涩语言”能做到这一点......
Almost every variable-size structure implemented in popular libraries do some small optimisations to avoid reallocing all the time. Remember that it usually has to copy the data to make it bigger.
Usually it grows by bigger amounts. a common strategy is to double size until if reaches some limit, and then grow by a fixed amount over there. and for shrinking, don't worry to resize until it's wasting more than half the size.
OTOH, some realloc() implementations already do that for you behind curtains. alas, i doubt your 'obscure language' does it...