# Need some Ruby magic

**URL:** <https://rubytalk.org/t/need-some-ruby-magic/22918>\
**Category:** ruby-talk\
**Created:** [1 December 2005 19:42 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918 "2005-12-01T19:42:42Z")\
**Posts on this page:** 7\
**Page:** 3

<div class="post-metadata">

**Author:** ![Stephen\_Waits1](https://avatars.discourse-cdn.com/v4/letter/s/57b2e6/32.png) [@Stephen\_Waits1](https://rubytalk.org/u/Stephen_Waits1)\
**Post date:** [6 December 2005 19:52 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/41 "2005-12-06T19:52:21Z")

</div>

Ok, I think I've beat sort\_by{ rand } on large Arrays , by about 30%. I ended up with this:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.each { |v| h[rand(1000000000)] = v }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }

Explanation..

\* Hash works better than an Array of Arrays [[rand,x[0]],[rand,x[1]],...] because Array#\<=\> seems to be slow.

\* Got some speedup by avoiding Float#\<=\>, hence the Integer version of rand.

\* On rand(1000000000); chose 1billion rather arbitrarily to keep things out of the range of BigNum. Oddly, using 2^31-1 caused BigNums to show up. Ideally we'd use the largest FixNum, but I don't know how to retrieve that.

\* Bias should be minimal for most applications, even at rand(1Billion).

\* Can it be improved further???

Find my benchmark results, and script below.

--Steve

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle (10) 0.016000 0.000000 0.016000 ( 0.016000)  
shuffle2 (10) 0.000000 0.000000 0.000000 ( 0.000000)  
shuffle3 (10) 0.000000 0.000000 0.000000 ( 0.000000)  
sort (10) 0.000000 0.000000 0.000000 ( 0.000000)  
sort\_by (10) 0.000000 0.000000 0.000000 ( 0.000000)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle (100) 0.156000 0.000000 0.156000 ( 0.156000)  
shuffle2 (100) 0.047000 0.000000 0.047000 ( 0.046000)  
shuffle3 (100) 0.031000 0.000000 0.031000 ( 0.032000)  
sort (100) 0.125000 0.000000 0.125000 ( 0.125000)  
sort\_by (100) 0.031000 0.000000 0.031000 ( 0.031000)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle (1000) 1.625000 0.000000 1.625000 ( 1.625000)  
shuffle2 (1000) 0.656000 0.000000 0.656000 ( 0.672000)  
shuffle3 (1000) 0.266000 0.000000 0.266000 ( 0.281000)  
sort (1000) 2.094000 0.000000 2.094000 ( 2.093000)  
sort\_by (1000) 0.453000 0.000000 0.453000 ( 0.453000)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle (10000) 16.469000 0.032000 16.501000 ( 16.578000)  
shuffle2 (10000) 8.156000 0.000000 8.156000 ( 8.203000)  
shuffle3 (10000) 3.344000 0.047000 3.391000 ( 3.391000)  
sort (10000) 25.453000 0.000000 25.453000 ( 25.593000)  
sort\_by (10000) 4.765000 0.000000 4.765000 ( 4.796000)

#!/usr/bin/env ruby

require 'benchmark'

class Array

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

&nbsp;&nbsp;&nbsp;def shuffle2  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmparr = self.collect { |x| [rand(1000000000),x] }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmparr.sort.collect { |x| x[1] }  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def shuffle3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.each { |v| h[rand(1000000000)] = v }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }  
&nbsp;&nbsp;&nbsp;end

end

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

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

&nbsp;&nbsp;&nbsp;# run our benchmarks  
&nbsp;&nbsp;&nbsp;[Benchmark.bm](http://Benchmark.bm)(16) do |bb|

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# my method  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb.report("shuffle ("+n.to\_s+")") do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;100.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.shuffle  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# decorate, sort, undecorate  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb.report("shuffle2 ("+n.to\_s+")") do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;100.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.shuffle2  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# decorate, sort, undecorate with a hash  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb.report("shuffle3 ("+n.to\_s+")") do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;100.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.shuffle3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# Array's sort  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb.report("sort ("+n.to\_s+")") do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;100.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.sort { rand(10000) \<=\> 5000 }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# Enumerable's sort\_by  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb.report("sort\_by ("+n.to\_s+")") do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;100.times do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.sort\_by { rand }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n")

&nbsp;&nbsp;&nbsp;end

end

---

<div class="post-metadata">

**Author:** ![Uwe\_Schmitt](https://avatars.discourse-cdn.com/v4/letter/u/85f322/32.png) [@Uwe\_Schmitt](https://rubytalk.org/u/Uwe_Schmitt)\
**Post date:** [6 December 2005 16:32 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/42 "2005-12-06T16:32:38Z")

</div>

> > \> If you use random as sorting key, the result of a\<=\>b  
> > \> will differ each time you evaluate a\<=\>b.  
> > \> In my case I attach a random number to each item,  
> > \> then I sort my list according to this number and remove  
> > \> this 'decoration' afterwards.
> > 
> > run
> > 
> > &nbsp;&nbsp;ri Enum#sort\_by
> > 
> > and see what it do.

Thanks. As I told you before I'm new to ruby 😉

Greetings, Uwe

---

<div class="post-metadata">

**Author:** ![Joel\_VanderWerf1](https://avatars.discourse-cdn.com/v4/letter/j/94ad74/32.png) [@Joel\_VanderWerf1](https://rubytalk.org/u/Joel_VanderWerf1)\
**Post date:** [6 December 2005 19:56 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/43 "2005-12-06T19:56:20Z")

</div>

Stephen Waits wrote:

> \* On rand(1000000000); chose 1billion rather arbitrarily to keep things out of the range of BigNum. Oddly, using 2^31-1 caused BigNums to show up. Ideally we'd use the largest FixNum, but I don't know how to retrieve that.

2\*\*30 - 1 is reliably a fixnum (though I guess it might not be the biggest one on some platforms).

> **···**
>
> --  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

---

<div class="post-metadata">

**Author:** ![Stephen\_Waits1](https://avatars.discourse-cdn.com/v4/letter/s/57b2e6/32.png) [@Stephen\_Waits1](https://rubytalk.org/u/Stephen_Waits1)\
**Post date:** [6 December 2005 19:57 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/44 "2005-12-06T19:57:31Z")

</div>

Stephen Waits wrote:

> &nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
> &nbsp;&nbsp;&nbsp;&nbsp;self.each { |v| h[rand(1000000000)] = v }  
> &nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }

OOPS!

I forgot to deal with collisions in the hash! ☹

--Steve

---

<div class="post-metadata">

**Author:** ![Stephen\_Waits1](https://avatars.discourse-cdn.com/v4/letter/s/57b2e6/32.png) [@Stephen\_Waits1](https://rubytalk.org/u/Stephen_Waits1)\
**Post date:** [6 December 2005 20:04 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/45 "2005-12-06T20:04:13Z")

</div>

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:

&nbsp;&nbsp;&nbsp;def shuffle3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.each do |v|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000) until !h.has\_key?(k)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h[k] = v  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;end

shuffle3 (10000) 3.625000 0.016000 3.641000 ( 3.656000)  
sort\_by (10000) 5.250000 0.000000 5.250000 ( 5.312000)

--Steve

---

<div class="post-metadata">

**Author:** ![Mauricio\_Fernandez](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@Mauricio\_Fernandez](https://rubytalk.org/u/Mauricio_Fernandez)\
**Post date:** [6 December 2005 21:16 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/46 "2005-12-06T21:16:12Z")

</div>

> 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:
> 
> &nbsp;&nbsp;def shuffle3  
> &nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
> &nbsp;&nbsp;&nbsp;&nbsp;self.each do |v|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000) until !h.has\_key?(k)

This is not equivalent to  
&nbsp;&nbsp;&nbsp;&nbsp;begin  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000)  
&nbsp;&nbsp;&nbsp;&nbsp;end until !h.has\_key?

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

> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h[k] = v

You forgot  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }  
&nbsp;&nbsp;&nbsp;&nbsp;

> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;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  
&nbsp;&nbsp;def shuffle3  
&nbsp;&nbsp;&nbsp;&nbsp;h = Hash.new  
&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000)  
&nbsp;&nbsp;&nbsp;&nbsp;self.each do |v|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000) until !h.has\_key?(k)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h[k] = v  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }  
&nbsp;&nbsp;end

&nbsp;&nbsp;def shuffle4  
&nbsp;&nbsp;&nbsp;&nbsp;h = {}  
&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000)  
&nbsp;&nbsp;&nbsp;&nbsp;self.sort\_by{ k = rand(1000000000) while h.has\_key?(k); h[k] = k }  
&nbsp;&nbsp;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

> **···**
>
> On Wed, Dec 07, 2005 at 05:04:13AM +0900, Stephen Waits wrote:
> 
> --  
> Mauricio Fernandez

---

<div class="post-metadata">

**Author:** ![Stephen\_Waits1](https://avatars.discourse-cdn.com/v4/letter/s/57b2e6/32.png) [@Stephen\_Waits1](https://rubytalk.org/u/Stephen_Waits1)\
**Post date:** [6 December 2005 23:18 UTC](https://rubytalk.org/t/need-some-ruby-magic/22918/47 "2005-12-06T23:18:23Z")

</div>

Mauricio Fernández wrote:

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

Oops.. I thought too much like C. Now I understand that the loop is called 0 or more times, except in the case of "begin; end while" where it's 1 or more. Thank you for teaching me!

> After fixing shuffle3, I get:

I'm getting slightly different results, still better than sort\_by{rand} and better than your new shuffle4, but now only on larger Arrays. I wonder too how performance might vary when Enumerable is mixed into ADTs other than Array.

--Steve

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle3 (1000) 0.375000 0.000000 0.375000 ( 0.375000)  
shuffle4 (1000) 0.484000 0.000000 0.484000 ( 0.485000)  
sort\_by{rand} (1000) 0.328000 0.016000 0.344000 ( 0.344000)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle3 (10000) 3.906000 0.031000 3.937000 ( 3.953000)  
shuffle4 (10000) 5.531000 0.047000 5.578000 ( 5.594000)  
sort\_by{rand} (10000) 4.672000 0.109000 4.781000 ( 4.812000)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
shuffle3 (100000) 49.703000 0.328000 50.031000 ( 50.280000)  
shuffle4 (100000) 71.938000 0.453000 72.391000 ( 73.061000)  
sort\_by{rand} (100000) 62.000000 0.782000 62.782000 ( 63.451000)

module Enumerable

&nbsp;&nbsp;&nbsp;def shuffle3  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h = {}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.each do |v|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;begin  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end while h.has\_key?(k)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h[k] = v  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h.keys.sort.collect { |k| h[k] }  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def shuffle4  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h = {}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k = rand(1000000000)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.sort\_by{ k = rand(1000000000) while h.has\_key?(k); h[k] = k }  
&nbsp;&nbsp;&nbsp;end

end

[Previous page](https://rubytalk.org/t/need-some-ruby-magic/22918.md?page=2)