[ruby-list:39600] Re: ruby-ver?配列のランダム化

山本です。

Shin-ichiro HARA <[e-mail]> wrote:
(2004/04/26 18:06)

>これはやはり sort を使うこと自体が、コスト高であるのが気に
>なります。

slice! は平均して「要素数 / 2」の要素を毎回ずらす必要があるので、
O(n * log(n)) のオーダで要素を交換するだけの sort のほうが速いんじゃないか、
と思っていました。（でも sort_by は一時配列を使うので、そうでもないですね）

300.times { Array.new(100).randomize! } だと

      user     system      total        real
  0.290000   0.000000   0.290000 (  0.290000)  # slice!
  0.621000   0.000000   0.621000 (  0.621000)  # sort_by
  0.641000   0.000000   0.641000 (  0.651000)  # 原さんの一様アルゴリズム

で確かに slice! が一番速いです。（原さんのアルゴリズムより速いのは意外でした）

でも 10.times { Array.new(3000).randomize! } ぐらいになると

  0.761000   0.000000   0.761000 (  0.761000)  # slice!
  0.901000   0.000000   0.901000 (  0.901000)  # sort_by
  0.631000   0.000000   0.631000 (  0.631000)  # 原さんの一様アルゴリズム

で、3.times { Array.new(10000).randomize! } だと

      user     system      total        real
  2.083000   0.000000   2.083000 (  2.083000)  # slice!
  0.981000   0.000000   0.981000 (  0.981000)  # sort_by
  0.631000   0.000000   0.631000 (  0.631000)  # 原さんの一様アルゴリズム

となって逆転してきます。でも逆にいうと、ここまで大きくないと slice! には
勝てないようです。原さんの確率一様なアルゴリズムは、速度的に安定してますね。

>さらに、randomize の精度が sort のアルゴリズム依存であって、
>例えば stable な sort であるとすると、順序が変わらない確率
>が若干高いです。いくら確率を対象としているといって、アルゴ
>リズムが確率的なのは気持ち悪いです。（気持ち悪くない人もい
>るかも。）

確かにそうかもしれません・・・でも、rand 実数バージョンならこの問題はもう少し
緩和される気もします。（同じ実数が頻繁に生成されない限り）

>In [ruby-list:39593]
>
>> class Array
>>   def randomize!
>>     length.times do |i1|
>>       i2 = rand(length)
>>       t = self[i1]
>>       self[i1] = self[i2]
>>       self[i2] = t
>>     end
>>   end
>> 
>>   def randomize
>>     result = self.dup
>>     result.randomize!
>>     result
>>   end
>> end
>
>こちらは、アルゴリズムとしてまずいのでは？手で計算する
>と [1, 2, 3] をシャッフルして 2 が先頭に来る確率は 10/27
>みたい。もちろん 1/3 であるべきですよね。
>#そもそも手計算で正答する確率がかなり低いのですが(^^;
>
>  def randomize!
>    (length-1).downto(0) do |i1|
>      i2 = rand(i1+1)
>      t = self[i1]
>      self[i1] = self[i2]
>      self[i2] = t
>    end
>  end
>
>だったらいいかな。

ですね (^^; 適当にかき混ぜることしか考えてなくて、確率的な一様性は
頭にありませんでした。原さんのアルゴリズムだと、順列がひとつずつ、
一様に生成されることが期待できますね。

>一番美しいのは r = rand(nの階乗) を一発だけ計算して、後で
>ゴソゴソするアルゴリズムだと思うんですが、r を配列に「デ
>コード」するコストが大きくてあまり速くならなそう。

面白そうですね。r をビット演算するイメージでしょうか。
気が向いたら組んでみるかもしれません。