转到 - 使用容器/堆实现优先级队列 [英] Go - Using a container/heap to implement a priority queue

问题描述

总的来说，我试图使用优先级队列来实现Dijkstra的算法。

根据golang-nuts的成员，在Go中执行此操作的惯用方式是使用具有自定义底层数据结构的堆接口。所以我创建了Node.go和PQueue.go，如下所示：

  // Node.go 
包pqueue 
 
类型节点struct {
行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：

  // PQueue.go 
包pqueue 
 
导入container / vector
 importcontainer / 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 
 
 $ b func（pq * PQueue）Push（i interface {}）{
 heap.Push（pq，i）
 pq.size ++ 
 } 
 
 func（pq * PQueue）Pop（）接口{} {
 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中）

  // Euler 81 
 
软件包主要
 
导入fmt
导入io / ioutil 
 importstrings
 importstrconv
 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）
yrows：= strings.Split（inFileStr，\\\
， - 1）行
 
 = 0;行< MATSIZE; row ++ {
 byrows [row] =（byrows [row]）[0：len（byrows [row]） -  1] 
 bycols：= strings.Split（byrows [row]，， -1）
为col：= 0; col< MATSIZE; col ++ {
 matrix [row] [col]，_ = strconv.Atoi（bycols [col]）
} 
} 
 
 PrintMatrix（矩阵）
 sum，len：= SolveMatrix（矩阵）
 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（\\\
）
} 
} 
 
 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（）{//编译器关于未使用的变量stfu 
 fmt.Print（empty）
 
 
 PQ.Push（firstNode）//问题
 
 
返回0，0 
} 
  
  
 $ b 
问题是，在编译时我得到错误信息： 
 
 
  [〜/ Code / Euler / 81] $ make 
 6g -o pqueue.6 Node.go PQueue.go 
 6g main.go 
 main.go：58 ：在函数参数
中隐式赋值pqueue.Node的未导出的字段行：make [***]错误1 
  
并发表评论出PQ.Push（firstNode）确实符合编译器。但我不明白为什么我首先得到错误信息。推并不以任何方式修改参数。  
 
 
 
 
 
更新：
为了未来在搜索中遇到这种情况，充满了严重的误解。请看下面的一个更实用的模板：
 Node.go： 
 
 
  //节点.go 
包pqueue 
 
导入fmt
 
类型节点struct {
行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）等式（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 {
返回n.row 
} 
 
 func（n * Node）Col（）int {
 return n.col 
} 
 
 func（n * Node）SetParent（p * Node）{
 n.parent = p 
} 
 
 func（n * Node）Parent（）* Node {
返回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 
 
类型PQueue [] *节点
 
 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 
 
 $ b 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 b 
 
 
 
解决方案
 
  package main 
 var PQ pqueue.PQueue 
 var firstNode pqueue.Node 
 PQ.Push（firstNode）
  
变量 firstNode 通过值传递，这意味着有一个隐含的参数赋值给参数in函数调用 PQ.Push（firstNode）。类型 pqueue.Node 包含不是从 package pqueue中导出的私有字段，例如 row   to  package main ：在函数参数中隐式赋值pqueue.Node的未导出字段'row'。
 
 
 
在 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）
  
 
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
}

解决方案
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)


                        
这篇关于转到 - 使用容器/堆实现优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！