１ヶ月前から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)