将Go的heap.Interface翻译为一个结构体。

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

Go heap.Interface as a struct

问题

我正在使用Go的heap包创建一个优先队列。文档中有一个示例

我创建的队列需要基于一个结构体,而不是一个切片,因为它需要其他属性,比如互斥锁。

type PQueue struct {
    queue []*Item
    sync.Mutex
}

我实现了所有heap.Interface要求的方法。

问题是,我的PQueue.Push方法似乎不能永久地将一个值添加到PQueue.queue中。

func (p PQueue) Push(x interface{}) {
    p.Lock()
    defer p.Unlock()
    item := x.(*Item)
    item.place = len(p.queue) // 队列中的项的索引
    p.queue = append(p.queue, item)
    // len(p.queue) 确实增加了
    // 但是在函数退出后,队列的长度没有增加
}

如果我在函数的最后打印p.queue的长度,长度确实增加了。然而,在函数退出后,原始结构似乎没有被更新。

我认为这可能是因为func (p PQueue)不是一个指针。为什么会这样?有没有办法修复它?如果我改用func (p *PQeueue) Push(x interface{}),那么我就需要实现自己的堆,因为heap.Interface要求不使用指针。这是我的唯一选择吗?

英文:

I'm creating a priority queue using Go's heap package. There is an example of one in the documentation.

The queue I'm creating needs to be based around a struct rather than a slice because it requires other properties like a mutex.

type PQueue struct {
    queue []*Item
    sync.Mutex
}

I implement all the methods that heap.Interface requires.

The issue is that my PQueue.Push method seems not to be permanently adding a value to PQueue.queue.

func (p PQueue) Push(x interface{}) {
    p.Lock()
    defer p.Unlock()
    item := x.(*Item)
    item.place = len(p.queue) // the index of an item in the queue
    p.queue = append(p.queue, item)
    // len(p.queue) does increase
    // after the functions exits, the queues length has not increased
}

If I print the length of p.queue at the end of this function, the length has increased. After the functions exits however, it seems the original struct does not get updated.

I think it might be happening because of func (p PQueue) not being a pointer. Why might that be? Is there a way to fix it? If I were to use func (p *PQeueue) Push(x interface{}) instead, I would need to implement my own heap because heap.Interface specifically requires no pointer. Is that my only option?

答案1

得分: 3

问题在于你在一个副本的切片上进行了追加操作。因此,修改只在函数内部显示,但在函数返回后就会丢失。

这篇博文将切片传递给函数部分中:

> 需要明白的是,尽管切片包含一个指针,但它本身是一个值。在底层,它是一个包含指针和长度的结构体值。它不是指向结构体的指针。

使用append时,你修改的是切片的头部。

> 因此,如果我们想要编写一个修改头部的函数,我们必须将其作为结果参数返回。

或者:

> 另一种修改切片头部的方法是将指针传递给它。

因此,如果你想要使用append进行修改,你需要传递一个指针。只需将方法更改为使用指针接收器。为了使其工作,你需要使用指针调用init,例如heap.Init(&pq),就像你链接的示例中所示,它也使用了指针接收器。

根据规范中的方法集

> 相应指针类型 *T 的方法集是所有声明了接收器 *T 或 T 的方法集合(也就是说,它还包含 T 的方法集)。

因此,使用指针类型将适用于值接收器和指针接收器,并且仍然实现接口。

英文:

The problem is that you are appending to a copy of your slice. Thus the change shows within the function, but is lost once you return from the function.

In this blog article from the section Passing slices to functions:

> It's important to understand that even though a slice contains a
> pointer, it is itself a value. Under the covers, it is a struct value
> holding a pointer and a length. It is not a pointer to a struct.

With append you are modifying the slice header. And

> Thus if we want to write a function that modifies the header, we must
> return it as a result parameter

Or:

> Another way to have a function modify the slice header is to pass a
> pointer to it.

As a result you need to pass a pointer if you want to modify it with append. Simply change the method to use a pointer receiver. And for that to work you need to call init with a pointer like heap.Init(&pq) as shown in the example that you linked to which does just that and also uses pointer receivers.

From the spec on Method Sets:

> The method set of the corresponding pointer type *T is the set of all methods
> declared with receiver *T or T (that is, it also contains the method
> set of T).

So using a pointer type will work with value and pointer receivers and still implement the interface.

答案2

得分: 2

你对问题与你的Push方法的接收者有关的观点是正确的:该方法将接收PQueue的副本,因此对结构体所做的任何更改都不会持久保存。

将方法更改为使用指针作为接收者是正确的更改,但这也意味着PQueue不再实现heap.Interface。这是因为Go语言不允许你获取接口变量内部存储值的指针,所以q.Push()自动转换为(&q).Push()不会发生。

不过这并不是死胡同,因为*PQueue仍然应该实现heap.Interface。所以如果你之前调用了heap.Init(q),只需将其更改为heap.Init(&q)即可。

英文:

You are right about the problem being related to the receiver of your Push method: the method will receive a copy of the PQueue, so any changes made to the struct will not persist.

Changing the method to use a pointer as a receiver is the correct change, but this also means that PQueue no longer implements heap.Interface. This is due to the fact that Go does not let you take a pointer to the value stored inside an interface variable, so the automatic translation of q.Push() to (&q).Push() does not occur.

This isn't a dead end though, since *PQueue should still implement the heap.Interface. So if you were previously calling heap.Init(q), just change it to heap.Init(&q).

答案3

得分: 0

这是翻译好的内容:

我认为这可能是因为func (p PQueue)不是一个指针而导致的。

没错。引用《Effective Go》的说法:

在值上调用方法会导致方法接收到该值的副本,所以任何修改都会被丢弃。

你说:

heap.Interface明确要求不使用指针。

我有点困惑,你指向的示例实际上是使用指针的:

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

也许还有其他问题?

英文:

> I think it might be happening because of func (p PQueue) not being a pointer

That's right. Quoting Effective Go:

> invoking [the method] on a value would cause the method to receive a
> copy of the value, so any modifications would be discarded.

You say:
> heap.Interface specifically requires no pointer

I'm confused, the example you point to is, in fact, using a pointer:

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

Maybe something else is going on?
1: http://golang.org/doc/effective_go.html#pointers_vs_values

huangapple
  • 本文由 发表于 2015年5月28日 11:19:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/30496639.html
匿名

发表评论

匿名网友

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

确定