英文:
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 && n.col == o.col
}
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)
}
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
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 "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
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
}
答案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
:在函数参数中隐式赋值未导出字段row
的pqueue.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 &Node{}
}
In PQueue.go
, add this function to package pqueue
:
func NewPQueue() *PQueue {
return &PQueue{}
}
Then. in package main
, you can write:
PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论