Bonanzaで使われているinsertion sortとは何か?
■ Bonanzaで使われているinsertion sortとは何か?
Bonanzaで使われているsort(並べ替え)は、
1) insertion sort
2) shell sort
3) quick sort
の3種類である。
3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースのメンテナンスにのみ使われており、実際の探索で使われているのは1),2)のみだ。
また、2)には1)が必要である。そこで、今回は1)について解説する。
■ Bonanzaのnext.c
Bonanzaのnext.cは、次の指し手を生成するcoroutineである。ここでinsertion sortが使われている。
指し手生成をcoroutineにしないでいきなり全部の手を生成したり、全部の手に対して点数をつけてquick sortしたりすると劇的なパフォーマンスの低下を招くのでそれは絶対に避けたほうが良いと思う。
さて、next.cで使われているソートはinsertion sortであり、この配列には数手しか入っていない(どんな手が入っているのかは今回解説しない)ので、insertion sortならば非常に高速である。
psortv[n] = INT_MIN; // 末尾に番兵を置く for ( i = n-2; i >= 0; i-- ) { // このsortv,moveがtmp変数だとみなせば、 // ふつうの挿入ソート。ループ変数が逆方向に動くだけ。 sortv = psortv[i]; move = pmove[i]; for ( j = i+1; psortv[j] > sortv; j++ ) { // 降順なので前にひとつずらしていく。 psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j]; } psortv[j-1] = sortv; pmove[j-1] = move; }
上のコードは「広く知られているinsertion sortのコードは駄目すぎる」(→ http://d.hatena.ne.jp/yaneurao/20091126 )にあるような、「広く知られているinsertion sortのコード」 + 番兵 + 降順ソートに書き換えたバージョンだ。
早い話が、上の処理を抜けたあとは、一番大きな点数をつけた指し手はpmove[0]に入っており、そのときの点数がpsortv[0]になる。
Bonanzaで使われているinsertion sortはたいてい上のパターンで書かれているので、上のパターンを知っていれば、「ああ、ここではpsortvの値が降順になるようにpmove[0]..[n-1]をソートしているんだな」と見た瞬間に理解できる。「for(int i=0; i < n ; ++i)」などと同じく、これは形で覚えるといいだろう。
「広く知られているinsertion sortのコードは駄目すぎる」の指摘にあるようにこのコードは最後にinsertが発生しないときもwrite backが発生するのでパフォーマンス的に見れば改善の余地があるコードであることも付記しておく。