stable quick sort
stable な quick sort もあるよ、という話なのだが。
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort [ y | y <- xs, y < x ]
++ [x]
++ quicksort [ y | y <- xs, y >= x ]これは遅そうだなぁ。in-place にはできないのか？じゃないとメモリ消費量がすごそう。
ただし、このようなことをする場合には内部的にmallocが必要となる(リストだし・・・)。
連結リストだからといって毎回動的メモリ確保が必要かといえばそうでもない。必要なサイズがあらかじめ分かれば1度大きな配列を作ってインデックスをポインタ代わりに使えば済む。
そもそも、問題は malloc がどうのこうのいうよりはパーティショニングを高速にできるかどうかで、安定にやろうと思うと、これが案外簡単ではないという話では。この例ではリストを2回走査しているし、pivot を先頭要素以外にしちゃうとこれまた面倒だし*1。
ちなみに前後から同時に探索すると言うのは、信じられないくらいの量の要素を入れると、キャッシュの効果がどうのこうので遅くなる、ということも予想されますが、それはまあ気にしない方向で。
前後から同時に走査しようとそれぞれで局所参照性はあるので、たいしたことはないと思う。キャッシュが1ブロックしかないなら別だけど。
で、なんか性能比較した論文ないかなとちょっと探してみたけど、短い時間だといいのが見つからなかった。が、代わりに 2ch のスレッドが見つかった。
*1:途中でpivotを変更しちゃえばいいといえばいいけど
vi のモード #2
それは私も分かって書いています。このタイトルはただの冗談です。
ならそう書いておいたほうが知らない人に無駄な誤解をばら撒かなくていいかなと思ったり。
ex mode も出てきますが、これはむしろ ex というコマンド名で起動したときを表し、visual mode に対応するものらしい。
これはそのとおりかも。vim のドキュメント*1では、":" を押して入るコマンド入力モードを command-line mode、ex という名前で起動したとき(もしくは command mode から Q を押したとき)のラインエディタのモードを ex mode と呼んでいる。訂正したいと思う。
昔みた記事*2には command mode, ex mode, insert mode の3つが書いてあった気がするんだけどな。記憶違いかな。
ついでなので、vim の基本の6つのモードの紹介とかしてみる。vim の visual mode は screen editor としての意味の visual mode とは違うので注意。
Normal mode
起動時のモード。hjkl でカーソル移動できる。traditional vi の command mode に相当。
Visual mode
Normal mode から V, v, Ctrl-V で移行する範囲指定のモード。traditional vi には無い。
Select mode
MS-Windows の selection mode like な範囲指定のモード。Visual mode と似たようなものだが細かい挙動が違うらしい。使わないので詳しいことは知らない。Visual mode と同様、traditional vi には無い。
Insert mode
Normal mode から i, a, o などで入るテキスト入力用のモード。
Command-line mode
Normal mode から ":" で移行する ex command の入力用モード。"/" や "?" での検索モードもこれに含まれる。コマンドを実行すると Normal mode に戻る。
Ex mode
ex という名前で起動するか、 Normal mode から "Q" で移行する ex command によるラインエディタモード。
