使用容器/堆来实现优先队列

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

Using a container/heap to implement a priority queue

问题

在大局观中,我正在尝试使用优先队列实现Dijkstra算法。

根据golang-nuts成员的说法,在Go语言中,使用自定义底层数据结构的堆接口是一种惯用的方法。所以我创建了Node.go和PQueue.go文件,如下所示:

//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
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
// 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

}

编译时出现错误信息:

[~/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)这一行可以通过编译。但我不明白为什么会出现这个错误信息。Push函数不会以任何方式修改参数。

英文:

In the big picture, I'm trying to implement Dijkstra's algorithm using a priority queue.

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 &amp;&amp; n.col == o.col
}

And PQueue.go:

// PQueue.go
package pqueue

import &quot;container/vector&quot;
import &quot;container/heap&quot;

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) &lt; (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)
}

And main.go: (the action is in SolveMatrix)

// Euler 81

package main

import &quot;fmt&quot;
import &quot;io/ioutil&quot;
import &quot;strings&quot;
import &quot;strconv&quot;
import &quot;./pqueue&quot;

const MATSIZE = 5
const MATNAME = &quot;matrix_small.txt&quot;

func main() {
	var matrix [MATSIZE][MATSIZE]int
	contents, err := ioutil.ReadFile(MATNAME)
	if err != nil {
		panic(&quot;FILE IO ERROR!&quot;)
	}
	inFileStr := string(contents)
	byrows := strings.Split(inFileStr, &quot;\n&quot;, -1)

	for row := 0; row &lt; MATSIZE; row++ {
		byrows[row] = (byrows[row])[0 : len(byrows[row])-1]
		bycols := strings.Split(byrows[row], &quot;,&quot;, -1)
		for col := 0; col &lt; MATSIZE; col++ {
			matrix[row][col], _ = strconv.Atoi(bycols[col])
		}
	}

	PrintMatrix(matrix)
	sum, len := SolveMatrix(matrix)
	fmt.Printf(&quot;len: %d, sum: %d\n&quot;, len, sum)
}

func PrintMatrix(mat [MATSIZE][MATSIZE]int) {
	for r := 0; r &lt; MATSIZE; r++ {
		for c := 0; c &lt; MATSIZE; c++ {
			fmt.Printf(&quot;%d &quot;, mat[r][c])
		}
		fmt.Print(&quot;\n&quot;)
	}
}

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(&quot;empty&quot;)
	}

	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 &#39;row&#39; of pqueue.Node in function argument
make: *** [all] Error 1

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.


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 &quot;fmt&quot;

type Node struct {
	row    int
	col    int
	myVal  int
	sumVal int
	parent *Node
}

func NewNode(r, c, mv, sv int, n *Node) *Node {
	return &amp;Node{r, c, mv, sv, n}
}

func (n *Node) Eq(o *Node) bool {
	return n.row == o.row &amp;&amp; n.col == o.col
}

func (n *Node) String() string {
	return fmt.Sprintf(&quot;{%d, %d, %d, %d}&quot;, 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
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) &lt; (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 = &quot;{&quot;
	for _, v := range *pq {
		build += v.String()
	}
	build += &quot;}&quot;
	return build
}

答案1

得分: 5

package main
var PQ pqueue.PQueue
var firstNode pqueue.Node
PQ.Push(firstNode)

变量firstNode是按值传递的,这意味着在函数调用PQ.Push(firstNode)中,参数会隐式赋值给参数。类型pqueue.Node包含了私有字段,例如row,这些字段未从package pqueue导出到package main:在函数参数中隐式赋值未导出字段rowpqueue.Node

Node.go中,将此函数添加到package pqueue

func NewNode() *Node {
return &Node{}
}

PQueue.go中,将此函数添加到package pqueue

func NewPQueue() *PQueue {
return &PQueue{}
}

然后,在package main中,你可以写:

PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)

英文:
package main
var PQ pqueue.PQueue
var firstNode pqueue.Node
PQ.Push(firstNode)

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."

In Node.go, add this function to package pqueue:

func NewNode() *Node {
	return &amp;Node{}
}

In PQueue.go, add this function to package pqueue:

func NewPQueue() *PQueue {
	return &amp;PQueue{}
}

Then. in package main, you can write:

PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)

huangapple
  • 本文由 发表于 2011年1月16日 14:27:08
  • 转载请务必保留本文链接:https://go.coder-hub.com/4704144.html
匿名

发表评论

匿名网友

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

确定