Golang中的Peekable队列

huangapple go评论77阅读模式
英文:

Peekable Queue in Golang

问题

我正在尝试设计一种机制,以允许多个进程(goroutine)之间的合作。有两类进程 - 提供者和用户。提供者将其服务的“竞标”放入队列中,用户获取等待中的竞标并开始与提供者合作。然而,用户可能不喜欢一个竞标,这时应该发生两件事情:

  • 这个竞标应该返回到队列中,并且应该放在队列的开头
  • 用户应该得到队列中的下一个竞标

理想情况下,我希望避免一个协调提供者和用户之间通信的中央进程。另一种思考这个问题的方式是想象一个“可查看”的队列或通道。类似于AWS Kinesis的工作方式。读取器可以访问队列的头部进行“查看”。当读取器在查看时,其他读取器无法看到该项。如果读取器喜欢该项,那么它将从队列中移除。如果不喜欢,读取器释放该项上的锁,另一个读取器可以进行查看。

有没有什么想法如何在Go中使用通道和goroutine来最好地实现这种行为?

英文:

I am trying to design a mechanism to allow cooperation of many processes – goroutines. There are two classes of processes – providers and users. Providers put “bids” for their services into a queue and users take waiting bids and start working with providers. However, a user may not like a bid and then two things should happen:

  • This bid should return to the queue. It should be placed at the beginning of the queue
  • The user should be given the next bid in the queue

Ideally, I would like to avoid a central process that coordinates the communication between providers and users.
Another way of thinking about this problem is to imagine a “peekable” queue or channel. A concept similar to the way AWS Kinesis works. A reader can get an access to “peek” into the head of the queue. As this reader is peeking, no other readers can see the item. It the reader likes the item, then it removes it from the queue. If not the reader releases the lock on the item and another reader can peek.

Any ideas how to best implement this behavior in Go using channels and goroutines?

答案1

得分: 1

根据@DaveC在他的评论中所说,最简单和最快的方法是使用互斥锁(mutex)。

你可以使用"container/list"包,它为你实现了一个双向链表。这个链表可以从两端进行推入和弹出。

下面是一个快速实现,它实现了我认为你所要求的功能:

import (
	"container/list"
	"sync"
)

type Queue struct {
	q list.List
	l sync.Mutex
}

func (q *Queue) Push(data interface{}) {
	q.l.Lock()
	q.q.PushBack(data)
	q.l.Unlock()
}

func (q *Queue) Pop() interface{} {
	q.l.Lock()
	data := q.q.Remove(q.q.Front())
	q.l.Unlock()
	return data
}

func (q *Queue) TakeAnother(data interface{}) interface{} {
	q.l.Lock()
	e := q.q.Front()
	// 将数据与列表前端的数据交换
	e.Value, data = data, e.Value
	q.l.Unlock()
	return data
}

我没有使用通道或goroutine,因为我认为它们不是这个任务的正确工具。

英文:

As @DaveC states in his comment, the simplest and fastest way to do this is to use a mutex.

You could use the "container/list" package, which implements a double-linked list for you. This can be pushed/popped from both ends.

Here is a quick implementation that does what I think you are asking:

import (
	"container/list"
	"sync"
)

type Queue struct {
	q list.List
	l sync.Mutex
}

func (q *Queue) Push(data interface{}) {
	q.l.Lock()
	q.q.PushBack(data)
	q.l.Unlock()
}

func (q *Queue) Pop() interface{} {
	q.l.Lock()
	data := q.q.Remove(q.q.Front())
	q.l.Unlock()
	return data
}

func (q *Queue) TakeAnother(data interface{}) interface{} {
	q.l.Lock()
	e := q.q.Front()
	// swap the data with whatever is in the front of the list
	e.Value, data = data, e.Value
	q.l.Unlock()
	return data
}

Nowhere do I use channels or goroutines, since I don't think they are the correct tool for this job.

huangapple
  • 本文由 发表于 2015年6月12日 09:31:52
  • 转载请务必保留本文链接:https://go.coder-hub.com/30794018.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定