英文:
Queue implementation using slices in Go
问题
我看过一些使用切片实现的Go语言FIFO队列的实现。当项目从队列中退出时，是否可以释放这些内存而不重新分配底层数组？如果不这样做，似乎队列会泄漏大量内存。这是我的意思：
type queue struct {
data []int
head int
}
func (q *queue) enqueue(val int) {
q.data = append(q.data, val)
}
func (q *queue) dequeue() int {
val := q.data[q.head]
q.head++
return val
}
在调用enqueue/dequeue多次之后，切片底层数组的低索引不再可用，但我不确定如何释放它们。有人可以指导我一个不使用指针的正确队列实现吗？它不会像这样泄漏内存或者有性能问题。或者，也可以给我一个关于如何实现这个的描述。
谢谢，
Plamen
英文:
I have seen some implementations of FIFO Queues using slices in Go. As items exit the queue can this memory be freed up without reallocating the underlying array? If this doesn't occur it would seem to me that the queue would leak a ton of memory. This is what I mean:
type queue
{
[]int
int head
}
func (q *queue) enqueue(val int) {
q = append(q, val)
}
func (q *queue) dequeue() int {
return (*q)[q.head++]
}
After calling enqueue/dequeue a bunch of times, the low indexes of the array underying the slice are no longer usable but I am not sure how they can be freed either. Can someone point me to a proper queue implementation that does not use pointers, and doesn't leak memory like this or have performance issues? Alternatively a description of how this might work would also be appreciated.
Thank you,
Plamen
答案1
得分: 2
你可以使用循环缓冲区（circular buffer）。从维基百科上可以找到相关信息：
循环缓冲区、循环队列、循环缓存或环形缓冲区是一种数据结构，它使用一个固定大小的缓冲区，就像它们是首尾相连一样。这种结构非常适合缓冲数据流。
...
循环缓冲区是一个非常理想的队列实现策略，适用于具有固定最大大小的队列。如果队列采用了最大大小，那么循环缓冲区是一个完全理想的实现；所有队列操作都是常数时间。然而，扩展循环缓冲区需要移动内存，这相对来说是比较昂贵的。对于任意扩展的队列，可能更倾向于使用链表方法。
这里有一个实现循环缓冲区的包：https://github.com/eapache/queue。
根据使用情况，通道（channel）也是实现队列的一种好方法。它会阻塞，但是使用带有默认情况的 select 语句可以避免这种行为：
select {
case msg := <-queue:
default:
}
英文:
You can use a circular buffer. From wikipedia:
> A circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.
>
> ...
>
> Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a linked list approach may be preferred instead.
Here's a package that implements this: https://github.com/eapache/queue.
Depending on the use case, a channel is also a good way to implement a queue. It blocks, but using a select with a default you can avoid that behavior:
select {
case msg := <-queue:
default:
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论