From: Maarten Boonen <m44rt3n@...>
Date: 2004-12-16T17:27:15+09:00
Subject: Re: [ANN] rand.rb 0.9: Random access methods for Enumerables

trans. (T. Onoma) schreef:
> On Wednesday 15 December 2004 05:12 pm, Maarten Boonen wrote:
> | Neil Spring schreef:
> | > On Dec 14, 2004, at 7:24 PM, Ilmari Heikkinen wrote:
> | >> rand.rb is a library for picking random elements and shuffling.
> | >> This work is licensed under the same terms as Ruby itself.
> | >
> | > umm,  could you maybe replace:
> | >
> | >   def shuffle!
> | >     sort!{rand <=> 0.5}
> | >   end
> | >
> | > with:
> | >
> | >   def shuffle!
> | >     each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i],
> | > self[j]}
> | >     self
> | >   end
> |
> | I made this a function a few days ago and it seems to be a lot faster.
> | Not sure if it's completely correct though.
> |
> | def shuffle!
> |  a = 0
> |  while(a<length)
> |   b = (length*Kernel.rand).to_i
> |   tmp = self[a]
> |   self[a] = self[b]
> |   self[b] = tmp
> |   a+=1
> |  end
> |  self
> | end
> 
> Well, lets see... a couple of equivalent transformations and:
> 
>   def shuffle!
>     ln = length
>     ln.times do |a|
>       b = Kernel.rand(ln)
>       self[a], self[b] = self[b], self[a]
>     end
>     self
>   end
> 
> If you look closely, it is almost the very same thing. The real difference 
> lies in the the subtraction on the index being fed into #rand. I think this 
> is to improve the randomness a bit.
> 
> How much faster does it run?
> 
> T.

Just a very small test: (code below)

-> third is your equivalent code, self[a], self[b] = self[b], self[a] 
seems to slow it down quite a lot.

 >ruby test3.rb
1.272
0.571
1.042
 >Exit code: 0
 >ruby test3.rb
1.262
0.601
1.042
 >Exit code: 0
 >ruby test3.rb
1.302
0.551
1.041
 >Exit code: 0






class Array

   def shuffle!
     each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i], 
self[j]}
     self
   end

def shuffle2!
	a = 0
	while(a<length)
		b = (length*Kernel.rand).to_i
		tmp = self[a]
		self[a] = self[b]
		self[b] = tmp
		a+=1
	end
	self
end

   def shuffle3!
     ln = length
     ln.times do |a|
       b = Kernel.rand(ln)
       self[a], self[b] = self[b], self[a]
     end
     self
   end

end


arr = (1..100000).to_a

a=Time.now
arr.shuffle!
puts Time.now-a

a=Time.now
arr.shuffle2!
puts Time.now-a

a=Time.now
arr.shuffle3!
puts Time.now-a