From: Stephen Waits <steve@...>
Date: 2005-12-06T07:11:43+09:00
Subject: Re: Shuffling an array, sort_by{rand}'s bias (was Re: need some Ruby magic)

Mauricio Fern�ndez wrote:
>> does
>>
>>   %w( a b c d ).sort{ rand <=> rand }
>>
>> help?
> 
> It is however somewhat slower than sort_by{ rand }.

It's considerably slower.  Changing it to sort { rand(10000) <=> 5000 } 
shows a 30% speedup on 10k element Arrays on my system.  Don't know why 
I chose those numbers, I suppose bigger numbers reduce the "0" 
comparison, considering { rand(3) <=> 1 }.

Anyway, I put together a small benchmark to compare my (revised) 
shuffle, to sort, and sort_by:

#!/usr/bin/env ruby

class Array
   def shuffle
     newarr = self.dup
     2.times do
       self.length.times do |x|
         y = rand(self.length)
         newarr[x], newarr[y] = newarr[y], newarr[x]
       end
     end
     newarr
   end
end

printf(" size shuffle sort sort_by\n")

[10, 100, 1000, 10000].each do |n|

   # populate an Array size n
   a = Array.new(n) { |i| i }

   # my method
   start = Time.new
   100.times do
     b = a.shuffle
   end
   a_time = Time.new - start

   # Array's sort
   start = Time.new
   100.times do
     b = a.sort { rand(10000) <=> 5000 }
   end
   b_time = Time.new - start

   # Enumerable's sort_by
   start = Time.new
   100.times do
     b = a.sort_by { rand }
   end
   c_time = Time.new - start

   # results
   printf("%6d %5.2f %5.2f %5.2f\n", n, a_time, b_time, c_time)
	
end


Which, on my P4/3.0GHz (Win32) emits this:

  size shuffle sort sort_by
     10  0.00  0.02  0.00
    100  0.16  0.13  0.03
   1000  1.61  2.03  0.44
  10000 16.31 28.14  4.78

--Steve