RE: sort を使うときは，LC_ALL=C を忘れずに
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく．
404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な
まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
sort コマンドが思いのほか遅いという報告の大半は，LC_ALL=C していないというオチ．追記: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記 でも書いたが，今の日本で貴重な電力を浪費する人が少しでも減るよう，もう一度書いておく．
なお，実験結果は以下のとおり．
/usr/share/dict/words
# MacBook Air (Mid 2011) 11-inch Core i7 1.8GHz # c-bucketsort-674065d > run ./bucketsort /usr/share/dict/words > /dev/null elapsed (real): 0.174s; RSS=9.7M # sort (GNU coreutils) 5.93 > run /usr/bin/sort /usr/share/dict/words > /dev/null elapsed (real): 1.987s; RSS=13.7M > LC_ALL=C run /usr/bin/sort /usr/share/dict/words > /dev/null elapsed (real): 0.076s; RSS=13.6M # sort (GNU coreutils) 8.14 (installed using Homebrew) > run /usr/local/bin/sort /usr/share/dict/words > /dev/null elapsed (real): 1.307s; RSS=17.4M > LC_ALL=C run /usr/local/bin/sort /usr/share/dict/words > /dev/null elapsed (real): 0.076s; RSS=16.7M # multikey quick sort (マルチキークイックソート（Multikey Quicksort）のための C++ ヘッダ 改良版 - やた＠はてな日記) > run mkq-sort /usr/share/dict/words > /dev/null elapsed (real): 0.076s; RSS=8.9M
ruby -e 'puts (1..1e1).to_a.shuffle' > 1e7.txt
> ruby -e 'puts (1..1e1).to_a.shuffle' > 1e7.txt > run ./bucketsort 1e7.txt > /dev/null elapsed (real): 10.785s; RSS=384.3M # sort (GNU coreutils) 5.93 > run /usr/bin/sort 1e7.txt > /dev/null elapsed (real): 195.433s; RSS=521.2M > LC_ALL=C run /usr/bin/sort 1e7.txt > /dev/null elapsed (real): 10.080s; RSS=521.8M # sort (GNU coreutils) 8.14 (installed using Homebrew) > run /usr/local/bin/sort 1e7.txt > /dev/null elapsed (real): 125.085s; RSS=524.5M > LC_ALL=C run /usr/local/bin/sort 1e7.txt > /dev/null elapsed (real): 6.841s; RSS=525.1M # multikey quick sort > run mkq-sort 1e7.txt > /dev/null elapsed (real): 5.661s; RSS=360.7M
このようにして，sort (GNU coreutils) により浪費された計算機資源のことを思うと，罪作りな仕様だと思う．ちなみに，LC_ALL=C のことは 実は sort コマンドの help にも書いてある（残念ながら locale によって大幅に遅くなるとは書いてないが）．
> sort --help ... *** WARNING *** The locale specified by the environment affects sort order. Set LC_ALL=C to get the traditional sort order that uses native byte values. ...
今回の再実験で，
- Linux より，MacOS の方が LC_ALL=C しないときの速度低下が著しい
- GNU coreutils の最新版では（自動並列化のおかげで）sort が結構速くなっている（--parallel=1 にするとほとんど同じ）
というのが新たに分かったのは良かった．
文字列のソートなら，多くの場合 Multikey Quicksort が sort (GNU coreutils) より安定して速い．[追記: 2013/02/11] burst sort など，さらに速いソートもある．
bucket sortと言えば，自分が公開している分類器でも（素性の発火分布が冪乗則に従う）素性ベクトルで素性番号を整列するために，bit を bucket に用いた変形 bucket sort を使っている．大部分を占める高頻度（で小さいIDの）素性は bucket sort（ソート後の要素はビット演算で取り出す）して，残りの少数の低頻度素性は挿入ソート．これで，std::sort (introsort) 比で3倍ぐらい速い．bucket sort は，汎用的には使いづらいが，適材適所に使えばとても役に立つ，という認識．
