drba1172
drba1172
2011-01-16 06:27

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

  • heap
已采纳

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, "
", -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
", 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() { // 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条回答

  • dpwgzi7987 dpwgzi7987 10年前
    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)
    
    点赞 评论 复制链接分享

为你推荐