psort.scm

　quickselectを使った部分ソートを実装してみた。細部を真剣に検討していない（する前に力尽きた）ので、もうちょっとテストしてみないと、自分でも使う気になれないが、概ね動いている模様。http://xem.jp/~tkng/code/に置いといた。
　関数型言語？と思わず疑問符をつけてしまうぐらい、破壊的操作ばっかり使ったコードになってしまった。ここまで破壊的操作ばかりだと、いっそすがすがしいぐらい。
　性能がどれぐらい違うのか計測してみた所、Gauche付属のsortで30000要素のソートに0.1秒かかるところ、30000要素の上位100個だけ求めるという操作で0.01秒。一桁違う。逆に言うと、一桁しか違わない。
　しかし、Gaucheは比較関数を省略するとCで書かれたソート関数を使うので、そちらも試してみた所、0.017秒という結果になった。この場合だと差は2倍もない。Cで書けば30000要素のソートぐらいはあっという間のようだ。
　結論としては、n log nは十分に速い、という事になるのだろうか。もちろん、一回の比較操作がもっと重い場合には、部分ソートにも価値はあるし、実際に今考えている用途は比較操作が重たいのだが、整数やら実数やらの比較を行う程度なら、何も考えずにソートしても大きな問題ではない。