From: James Edward Gray II <james@...>
Date: 2007-02-15T23:53:50+09:00
Subject: Re: just a question... (was: Re: [SUMMARY] One-Liners (#113))

On Feb 15, 2007, at 8:37 AM, Benedikt Heinen wrote:

> On Thu, 15 Feb 2007, Ruby Quiz wrote:
>> 	quiz.sort{rand}
>
>> Does that even work?  Let's ask IRb:
>>
>> 	>> quiz = (1..10).to_a
>> 	=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>> 	>> quiz.sort{rand}
>> 	=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]
>> 	>> quiz.sort{rand}
>> 	=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]
> [...]
>> That's not looking too random to me.
>> Let's think about this.  What does the above code do.  sort()  
>> compares elements
>> of the Array, arranging them based on the returned result.  We are  
>> suppose to
>> return a result of -1, 0, or 1 to indicate how the elements  
>> compare.  However,
>> rand() returns a float between 0.0 and 1.0.  Ruby considers  
>> anything over 0.0 to
>> be the 1 response, so most of the rand calls give this.  You can  
>> get a 0.0
>> result from time to time, but it will be a loner in a sea of 1s.
>> So what is the above code actually trying to do?  It's trying to  
>> compare a
>> selection of random numbers and sort on that instead.  Writing the  
>> process out
>> longhand it is:
>>
>> 	quiz.map { |e| [rand, e] }.sort.map { |arr| arr.last }
>
>
> Hmmm...  Not being aware of sort_by before, why this complicated?  
> What's wrong with
>
> 	quiz.sort{rand-0.5}
>
> ?

In the above example I was trying to show what sort_by() does behind  
the scenes.  In truth, you should just be using the simple:

   quiz.sort_by { rand }

> 	>> quiz.sort{rand-0.5}
> 	=> [4, 2, 3, 9, 7, 8, 1, 6, 5, 10]
> 	>> quiz.sort{rand-0.5}
> 	=> [9, 6, 2, 5, 1, 4, 3, 8, 7, 10]
> 	>> quiz.sort{rand-0.5}
> 	=> [3, 8, 10, 6, 9, 5, 1, 7, 2, 4]
> 	>> quiz.sort{rand-0.5}
> 	=> [4, 7, 10, 1, 9, 5, 2, 8, 6, 3]
> 	>> quiz.sort{rand-0.5}
> 	=> [8, 5, 10, 9, 2, 1, 7, 3, 4, 6]
> 	>> quiz.sort{rand-0.5}
> 	=> [6, 9, 2, 8, 1, 7, 4, 10, 3, 5]
> 	>> quiz.sort{rand-0.5}
> 	=> [3, 4, 5, 10, 7, 1, 8, 6, 2, 9]
>
> It does seem to find your "random" criteria, is shorter and uses  
> less calls...

Actually it's more calls.

You generate a random number for every comparison of elements and do  
math on them each time you do (additional calls).  The sort_by()  
method (and my longhand version) generates just one set of random  
numbers up front, one for each element.

Because of this, they are significantly faster on moderate-to-large  
size datasets:

#!/usr/bin/env ruby -w

require "benchmark"

data  = Array.new(100) { rand(100) }

TESTS = 10_000
Benchmark.bmbm do |results|
   results.report("sort:") { TESTS.times { data.sort { rand - 0.5 } } }
   results.report("map->sort->map:") do
     TESTS.times do
       data.map { |e| [rand, e] }.sort.map { |arr| arr.last }
     end
   end
   results.report("sort_by:") { TESTS.times { data.sort_by { rand } } }
end

# >> Rehearsal ---------------------------------------------------
# >> sort:             6.290000   0.000000   6.290000 (  6.315368)
# >> map->sort->map:   2.800000   0.000000   2.800000 (  2.800905)
# >> sort_by:          1.490000   0.000000   1.490000 (  1.485774)
# >> ----------------------------------------- total: 10.580000sec
# >>
# >>                       user     system      total        real
# >> sort:             6.330000   0.000000   6.330000 (  6.346076)
# >> map->sort->map:   2.820000   0.000000   2.820000 (  2.825896)
# >> sort_by:          1.490000   0.000000   1.490000 (  1.485223)

__END__

James Edward Gray II