在Golang中使用两个不同的优先队列

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

Using two different priority queues in Golang

问题

我是一个Gopher新手。最近我遇到了一个关于在Golang中实现优先队列的问题。我查看了https://pkg.go.dev/container/heap@go1.17.3来实现一个优先队列。你只需要为容器实现heap.Interface接口即可。这部分很简单,我没有问题。

但是我的问题是:
我需要两个优先队列,一个是最小优先队列,一个是最大优先队列。在Java中,这很容易实现。我只需要在初始化时更改比较器就可以了。
在Golang中,我只需要更改sort.Interface中的Less方法,这也可以。然而,我不想写重复的代码,我正在寻找更简洁的方法来创建这两个优先队列。

这里有一个我想要实现的示例:

// 最小优先队列

type PriorityQueue1 []*Item

// 为最小优先队列实现以下所有方法
func (pq PriorityQueue1) Len() int { return len(pq) }

func (pq PriorityQueue1) Less(i, j int) bool {
	// 我们希望Pop方法返回最高优先级的元素,所以这里使用大于号。
	return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue1) Swap(i, j int) {
  // 交换元素
}

func (pq *PriorityQueue1) Push(x interface{}) {
  // 定义push逻辑
}

func (pq *PriorityQueue1) Pop() interface{} {
  // 定义pop逻辑
}

现在我定义了最大优先队列**除了Less方法之外其他都相同**),如下所示

// 最大优先队列

type PriorityQueue2 []*Item

// 为最大优先队列实现以下所有方法
func (pq PriorityQueue2) Len() int { return len(pq) }

func (pq PriorityQueue2) Less(i, j int) bool {
	return **pq[i].priority < pq[j].priority**  // 只有一行代码不同
}

func (pq PriorityQueue2) Swap(i, j int) {
  // 交换元素
}

func (pq *PriorityQueue2) Push(x interface{}) {
  // 定义push逻辑
}

func (pq *PriorityQueue2) Pop() interface{} {
  // 定义pop逻辑
}

现在,为了只改变Less方法的一行代码,我为最大优先队列重新编写了几乎相同的方法。我想要减少这种重复的模板代码,我想知道解决这个问题的最简洁和简洁的方法。我不想使用任何第三方库(但如果有提供干净封装的库,我对其逻辑感兴趣)。

请提供一些建议。谢谢。

英文:

I am a Gopher Noob. I ran into this question recently regarding implementing priority queues in Golang. I went through https://pkg.go.dev/container/heap@go1.17.3 for implementing a priority queue. All one has to do is implement the heap.Interface for the container. Its straightforward enough and i have no questions about that.

My question though is this:
I need two priority queues. One is a minimum and maximum priority queue. In Java, this is quiet easy is initialize. I just have to change the comparator during initialization and thats it.
In golang, I simply have to change the Less method in sort.Interface which is fine. However, I am not interested in writing redundant code and i am looking for cleaner way to create both priority queues.

Here is an example for what i am looking to do:

// A PriorityQueue1

type PriorityQueue1 []*Item

// Implement all the following methods for the min Prioirity queue
func (pq PriorityQueue1) Len() int { return len(pq) }

func (pq PriorityQueue1) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority &gt; pq[j].priority
}

func (pq PriorityQueue1) Swap(i, j int) {
  //Swap
}

func (pq *PriorityQueue1) Push(x interface{}) {
  //Define push logic
}

func (pq *PriorityQueue1) Pop() interface{} {
  //Define pop logic
}

Now, I define the maximum priority queue (**everything is the same except Less**), which goes like this.. 

// A PriorityQueue2

type PriorityQueue2 []*Item

// Implement all the following methods for the max Prioirity queue
func (pq PriorityQueue2) Len() int { return len(pq) }

func (pq PriorityQueue2) Less(i, j int) bool {
	return **pq[i].priority &lt; pq[j].priority**  // Thats it. One line change..
}

func (pq PriorityQueue2) Swap(i, j int) {
  //Swap
}

func (pq *PriorityQueue2) Push(x interface{}) {
  //Define push logic
}

func (pq *PriorityQueue2) Pop() interface{} {
  //Define pop logic
}

Now why would i have to go through this ordeal of rewriting almost the same methods as that of the min queue for a one line change in Less. I am looking to reduce the boilerplate and i am wondering about what is the cleanest and concise way to go about solving this question. I am also not interested in using any third party libraries (but i am interested in its logic if there is one which provides a clean wrapper).

Please provide some inputs. Thanks..

答案1

得分: 1

你可以将该函数作为构造函数的依赖注入到Priority Queue结构体中。

它应该按照以下方式工作:

type Item int

type PriorityQueue []Item

var lesser LessFunction

func GetPriorityQueue(l LessFunction) PriorityQueue {
    lesser = l
    return []Item{}
}

type LessFunction func(i, j int) bool

func (pq PriorityQueue) Less(i, j int) bool {
    return lesser(i, j)
}

在代码中使用如下:

q := GetPriorityQueue(func(i, j int) bool { return i < j })

请注意:
除了我展示的方法之外,还有多种方法可以解决这个问题。这种方法显示了与Java的lambda函数的相似之处。

英文:

You can inject the function as a dependency to the constructor for the Priority Queue struct.

It should work as follows:

type Item int

type PriorityQueue []Item

var lesser LessFunction

func GetPriorityQueue(l LessFunction) PriorityQueue {
	lesser = l
	return []Item{}
}

type LessFunction func(i, j int) bool

func (pq PriorityQueue) Less(i, j int) bool {
	return lesser(i, j)
}

Use this in code as follows:

q := GetPriorityQueue(func(i, j int) bool { return i &lt; j })

Please note:
There are multiple ways you can tackle this apart from what I have shown. This shows the similarity to Java's lambda functions.

huangapple
  • 本文由 发表于 2021年11月29日 14:08:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/70150386.html
匿名

发表评论

匿名网友

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

确定