巨大なテキストファイル（例えば500M、すみません、それほど巨大ではありません。）をランダムソート（例えば
sort -R）しようとするとソートのアルゴリズムが走るためか、非常に時間がかかる。ところがランダムソートは厳密にはソートする必要がないはずである。そこでバケットソートのバケツをランダムに行うことを提案する。その方法は、複数の一時ファイルを作成し、それらのファイルにランダムに格納し、それを結合することで、トランプのような「シャッフル」を行うことにする。それが下記のrubyワンライナ。
ruby -r tempfile -ne 'BEGIN{R=1000;$ta=Array.new(R){|i|Tempfile.open(i)}}; $ta[rand(R)].print $_; END{$ta.each{|t|t.close;print open(t.path).read}}'
R=1000を適当な値に変更する（大きいほどよくシャッフルされることになるが、システムがそれを許さない場合もある）。またeach内（すなわちバケツ内）でsort -Rしてやれば、完全な？ランダムソートとなる。それが下記。
ruby -r tempfile -ne 'BEGIN{R=1000;$ta=Array.new(R){|i|Tempfile.open(i)}}; $ta[rand(R)].print $_; END{$ta.each{|t|t.close;print `sort -R #{t.path}`}}'
ちなみに、全然巨大ではないが170万行くらいのテキストのソートを行った。前者（シャッフル）は5秒程度、後者（完全なランダムソート）は80秒程度、sort -Rのみだと、110秒程度かかった。
トランプのように前者（シャッフル）を多段にするのも手かもしれない。
追記
さらに検証。sort_by{rand}でバケツをランダムソート。
ruby -r tempfile -ne 'BEGIN{R=1000;$ta=Array.new(R){|i|Tempfile.open(i)}}; $ta[rand(R)].print $_; END{$ta.each{|t|t.close;print open(t.path).each_line.sort_by{rand}}}'
8秒程度。次のブログ記事：[ruby]配列のシャッフルの決まり文句は「sort_by{ rand }」だったによると、sort_by{rand}はしっかりとしたランダムソートらしいが、かなり早いか、よっぽどsort -Rが遅いのだろうか。もし正しければ次のコマンドでよいことになる。
ruby -e 'puts ARGF.each_line.sort_by{rand}'
これも8秒程度。むしろこちらを使いたい。そこで単純にソートで比較してみた。
ruby -e 'puts ARGF.each_line.sort'と
sortなんと、sortの方が6倍遅かった。 コマンドのsortは使ってはいけない？？？、、、と思ったら？2012-01-13 ぬか喜びしないためにも。それでも
sort -Rはなぜか20秒程度だった。（下の追記へ進む）
追記2
sortコマンドのソースを見てみた。sortという単独パッケージではなく、coreutilsというパッケージの中にある。randomのオプションがある場合、compare_random という関数がよばれるらしい。そのコメントは次のようである。/* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB) using one or more random hash functions. TEXTA[LENA] and TEXTB[LENB] must be zero. */値をハッシュ関数によって置き換えたものでソートするという意味である。 すなわちこういうことである。
% ruby -e '(0..10).each {puts rand(2)}' | sort -R
1
1
1
1
1
1
1
0
0
0
0
この関数から予測するに毎度比較する両方の値をハッシュ関数により値を求めている。計算量がnlog(n)だったとしても、2nlog(n)くらいハッシュ関数を呼んでいる可能性がある。事前にn個の全ての値をハッシュ関数で値を求め、それをソートすれば、もっと効率良くなるかもしれない。
結論
sort -Rは、ここで提案する「シャッフル」より4倍ほど遅いのでそれなりに役立つかもしれない。
でも、ワンライナーなら下記でも十分に早いので、それでよいのかもしれない。
ruby -e 'puts ARGF.each_line.sort_by{rand}'
次回の追記は100GBくらいに挑戦する予定。
