[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

just a question... (was: Re: [SUMMARY] One-Liners (#113

Benedikt Heinen

2/15/2007 2:38:00 PM

2 Answers

James Gray

2/15/2007 2:54:00 PM

0

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

Michael Ulm

2/16/2007 8:47:00 AM

0

Benedikt Heinen schrieb:
> 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}
>
> ?
>
> (which puts your random numbers from their range of 0.0-1.0 to a new
> range of -0.5 and 0.5 -- if you find it aesthetically more pleasing,
> you could of course use
>
> quiz.sort{2*rand-1.0}
>
> to make the range -1.0..1.0.
>
> >> 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...
>

Apart from being slower, it is also not producing a random permutation.
The results are skewed due to the way the sorting works.
Try this:

counter = Hash.new(0)
ar = [1, 2, 3]
10000.times {counter[ar.sort{rand-0.5}] += 1}
p counter

On my system, this just produced

{[2, 3, 1]=>1200, [2, 1, 3]=>1230, [3, 2, 1]=>2530,
[1, 2, 3]=>2533, [3, 1, 2]=>1264, [1, 3, 2]=>1243}

HTH,

Michael



--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-542, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------