From: "Mauricio Fernández" <mfp@...>
Date: 2005-12-07T06:16:12+09:00
Subject: Re: Shuffling an array, sort_by{rand}'s bias (was Re: need some Ruby

On Wed, Dec 07, 2005 at 05:04:13AM +0900, Stephen Waits wrote:
> Stephen Waits wrote:
> >I forgot to deal with collisions in the hash!   :(
> 
> Here's another shot.. still faster than sort_by{rand} on my system, and 
> now should be unbiased:
> 
>   def shuffle3
>     h = Hash.new
>     self.each do |v|
>       k = rand(1000000000) until !h.has_key?(k)

This is not equivalent to 
    begin
      k = rand(1000000000)
    end until !h.has_key?


Compare
    k = 1 until true
    k                                                  # => nil
to
    begin; k = 1 end until true
    k                                                  # => 1


>       h[k] = v

You forgot
     h.keys.sort.collect { |k| h[k] }
    
>     end
>   end
> 
> shuffle3 (10000)  3.625000   0.016000   3.641000 (  3.656000)
> sort_by (10000)   5.250000   0.000000   5.250000 (  5.312000)


After fixing shuffle3, I get:

module Enumerable
  def shuffle3
    h = Hash.new
    k = rand(1000000000)
    self.each do |v|
      k = rand(1000000000) until !h.has_key?(k)
      h[k] = v
    end
    h.keys.sort.collect { |k| h[k] }
  end

  def shuffle4
    h = {}
    k = rand(1000000000)
    self.sort_by{ k = rand(1000000000) while h.has_key?(k); h[k] = k }
  end
end

GC.disable
(1..10).shuffle4                                   # => [8, 3, 10, 2, 4, 6, 7, 5, 9, 1]
a = 1..100000
t0 = Time.new                                      # => Tue Dec 06 22:13:56 CET 2005
a.shuffle4
(t1 = Time.new) - t0                               # => 0.766411
a.shuffle3
(t2 = Time.new) - t1                               # => 0.575967
a.sort_by{ rand }
Time.new - t2                                      # => 0.637288


-- 
Mauricio Fernandez