2008/06/06
ソート
計算量はO(N log N)だけど、クイックソートより遅いし、安定じゃないので、あんまり活用法が見出せないところですが、バランスの良い木の作り方がわかったので収穫アリでした。
クイックソートってある意味スゲー簡単にコーディングできる割に高速なアルゴリズムではあるんだけど、落とし穴がそこかしこにあるので使うときには注意が必要(な場合もある)。 […] ナイーブに組んでると、再帰のレベルが(ほぼ)データの長さになるのでスタックオーバーフローが簡単に起きる (で、大概の教科書にはそのナイーブなやり方しか解説がない)。
Gaucheの組み込みの(Cで実装された)ソートはデフォルトではQuick Sortで始めて、 再帰の深さが ceiling(2*log(N)) を越えた時にHeap Sortにスイッチするように してる。この技は(もう覚えてないけど、コメントによれば)TAOCPに出ていたようだ。 Quick SortもHeap Sortもin-placeでできるので、既にQuick Sortでソート済みの 連続領域がいくつかある状態でそれぞれの領域にそのままHeap Sortを適用できるのは便利。
ただ、このアルゴリズムは比較関数を省略してデフォルトのを使った場合に限られてて、 比較関数を渡した時はSchemeで書かれたMerge Sortになる。 Scheme関数をCからコールバックするオーバヘッドのせいで、pure Schemeの実装の 方が速かったからだ。(あと、stable-sortを使うと常にMerge Sortになる)。 必要以上に複雑になっている気はしないでもない。 思い切って全部Merge Sortにした方がすっきりするだろうけど、 アロケーション無しでソートしたい時もあるんだよなあ。
Tags: Programming, Gauche
