こんにちは、馬場です。
完全に出遅れていますが、個人的に触ってみたかったGo言語と戯れてみたいと思います。Go 言語といえば並行処理ですよね。せっかくですので、他の言語Java 8 / Scala 2.11 と比較しながら見ていきたいと思います。
お題：二分探索木を比較する。
並行処理のお題は、超充実しているGo 言語のチュートリアルTour of Goのエクササイズ、Equivalent Binary Tree です。
二分探索木とは、子の数が最大２である二分木で、「あるノードの左の子およびその全ての子孫ノードの持つ値はそのノードの値より小さく、右の子及びその全ての子孫ノードの持つ値はそのノードの値より大きくなるように構成した」もの(Wikipedia)です。
２つの二分木が、形はちがえど同じ値を保持している場合があります。そのために、
1. 二分探索木を生成し、
2. 2つの二分木の解析（＝どのような値を保持しているのか）を並行して行い、
3. その後解析結果を比較する
処理を３つの言語で実装します。
1. Java 8
まずは、二分探索木を生成するクラスです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
package tree; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * 整数の値をもつ二分探索木。 left Treeに含まれる値はすべてvalue より小さく right Treeに含まれる値はすべてvalue以上。 * * */ public class Tree { private Tree left; private Integer value; private Tree right; /** * 値がvalue 、子どもを持たないTreeを作成する * * @param value ノードの値 */ public Tree(int value) { this.value = value; } public Tree getLeft() { return left; } public Tree getRight() { return right; } public Integer getValue() { return value; } /** * ランダムにTreeを生成する。 生成されるTreeは coef,2coef,3coef,... ,10coefの10の値を保持する。 * * @param coef Treeに含まれる数を生成するための係数 * @return coef, 2coef, ... 10coef の10個の数字を保持するTree。形はバラバラ */ public static Tree createTree(int coef) { //ランダムにTree を生成できるよう、seeds の順番をバラバラにする Integer[] seeds = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; List<Integer> seedList = Arrays.asList(seeds); Collections.shuffle(seedList); Tree tree = null; for (int seed : seedList) { tree = insert(tree, (1 + seed) * coef); } return tree; } /** * 二分探索木の構造を保つように、Tree tree に値value を追加する。 * * @param tree Tree * @param value 追加する値 * @return valueを追加した新しいTree */ private static Tree insert(Tree tree, int value) { if (tree == null) { return new Tree(value); } if (value < tree.value) { tree.left = insert(tree.left, value); } else { tree.right = insert(tree.right, value); } return tree; } public String toString() { String string = ""; if (left != null) { string += left.toString() + " "; } string += value; if (right != null) { string += " " + right.toString(); } return "(" + string + ")"; } public static void main(String[] args) { System.out.println(Tree.createTree(1)); System.out.println(Tree.createTree(1)); System.out.println(Tree.createTree(1)); } } |
このTree の解析をするメソッドを実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
import java.util.ArrayList; import java.util.List; /** * Tree treeを解析し、Treeに含まれる数のList を返す * * @param tree 解析対象のTree * @return Treeに含まれる数のリスト（小さい順） */ public static List<Integer> walk(Tree tree) { List<Integer> result = new ArrayList<>(); if (tree.getLeft() != null) { result.addAll(walk(tree.getLeft())); } result.add(tree.getValue()); if (tree.getRight() != null) { result.addAll(walk(tree.getRight())); } return result; } |
お気づきの通り、ここまで並行処理全く関係ありません。それでは、2つのTreeを解析し、保持する値が同じかどうか確かめてみましょう。2つのTreeの解析は並行に行います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.List; import java.util.concurrent.CompletableFuture; import java.util.concurrent.ExecutionException; /** * 2つのTreeが同じ数のリストを含むTreeかどうか検証する。 * @param treeA 比較対象のTree * @param treeB 比較対象のTree * @return 同じならtrue/違う場合はfalse * @throws InterruptedException * @throws ExecutionException */ public static boolean isSame(Tree treeA, Tree treeB) throws InterruptedException, ExecutionException { // CompletableFuture#supplyAsync メソッド内で記述したラムダ式の処理は非同期に実行 CompletableFuture<List<Integer>> futureA = CompletableFuture .supplyAsync(() -> walk(treeA)); CompletableFuture<List<Integer>> futureB = CompletableFuture .supplyAsync(() -> walk(treeB)); //CompletableFuture#get メソッドは処理が完了した時点で結果を返す List<Integer> resultA = futureA.get(); List<Integer> resultB = futureB.get(); for (int i = 0; i < resultA.size(); i++) { if (resultA.get(i) != resultB.get(i)) { return false; } } return true; } |
Java8 で追加された CompletableFutureを利用して、２つのTreeの解析を並行で実行しています。CompletableFuture.supplyAsync は 引数に指定した処理を非同期で実行します。Futureのgetメソッドは、処理が終わった段階で値を返してくれます。ラムダ式もうまく使われていて、コードも非常に簡単。Thread だ、synchronized だと言っていた一昔前のJavaエンジニア（私です）からみると隔世の感があります。
2. Scala 2.11
次はScalaです。二分探索木を生成するクラスは以下のようになりました。ScalaらしくOptionを使います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
/** * 整数の値をもつ二分探索木。 left Treeに含まれる値はすべてvalue より小さく right Treeに含まれる値はすべてvalue以上。 * 子ノードleft/rightを持たない場合はNone */ case class Tree( value:Int, left:Option[Tree] = None, right:Option[Tree] = None){ override def toString() : String = { var string = "(" string += left.map( _.toString() + " ").getOrElse("") string += value string += right.map( " " + _.toString()).getOrElse("") string += ")" string } } object Tree { /** * ランダムにTreeを生成する。 生成されるTreeは coef,2coef,3coef,... ,10coefの10の値を保持する。 * * @param coef Treeに含まれる数を生成するための係数 * @return coef, 2coef, ... 10coef の10個の数字を保持するTree。形はバラバラ */ def createTree( coef : Int ) : Tree ={ val seeds = scala.util.Random.shuffle(0 to 9) val defaultTree: Option[Tree] = None // treeに順番に値を追加していく。 seeds.foldLeft(defaultTree){ (tree , seed) => insert(tree, (1 + seed) * coef) }.get } /** * 二分探索木の構造を保つように、Option[Tree] treeOption に値value を追加する。 * treeOption がNoneであった場合、値value のみをもつTree を生成し返す。 * * @param treeOption Option[Tree] * @param value 追加する値 * @return valueを追加した新しいOption[Tree] */ def insert( treeOption : Option[Tree] , value : Int): Option[Tree] = { treeOption match{ case None => Some(Tree(value)) case Some(tree) => if( value < tree.value ){ Some( tree.copy( left = insert(tree.left, value))) } else { Some( tree.copy( right = insert(tree.right, value))) } } } } |
このTree の解析をするメソッドを実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/** * Tree treeを解析し、Treeに含まれる数のListBuffer を返す * * @param tree 解析対象のTree * @return Treeに含まれる数のリスト（小さい順） */ def walk( tree : Tree ) : ListBuffer[Int]= { val result = ListBuffer[Int]() tree.left.foreach( t => result ++= walk(t)) result += tree.value tree.right.foreach( t => result ++= walk(t)) result } |
それでは、2つのTreeを解析し、保持する値が同じかどうか確かめてみましょう。2つのTreeの解析は並行に行います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/** * 2つのTreeが同じ数のリストを含むTreeかどうか検証する。 * 同じなら"true" 違ったら"false"と標準出力する。 * @param treeA 比較対象のTree * @param treeB 比較対象のTree * @throws InterruptedException * @throws ExecutionException */ def isSame(treeA:Tree , treeB: Tree) : Unit = { import scala.concurrent._ import ExecutionContext.Implicits.global // Futureブロックの処理は非同期で実行される val futureA:Future[ListBuffer[Int]] = Future { walk(treeA) } val futureB: Future[ListBuffer[Int]] = Future { walk(treeB) } // for 文で2つの処理を同期させ、 // 解析結果を比較している val result : Future[Boolean] = for { resultA <- futureA resultB <- futureB } yield { resultA == resultB } // Scala のFuture はget 相当のメソッドを持たない。callback関数を指定する仕組み。 result onSuccess { case r => println(r)} } |
Scala のFuture は「処理が終わったらその値を取得する」ということができません。完了時のcallback関数を設定する方式（onSuccessで指定しているブロック）です。とはいえ、上記のようなfor文を書くことにより、複数の処理を最後に同期させて結果を比較することができます。
3. Go
さて、これをGo で実装するとどうなるのでしょう？二分探索木を生成するクラス。これは、Go のチュートリアルを参照してください（というか、ここまでのプログラムはこのGo のプログラムをJava や Scala で書き直したものです）。
Tree を解析するメソッド、同じかどうか判定するメソッドは以下のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
package main import "code.google.com/p/go-tour/tree" import ("fmt") // Walk 関数では、Treeを探索しながら、Treeに含まれる全ての // 値を、値が小さい物から順にチャネル chに送信する func Walk(t *tree.Tree, ch chan int){ WalkSub(t, ch) close(ch) } // 再起呼び出し用の関数 func WalkSub(t *tree.Tree, ch chan int){ if t.Left !=nil { WalkSub(t.Left, ch) } ch <- t.Value if t.Right !=nil { WalkSub(t.Right, ch) } } // Same 関数は、2つのTree t1 とt2が全く同じ値を含んでいるものかどうか // 確認する func Same(t1, t2 *tree.Tree) bool{ c1 := make(chan int) c2 := make(chan int) // goroutine によりWalk関数を並行実行 go Walk(t1, c1) go Walk(t2, c2) // それぞれのチャネルが受信した値を取り出し // 一致するか評価 for i := range c1 { j := <- c2 if i != j { return false } } return true } func main() { fmt.Println(Same(tree.New(1),tree.New(1))) fmt.Println(Same(tree.New(1),tree.New(2))) } |
Future を利用していたJava やScala とだいぶ趣が違いますね。Go には チャネル(Channel)と呼ばれるものがあり、このチャネルを通して値の送受信が可能です。そこで、このチャネルをつかってTreeの解析と並行して行い、結果を比較しています。
Walk 関数内では、Treeに含まれる値を小さい順にどんどんチャネルに送ります。goroutineを利用してWalk関数は並行して実行します。Same関数では、チャネルの値を順番に取り出して比較することによって、２つのTreeが同じ値を持っているか、評価します。
Go の何がうれしいのか？
並行処理と言えばGoという評判ですが、それはやはりこの goroutineとチャネルの仕組みがあるからこそなのでしょう。特にチャネル。Java や Scala が利用しているFutureはTreeの解析を全部し終わってから同じかどうか評価しています。Goのチャネルは、値を受け取ったらその都度値を取り出して処理を行っています。二分木が大きく探索に時間がかかる場合、少しでも違いがあれば処理が終了し早く終わります。サービス的プログラムを書くのにもよさそうですね。
やってみてわかったこと
Goと本当に軽く戯れてみてわかったことは、チュートリアルの充実です。個人的にプログラミング言語を学ぶときの最初の障害はプログラミング環境をつくるところだと思っているのですが、その点このチュートリアルにはブラウザ上からプログラムを試す環境がついていて、非常に楽でした。他の言語もこれくらいわかりやすく「とにかくまずはやってみよう」と思った人フレンドリーなチュートリアルがあればいいな、と感じました。（Java のチュートリアルは、JVMの説明から入る来るものを拒む仕様...)
また、久しぶりにJava を調べてみて、Java 8 になって書きやすくなったと感じました。重い処理を複数のスレッドにわけて実行し、あとで結果をマージするような使い方であれば、Java8 の書き方が一番わかりやすいでしょう。
それでも一番好きなのはScalaです。
みなさんの開発の場でどれほど言語選択の自由があるのかわかりませんが、何かの参考になればうれしいです。
Comments
> Java や Scala が利用しているFutureはTreeの解析を全部し終わってから同じかどうか評価しています。Goのチャネルは、値を受け取ったらその都度値を取り出して処理を行っています。二分木が大きく探索に時間がかかる場合、少しでも違いがあれば処理が終了し早く終わります
という箇所、まずScalaやJavaのプログラムをそのように書いてないコト自体が問題で(それを書いた場合どのくらい面倒か、という別の問題があるが、書けないことはないはず)、それを試さずにGoを褒めるのはおかしいと思うので、そういう意味では比較として微妙だと思うのですが