使用容器/堆实现优先级队列 [英] Using a container/heap to implement a priority queue
问题描述
总的来说，我正在尝试使用优先级队列来实现Dijkstra的算法.
In the big picture, I'm trying to implement Dijkstra's algorithm using a priority queue.
根据golang-nuts的成员，Go中惯用的方法是使用带有自定义基础数据结构的堆接口.所以我像这样创建了Node.go和PQueue.go:
According to members of golang-nuts, the idiomatic way to do this in Go is to use the heap interface with a custom underlying data structure. So I have created Node.go and PQueue.go like so:
//Node.go
package pqueue
type Node struct {
row int
col int
myVal int
sumVal int
}
func (n *Node) Init(r, c, mv, sv int) {
n.row = r
n.col = c
n.myVal = mv
n.sumVal = sv
}
func (n *Node) Equals(o *Node) bool {
return n.row == o.row && n.col == o.col
}
和PQueue.go:
And PQueue.go:
// PQueue.go
package pqueue
import "container/vector"
import "container/heap"
type PQueue struct {
data vector.Vector
size int
}
func (pq *PQueue) Init() {
heap.Init(pq)
}
func (pq *PQueue) IsEmpty() bool {
return pq.size == 0
}
func (pq *PQueue) Push(i interface{}) {
heap.Push(pq, i)
pq.size++
}
func (pq *PQueue) Pop() interface{} {
pq.size--
return heap.Pop(pq)
}
func (pq *PQueue) Len() int {
return pq.size
}
func (pq *PQueue) Less(i, j int) bool {
I := pq.data.At(i).(Node)
J := pq.data.At(j).(Node)
return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}
func (pq *PQueue) Swap(i, j int) {
temp := pq.data.At(i).(Node)
pq.data.Set(i, pq.data.At(j).(Node))
pq.data.Set(j, temp)
}
main.go :(操作在SolveMatrix中)
And main.go: (the action is in SolveMatrix)
// Euler 81
package main
import "fmt"
import "io/ioutil"
import "strings"
import "strconv"
import "./pqueue"
const MATSIZE = 5
const MATNAME = "matrix_small.txt"
func main() {
var matrix [MATSIZE][MATSIZE]int
contents, err := ioutil.ReadFile(MATNAME)
if err != nil {
panic("FILE IO ERROR!")
}
inFileStr := string(contents)
byrows := strings.Split(inFileStr, "\n", -1)
for row := 0; row < MATSIZE; row++ {
byrows[row] = (byrows[row])[0 : len(byrows[row])-1]
bycols := strings.Split(byrows[row], ",", -1)
for col := 0; col < MATSIZE; col++ {
matrix[row][col], _ = strconv.Atoi(bycols[col])
}
}
PrintMatrix(matrix)
sum, len := SolveMatrix(matrix)
fmt.Printf("len: %d, sum: %d\n", len, sum)
}
func PrintMatrix(mat [MATSIZE][MATSIZE]int) {
for r := 0; r < MATSIZE; r++ {
for c := 0; c < MATSIZE; c++ {
fmt.Printf("%d ", mat[r][c])
}
fmt.Print("\n")
}
}
func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
var PQ pqueue.PQueue
var firstNode pqueue.Node
var endNode pqueue.Node
msm1 := MATSIZE - 1
firstNode.Init(0, 0, mat[0][0], 0)
endNode.Init(msm1, msm1, mat[msm1][msm1], 0)
if PQ.IsEmpty() { // make compiler stfu about unused variable
fmt.Print("empty")
}
PQ.Push(firstNode) // problem
return 0, 0
}
问题是，在编译时我收到错误消息:
The problem is, upon compiling i get the error message:
[~/Code/Euler/81] $ make
6g -o pqueue.6 Node.go PQueue.go
6g main.go
main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument
make: *** [all] Error 1
并注释掉PQ.Push(firstNode)行确实使编译器满意.但是我不明白为什么我会首先收到错误消息.推送不会以任何方式修改参数.
And commenting out the line PQ.Push(firstNode) does satisfy the compiler. But I don't understand why I'm getting the error message in the first place. Push doesn't modify the argument in any way.
更新: 为了将来在搜索中遇到此问题的人，上面的代码充满了严重的误解.请在下面查看可使用的更有用的模板: Node.go:
UPDATE: For the sake of those who come across this in searches in the future, the code above is chock full of gross misconceptions. Take a look below for a much more useful template to work off of: Node.go:
// Node.go
package pqueue
import "fmt"
type Node struct {
row int
col int
myVal int
sumVal int
parent *Node
}
func NewNode(r, c, mv, sv int, n *Node) *Node {
return &Node{r, c, mv, sv, n}
}
func (n *Node) Eq(o *Node) bool {
return n.row == o.row && n.col == o.col
}
func (n *Node) String() string {
return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal)
}
func (n *Node) Row() int {
return n.row
}
func (n *Node) Col() int {
return n.col
}
func (n *Node) SetParent(p *Node) {
n.parent = p
}
func (n *Node) Parent() *Node {
return n.parent
}
func (n *Node) MyVal() int {
return n.myVal
}
func (n *Node) SumVal() int {
return n.sumVal
}
func (n *Node) SetSumVal(sv int) {
n.sumVal = sv
}
PQueue.go:
PQueue.go:
// PQueue.go
package pqueue
type PQueue []*Node
func (pq *PQueue) IsEmpty() bool {
return len(*pq) == 0
}
func (pq *PQueue) Push(i interface{}) {
a := *pq
n := len(a)
a = a[0 : n+1]
r := i.(*Node)
a[n] = r
*pq = a
}
func (pq *PQueue) Pop() interface{} {
a := *pq
*pq = a[0 : len(a)-1]
r := a[len(a)-1]
return r
}
func (pq *PQueue) Len() int {
return len(*pq)
}
// post: true iff is i less than j
func (pq *PQueue) Less(i, j int) bool {
I := (*pq)[i]
J := (*pq)[j]
return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}
func (pq *PQueue) Swap(i, j int) {
(*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}
func (pq *PQueue) String() string {
var build string = "{"
for _, v := range *pq {
build += v.String()
}
build += "}"
return build
}
推荐答案
package main
var PQ pqueue.PQueue
var firstNode pqueue.Node
PQ.Push(firstNode)
变量firstNode由值传递，这意味着在函数调用PQ.Push(firstNode)中参数对参数的隐式分配.类型pqueue.Node包含诸如row之类的私有字段，这些私有字段不会从package pqueue导出到package main:在函数参数中隐式分配了pqueue.Node的未导出字段'row'."
The variable firstNode is passed by value which means that there is an implicit assignment of the argument to the parameter in the function call PQ.Push(firstNode). The type pqueue.Node contains private fields such as row which are not exported from package pqueue to package main: "implicit assignment of unexported field 'row' of pqueue.Node in function argument."
在Node.go中，将此功能添加到package pqueue:
In Node.go, add this function to package pqueue:
func NewNode() *Node {
return &Node{}
}
在PQueue.go中，将此功能添加到package pqueue:
In PQueue.go, add this function to package pqueue:
func NewPQueue() *PQueue {
return &PQueue{}
}
然后.在package main中，您可以编写:
Then. in package main, you can write:
PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)
这篇关于使用容器/堆实现优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
