流行に乗って Erlang をちょっと触ってみた
コメントが % だとか、36#12 とか書くと 36 進数の 12 (=38) になるとか、枝葉末節な部分で PostScript と共通点があるのはなんでだろう。(コメントが同じで文法が全然違うと polyglot が難しそうだな)(というと誰かが挑戦してくれたりして)
ところで、よくあるクイックソートのサンプルが
qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).Erlang - Wikipedia
のように、枢軸をリストの最初の要素に決めてしまっているけど、ほとんどソートされたデータを渡したときの計算量が O(N^2) になりそうで気になる。
- 実は Erlang ではほぼソートされたデータを渡しても計算量が O(N log N) で済む
- 実際に使うときは何らかの工夫をしてほとんどソートされたデータでも O(N log N) で済むようにしている
- 他のソートアルゴリズムを使う
- 複数のソートアルゴリズムを別プロセスで実行して、最初に終わったものを使う
- 計算量なんて気にしない
- そもそもソートなんてしない
どれだろう。
追記id:mikage_sawatari さんコメントありがとうございます。 手元のソース (R115B) の lib/stdlib/src/lists.erl *1 の lists:sort() とそこから呼ばれている関数を見てみましたが、手続き脳で Erlang を触ったばかりの私には難しいです。
所々に io:format を挿入して動かしてみた感じでは、リストの最初の数個を見て昇順か降順か見て、昇順(降順)になっていたらリストが大体昇順(降順)になっている部分ずつに分割しつつソートし、その後分割したリストをマージしているように見えます。 そうだとすると、ほとんどソートされたデータの方が速くなりそうです。
追記: Program | 速くないクイックソート - val it : α → α = fun という記事を読みました。関数型とか linked list の世界ではクイックソートよりマージソートが良さそうです。
