Rubyで配列のランダムソート

Rubyでランダムソートをしようと思ったら、色々な発見が出来た。試行錯誤の記録。

結論

ランダムソートならsort_by(rand)がいい。

p (1..10).sort_by{rand}
#=> [10, 3, 5, 9, 8, 6, 2, 4, 7, 1]

シェルスクリプトとして活躍中〜。

% random() { ruby -e 'print STDIN.to_a.sort_by{rand}' }
% printf "%d\n" {1..5} | random
2
1
3
4
5

かなり便利っす。

では、最適解が出るまでの記録をどうぞ。

ランダムソート

sortを使ってランダムに並び替えてみる。

p (1..10).sort{rand(3) - 1}
[5, 2, 10, 1, 4, 9, 6, 3, 7, 8]

rand(3) - 1だと、並び替える確率が低くなってしまうと思い、(rand(2) == 0) ? -1 : 1とした。

p (1..10).sort{(rand(2) == 0) ? -1 : 1}
#=> [2, 9, 1, 6, 3, 4, 5, 10, 7, 8]

しかし、この方式には罠があった。

よく見てみよう。

p (1..10).sort{(rand(2) == 0) ? -1 : 1}
#=> [2, 9, 1, 6, 3, 4, 5, 10, 7, 8]

よく見ると、うまく混ざってない。2,1が端、10,7,8も端

ふとした疑問

値が固定なのにバラバラになったぞ!!

p (1..10).sort{1}
#=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]

何故だ!?

Rubyのソートアルゴリズムを確かめる

p (1..10).sort{|a,b| puts "#{a} #{b}"; 0}
#=> 1 6
#=> 6 10
#=> 2 6
#=> 3 6
#=> 4 6
#=> 5 6
#=> 7 6
#=> 8 6
#=> 9 6
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

真ん中と端を比べてソートしている。おぉ!クイックソート!

色々実験してみると、

rand(3) - 1の方がよく混ざることが判明した。

p (1..10).sort{rand(3) - 1 }
#=> [5, 9, 8, 4, 10, 6, 1, 3, 2, 7]

Rubyのクイックソートの場合、中心を起点に交換する。

-1,1のランダム化では、交換してもう一度交換することになり、元の位置に近い場所へ戻ることになる。

-1,0,1のランダム化によって、値を交換しない時を作った方が、より遠くへ運ぶことができる。

しかし、中心にいくほどよく混ざるsortを使ったランダム化は正確にランダムな配列を作ることは出来なそうだ。

sortでは正確にランダム化出来ない事がわかってきたので、

別の方法を試すことにした。無駄にモジュール化。

module Random
  def random
    old = clone
    new = self.class.new
    while n = old.delete_at(rand(old.length))
      new << n
    end
    return new
  end
end

class Array
  include Random
end

p((1..10).to_a.random)
#=> [4, 5, 1, 10, 8, 2, 9, 7, 6, 3]

ランダムにポップして、新しい配列にプッシュする。ばらつきのない配列を作ることが出来た。

案外使えそう。

てことで、randomコマンド 0.0.1

#!/usr/bin/ruby

# random.rb 0.0.1

module Random
  def random
    old = clone
    new = self.class.new
    while n = old.delete_at(rand(old.length))
      new << n
    end
    return new
  end
end

class Array
  include Random
end

begin
  print STDIN.to_a.random
rescue => ex
  abort ex.message
end

パスの通ったところに,randomと言う名前で登録しておいて、

% random < books.txt | sort
BINARY HACKS
Fedora Core6 ビギナーズバイブル
Linux コマンドポケットリファレンス
Vi IMproved-Vim

なかなか便利。

しかし・・

Rubyist - 只今Ruby勉強中 - ランダム配列の話題より。

こっちの方が断然早かった・・・。

% time ruby -e '100000.times {|i| puts i}' | random 

で計測したところ、

# ボクノス法
random  5.97s user 0.18s system 52% cpu 11.767 total
# Ruby勉強中法 
random2  1.31s user 0.35s system 21% cpu 7.742 total

sort_by{ rand }でランダムな数列をインデックス化してソートをかけた方が断然早い。

ボクノス法は、delete_atやpushでメモリをいじりまくるので、重い処理になっていた。

Rubyで配列のランダムソートをする場合は、

sort_by{ rand }

がいい。Perl,JavaScriptに関しては、hail2u.net - Weblog - JavaScriptで配列をシャッフルが参考になります。

ようするに sort_by すごい便利って事で。