Golang Cafe #13 まとめ containerパッケージ
2014/01/19に開催された「Golang Cafe #13」についてのまとめです。
今回はcontainerパッケージ以下をみていきました。サンプルコードは+TakashiYokoyama氏が準備してくれています。
containerパッケージ以下にはheap、list、ringの3つがあるのですが、heapだけは少し特殊です。
list、ringがパッケージ内で定義されているものを使用する（heapも最終的には使用します）のに対して、heapはパッケージ内にinterfaceが定義されていて自分で作った配列やリストでそのinterfaceを実装し、heapはパッケージ内で定義されている関数を使用する、という形になります。
私の書いたサンプルはGitHubに置いてあります。
heapパッケージ
heapは他の言語ではあまり耳にしませんが、いわゆる二分木構造です。よく試験で出てくるあれです。
PushしてPopすることでヒープソートをやってくれているようです。
+TakashiYokoyamaがサンプルを用意してくれていたのですが、パッケージドキュメントのExampleをもとにもう少し簡単なものでまとめておきます。
package main import ( "container/heap" "fmt" "math/rand" "time" ) // 独自の型を定義して、この型に heap interface を実装 type myIntArray []int func (h myIntArray) Len() int { return len(h) } func (h myIntArray) Less(i, j int) bool { return h[i] < h[j] } func (h myIntArray) Swap(i, j int) { //fmt.Printf("swap: %v <> %v\n", h[i], h[j]) h[i], h[j] = h[j], h[i] } func (h *myIntArray) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *myIntArray) Pop() interface{} { // if len(*m) == 0 { // return nil // } old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } func main() { m := &myIntArray{} rnd := rand.New(rand.NewSource(time.Now().Unix())) heap.Init(m) for i := 0; i < 10; i++ { v := rnd.Intn(100) fmt.Printf("push: %d\n", v) // 必ずheap経由でPush // NG: m.Push(v) heap.Push(m, v) } for _, v := range *m { fmt.Printf("%v ", v) } fmt.Println() for m.Len() > 0 { //fmt.Printf("pop: %v\n", *m) v1 := (*m)[0] // 必ずheap経由でPop // NG: v := m.Pop() v2 := heap.Pop(m) fmt.Printf("min: %v, pop : %v\n", v1, v2) } }
実行結果（環境によって異なります）は
$ go run sample01.go push: 89 push: 18 push: 3 push: 28 push: 82 push: 55 push: 44 push: 70 push: 48 push: 97 3 28 18 48 82 55 44 89 70 97 min: 3, pop : 3 min: 18, pop : 18 min: 28, pop : 28 min: 44, pop : 44 min: 48, pop : 48 min: 55, pop : 55 min: 70, pop : 70 min: 82, pop : 82 min: 89, pop : 89 min: 97, pop : 97
ポイントは、
- 準備として独自の配列型にheap.Interfaceを実装する
- heap.Init関数で初期化を行う
- 追加時はかならずheap.Push関数経由で、取得時は必ずheap.Pop関数経由で行う
- 配列の先頭が最小になる
くらいでしょうか。
独自の配列型に実装したPopメソッドやPushメソッで操作した場合ソートが行われません。heapパッケージの関数経由で操作した場合のみソートが行われます。
またheapパッケージの関数経由で操作した場合は配列の先頭が最小となりますが、配列全体が昇順に並び替えられているわけではありません。あくまでheap.Pop関数で取得した値または配列の先頭が最小値になります。
※このサンプルでは、Less、Swapメソッドで昇順に並べ替えるように実装しているので最小値が先頭になっています。
listパッケージ
listパッケージはJavaでいうArrayListやC#でいうListと同じようなものです。ただしGenericsはサポートされていません。
メソッドもドキュメントにあるように名前から想像出来る通りなので、気を付けておきたいところだけをまとめてみます。
package main import ( "fmt" "container/list" ) func main() { l := list.New() for i := 0; i < 10; i++ { l.PushBack(i) } fmt.Printf("要素数: %d\n", l.Len()) // e := l.Front() fmt.Printf("先頭 value: %v, prev: %v, next: %v\n", e.Value, e.Prev(), e.Next()) fmt.Printf("要素数: %d\n", l.Len()) // e = l.Back() fmt.Printf("最後 value: %v, prev: %v, next: %v\n", e.Value, e.Prev(), e.Next()) fmt.Printf("要素数: %d\n", l.Len()) // fmt.Println("リスト要素を列挙") for v := l.Front(); v != nil; v = v.Next() { fmt.Printf("%v ", v.Value) } fmt.Println() // fmt.Println("先頭を削除") e = l.Front() l.Remove(e) fmt.Printf("要素数: %d\n", l.Len()) // fmt.Println("リスト要素を列挙") for v := l.Front(); v != nil; v = v.Next() { fmt.Printf("%v ", v.Value) } fmt.Println() }
実行結果
$ go run sanpme01.go
要素数: 10
先頭 value: 0, prev: <nil>, next: &{0xc08401cde0 0xc08401cd80 0xc08401cd50 1}
要素数: 10
最後 value: 9, prev: &{0xc08401cf30 0xc08401ced0 0xc08401cd50 8}, next: <nil>
要素数: 10
リスト要素を列挙
0 1 2 3 4 5 6 7 8 9
先頭を削除
要素数: 9
リスト要素を列挙
1 2 3 4 5 6 7 8 9list.Front、list.Backメソッドでリスト内の先頭、最後尾のElementを取得することができます。
リストに追加するときは任意の型を引数にして追加することができるのですが、リストから値を取得するときはElement型でしか取得することができません。Element.Valueとすることで実際の値を取得することができます。Element.Valueの戻り値はinterface{}型となるので、TypeAssertion等を行う必要があります。
また取得したElementのNextまたはPrevメソッドを使用することでリスト内の要素をを前方、後方にiterate処理することができます。
ただ残念なのは、他の言語の様にインデックスを指定してリストの要素のアクセスすることができないことです（少なくとも確認した範囲では見当たりませんでした）。先頭要素、最後尾要素を取得後走査していくしかなさそうです。
list.Front+list.Removeまたはlist.Back+list.Removeのような形で使用すればStackやQueueの様に使用することもできそうです。
ringパッケージ
ringパッケージは他の言語ではあまり見かけない実装です。簡単にいうと上でも説明したlistの最後尾が先頭に繋がった輪（ring）のイメージです。
package main import ( "fmt" "container/ring" ) func main() { r := ring.New(10) for i := 0; i < 10; i++ { r.Value = i r = r.Next() } fmt.Printf("要素数: %d\n", r.Len()) fmt.Printf("現在の値: %v\n", r.Value) // printElements("すべての要素を列挙", r) // fmt.Printf("現在の値: %v\n", r.Value) fmt.Println("20回Nextしならが要素を列挙") for i := 0; i < 20; i++ { fmt.Printf("%v ", r.Value) r = r.Next() } fmt.Println() // fmt.Printf("現在の値: %v\n", r.Value) fmt.Println("先頭から5個の要素を削除") r1 := r.Unlink(5) printElements("残ったすべての要素を列挙", r) printElements("削除したすべての要素を列挙", r1) // fmt.Printf("現在の値: %v\n", r.Value) r = r.Link(r1) printElements("追加後のすべての要素を列挙", r) // fmt.Println("同じringをlink") r = r.Link(r) fmt.Printf("要素数: %d\n", r.Len()) fmt.Printf("現在の値: %v\n", r.Value) printElements("追加後のすべての要素を列挙", r) } func printElements(msg string, r *ring.Ring) { fmt.Println(msg) r.Do(func(v interface{}) { fmt.Printf("%v ", v) }) fmt.Println() }
実行結果
$ go run sanpme01.go 要素数: 10 現在の値: 0 すべての要素を列挙 0 1 2 3 4 5 6 7 8 9 現在の値: 0 20回Nextしならが要素を列挙 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 現在の値: 0 先頭から5個の要素を削除 残ったすべての要素を列挙 0 6 7 8 9 削除したすべての要素を列挙 1 2 3 4 5 現在の値: 0 追加後のすべての要素を列挙 6 7 8 9 0 1 2 3 4 5 同じringをlink 要素数: 9 現在の値: 7 追加後のすべての要素を列挙 7 8 9 0 1 2 3 4 5
まずringではlistの様に前から何番目というような考え方をしない方がよさそうです。
r=ring.New(サイズ)でringを初期化することができます。
この時点でrはring（例えば10個の要素をもつring状のもの）内のある要素（Ring）を指しており、それがどの位置かは分かりません。
要素（Ring）のNextまたはPrevメソッドを使用することでring内を移動することができます。
要素に値を設定する場合はr.Valueに任意の値を指定することができますが、取得する場合はr.Valueがinterface{}を返すのでlistの場合と同じようにTypeAssertion等を行う必要があります。
もう1つ気を付けておく点は、ringにLink、またはUnlinkする場合は、現在の要素の次の要素との間に追加、次の要素から削除が行われるということです。
またlistと同じようにインデックスを指定してアクセスすることができないので（というか上でも書きましたが、インデックスは意識しないほうがよい）特定の要素を取得するには走査するか、別の手段が必要です。
次回
次回はflagパッケージを見ていくそうです。
