降順insertion sortについて
昨日の記事で、世間で広く知られているinsertion sortのコードがいかにひどいかについて書いた。
私の提案したコードをWikipediaにも掲載(注記としてだろう)したほうがいいのではという意見をいくつか頂戴した。
Yuichirou 2009/11/26 02:03
私はyaneuraoさんのコードの方が可読性にも優れていると思います。むしろ日本語版Wikipediaのコードは脱出条件が複雑な内側のループを無理にfor文で書いているため、可読性が落ちています。
yaneuraoさん、ぜひその最後のコードをWikipediaに掲載すべきだと思いますがいかがでしょうか。
上のYuichirouさんの意見は好意からだろうが、はてブでは、次のような否定的な意見も見られる。
shuji_w6e 「馬鹿すぎる」とか「駄目すぎる」とか何様なんだろ？調べて回ったついでに全部書き換えてくればいいのに。
それに対して私はコメント欄で次のように返した。
アホか。「調べて回ったついでに全部書き換え」るなんてこと、なんで調べた人間がいちいちしなきゃならんのだ。お前こそ何様のつもりだ。
まあ、それはそれとしても(私は常に大人げないのだ！)、仮に、私の書いたinsertion sortのコードがよく知られているコードに比べてすごくわかりやすくて、かつ、よく知られているコードより数割速いとしよう。「わかりやすくて」や「数割速い」については異論もあるだろうが、話の便宜上、そうだとしよう。
仮に、わかりやすくて、数割速くとも、insertion sortは、いまさら私のコードを普及させるわけにはいかない理由がある。
それは、例えば、降順に並べ替える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のコードは、あの将棋プログラムBonanzaで実際に使われているのだそうだ。
先頭でINT_MINを代入しているのが番兵で、psortv[i]の値が降順になるように、pmove[i]もソートする。要するにソートするレコード1つは、{psortv[i] , pmove[i] }で、計8バイト。ソートのkeyはpsortv[i]。
あとは、普通のinsertion sortのコードを思い浮かべれば、psort[0]..psort[n-1]の範囲に対して降順並び変えしているんだなというのはわかる。ただ、このプログラムを見せられてそれがパッとわかる人は少ないかも知れない。
このように、番兵つき降順insertion sortは実際のプログラムのなかでは慣用句的に使われる。しかし、普通のinsertion sortのコードが頭のなかに入っていないとこれを見てすぐに理解することは不可能だろう。
つまり、insertion sortのコードは慣用句であって、「for(int i=0 ; i < N ; ++i)」と同じように理解せねばならない。このプログラムを見ていちいち「ここでn-2から始まって…」なんて考えるものではない。そんなことをしていたら日が暮れてしまう。
初心者プログラマでない限り、「for( int i=0 ; i < N ; ++i)」を見た瞬間、ループのなかでiの取り得る値は {0 , … , N-1 } で、このループはN回まわると頭に思い浮かぶだろう。上の降順insertion sortについても同様だ。
このループ先頭のpsortv[n] = INT_MINを見た瞬間、「番兵をセットしたな」と思い浮かび、for(i = n-2 の2を見た瞬間、「これは降順insertion sortだな」とピンと来なければならない。内側のforでsortvと比較してあるから、keyはpsortv[i]だと確定して、内側のforが抜けたところで、書き戻しているから、「ああ確かに典型的なinsertion sortだ」と理解できなければならない。
このように、降順insertion sortはいたるところに現実的に使われており、これらを使ってあるソースを素早く理解しようと思えば、典型的なinsertion sortのコードを覚えておく必要がある。これはShell sortや、ダイクストラ法などについても同様で、ある程度熟練したプログラマなら見ただけで「アレだな」と理解出来て然りなのである。
そのような理由から、いまさらよく知られたコードを、いくらそれより速くてわかりやすいとしても「こちらのほうがいい書き方だよ」だなんて単純に置き換えることは出来ないのである。ましてほとんどのアルゴリズムの教科書のinsertion sortのコードが昨日の記事のような具合で、長年その教科書を使って勉強してきた人がたくさんいるわけである。
ちなみに、Shell sortは、よく知られているようにinsertion sortを用いるsortアルゴリズムであるが、Shell sortをDonald L.Shellが提案したのが1959年である。すなわちinsertion sortなんてものは、それ以前からあったことは間違いない。そう考えると半世紀以上の歴史がある。
こんな古典的なアルゴリズムの改良コードを提案するには、かなりの教育的な配慮のもとに、「こちらのほうがこういう理由で、こういう状況において速くなるんだよ」と示さねばならないのである。単に無責任にWikipediaを書き換えて回ればいいという問題では決してない。
おまけに、ターゲットアーキテクチャが定まらないと、「こちらのほうが速い」というのを示すのはとても難しい。
例えば、Knuthは、その著書TAOCP(The Art Of Computer Programming)のなかで、MIXというRISC型の仮想マシンを提案した。(最近のKnuthの本ではMMIXという新しいバージョンのものが使われている) MIXマシンで最短で書けることやMIXマシンで何stepで実行できるのかというのをアルゴリズム研究の礎にした。
私が思うに、その方針は正しい。しかし、現実的には世のなかのパソコンはほとんどがいまやx86/x64マシンであり、それらのマシンには、分岐予測という仕組みが備わっている。分岐予測が外れたときにはもの凄く大きなペナルティを食らうのが普通である。この部分をある程度考慮した上でアルゴリズムを検討しないと、現実に即したものにならない。その意味ではTAOCPで使われているMIXマシンと現実的なマシンとの溝を埋め合わせるための教育的な試みが必要だと思う。
『ターゲットアーキテクチャが定まらないと、「こちらのほうが速い」というのを示すのはとても難しい』と書いたが実際は、ターゲットがx86/x64,Corei7限定だとしても「こちらのほうが速い」を示すのにはとても労力が必要だ。コンパイラでコンパイルさせてみて明らかに実行時間に差があるならともかく、普通はアセンブリコードを見せて、こっちのほうが分岐予測が当たりやすく、かつこの命令とこの命令のlatencyがこちらより少なくそして、使用するレジスタが何本で済むだとか、そういう話になる。
しかし特定の命令のlatencyについては公開されていないものもある。または、「worst caseでこれだけのlatency」だとかその程度の情報しかわからないものもある。実測すると言っても前後のコンテキストの影響を結構受けたり、そのときのレジスタの値でlatencyが変わったりしえるので測定自体が難しい。
結局、本気で1サイクルでも短いプログラムを書こうと思うとIntelのプロセッサの開発チームに問い合わせなければならないが、私は、いまだかつてIntelのプロセッサの開発チームに問い合わせて教えてもらえたというプログラマは知り合いに一人しか居ない。彼は、「(当時はPrescottの時代だったから)イスラエルにFAXしてこことここを教えてもらった」と言っていたが、ある程度名のある会社で名のある製品を作っていないと門前払いだろう。
さて、長々と書いたが、
・insertion sortは高速化のために特化されたソートアルゴリズムであり高速でなければその存在価値がない。
・世間でよく知られているinsertion sortのコードは決して質の良いコードではなく、改良の余地がある。
・しかし、世間でよく知られているinserion sortのコードぐらい覚えておかないと他人の書いたソースを読めませんよ。
という3つが私の言いたかったことで、こうやってたくさんの人の目に触れたことで私としてはとても満足している。
