１ヶ月前からGoの勉強を始めて、先人の言う通りにA Tour of Goをなぞっていました。
そして、いよいよ最終章の並行処理(Concurrency)に入ったところで、練習問題Exercise: Equivalent Binary Treesがどうしても解けないで３日ぐらい、あーでもないこーでもないとゴニョゴニョやってましたが、どうしてもうまく行かんので己の敗北を認め、模範解答を見て、自分の理解のなさを痛感した次第であります。
とはいえ、学びも大きかったので、ここにあらましを書いていきたいと思います。
Exercise: Equivalent Binary Trees
2分木のデータ構造をした10個の整数値をgoroutineとchannelを使って1,2,3...10と順番に取り出す問題。
なお、この課題では本当は全部で4つの解答を求められるが、ここに挙げるのは、その内の１つ目の問題だけです。（１つだけで３日かかったんやで）
模範解答
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
if t.Left != nil {
Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}
}
func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
n := <-ch
fmt.Print(n, ",")
}
}
結果
1,2,3,4,5,6,7,8,9,10,
再帰で２分木の構造をなぞって、左の枝、節点、右の枝を順々にchannelに書き込んでいる。シンプルでわかりやすい。
自分が書いていた間違ったコード
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
if t.Left != nil {
go Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
go Walk(t.Right, ch)
}
}
func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
n := <-ch
fmt.Print(n, ",")
}
}
結果
10,5,7,6,3,1,2,9,4,8,
順番がバラバラ。模範解答のコードと酷似していますが、重大な過ちを犯しています。
go Walk(t.Left, ch) // goキーワードがついてる！！
そうです。再帰で呼んでるWalk関数の前にgoキーワードをついているため、Walk関数が全て並行で実行されていたのです。再帰で２分木をたどっていくときは、同期的に処理しなければいけなかったんです。
ただし、main関数で呼んでいる最初のWalk関数の前にはgoキーワードが必要です。main関数と最初のWalk関数は別々のgoroutineとすることで、お互いにchannelの送受信ができるようになっている。ということでした。うーん悔しい。
go Walk(tree.New(1), ch)