5
Nell'immagine grande, sto cercando di implementare l'algoritmo di Dijkstra utilizzando una coda di priorità.Go: utilizzo di un contenitore/heap per l'implementazione di una coda di priorità
Secondo i membri di golang-nuts, il modo idiomatico per farlo in Go è utilizzare l'interfaccia heap con una struttura dati sottostante personalizzata. Così ho creato Node.go e PQueue.go in questo modo:
//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
}
E 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)
}
E main.go: (l'azione è 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
}
il problema è che al momento la compilazione ottengo il messaggio di errore:
[~/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
E commentando la riga PQ.Push (firstNode) soddisfa il compilatore. Ma non capisco perché sto ricevendo il messaggio di errore in primo luogo. Push non modifica l'argomento in alcun modo.
UPDATE: Per il bene di coloro che vengono in questo nelle ricerche in futuro, il codice di cui sopra è pieno zeppo di idee sbagliate lordi. Date un'occhiata qui sotto per un modello molto più utile per lavorare fuori di: 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
}