From: "Jesús Gabriel y Galán" <jgabrielygalan@...>
Date: 2010-08-31T21:58:18+09:00
Subject: Re: A small problem for arrays

On Tue, Aug 31, 2010 at 2:34 PM, Robert Klemme
<shortcutter@googlemail.com> wrote:
> 2010/8/30 Jesús Gabriel y Galán <jgabrielygalan@gmail.com>:
>> On Mon, Aug 30, 2010 at 5:45 PM, Ruby Users Ruby Users <unc88@mail.ru> wrote:
>>> Robert Klemme wrote:
>>>> On 21.08.2010 18:27, Jean-Julien Fleck wrote:
>>>>> =>  [5, 6, 7]
>>>>>       Array Difference---Returns a new array that is a copy of the
>>>>>       original array, removing any items that also appear in other_array.
>>>>>       (If you need set-like behavior, see the library class Set.)
>>>>>
>>>>>          [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>   [ 3, 3, 5 ]
>>>>>
>>>>
>>>> Just adding to that: if Arrays are large and / or there are frequent set
>>>> operations needed then using class Set might yield better performance.
>
>>> -- Just adding to that: if Arrays are large and / or there are frequent
>>> set
>>> -- operations needed then using class Set might yield better
>>> performance.
>>> I do't much understand what you mean. If not hard can give you an
>>> example...
>>
>> It means that there are some operations that are more efficient in Set
>> than in Array, and that if you need a lot of those, it would be better
>> to use Set instead. For example, the intersection of two Sets is
>> faster than the intersection of two Arrays:
>>
>> require 'benchmark'
>> require 'set'
>>
>> n = 1_000
>>
>> a1 = (1..10_000).map {|x| rand(100)}
>> a2 = (1..10_000).map {|x| rand(100)}
>> s1 = Set.new.merge a1
>> s2 = Set.new.merge a2
>
> Here's another (probably more efficient) way to write that:
>
> a1 = Array.new(10_000) { rand(100) }
> a2 = Array.new(10_000) { rand(100) }
>
> s1 = a1.to_set
> s2 = a2.to_set
>
> It would probably be better to apply #uniq! on those Arrays (or do "a1
> = s2.to_a" after set creation) to get collections with identical
> sizes.

Yes, as an afterthought it would have been better to build two arrays
for example (1..5000).to_a and (3000..8000).to_a and randomize them.

>> Benchmark.bmbm do |x|
>>    x.report("array minus") do
>>      n.times {a1 - a2}
>>    end
>>    x.report("set &") do
>>      n.times {s1 & s2}
>>    end
>> end
>>
>> $ ruby set_bm.rb
>> Rehearsal -----------------------------------------------
>> array minus   0.900000   0.000000   0.900000 (  0.935476)
>> set &         0.280000   0.070000   0.350000 (  0.361684)
>> -------------------------------------- total: 1.250000sec
>>
>>                  user     system      total        real
>> array minus   0.880000   0.010000   0.890000 (  0.890552)
>> set &         0.280000   0.070000   0.350000 (  0.353687)
>
> I'm sorry, but you are comparing apples and oranges here:
>
> irb(main):001:0> a=[1,2,3]; b=[2,3,4]
> => [2, 3, 4]
> irb(main):002:0> a & b
> => [2, 3]
> irb(main):003:0> a.to_set & b.to_set
> => #<Set: {2, 3}>
> irb(main):004:0> a - b
> => [1]
> irb(main):005:0> a.to_set - b.to_set
> => #<Set: {1}>
>
> Operators - and & do not do the same thing.  But they behave identical
> for Array and Set!

I totally brainfarted !!! The reviewed version, with surprising
results, at least for me: Set#- is less efficient than Array#- (unless
I'm doing something wrong again):

require 'benchmark'
require 'set'

n = 1_000

a1 = (1..5_000).sort_by { rand }
a2 = (3_000..8_000).sort_by { rand }
s1 = a1.to_set
s2 = a2.to_set

Benchmark.bmbm do |x|
    x.report("array minus") do
      n.times {a1 - a2}
    end
    x.report("set minus") do
      n.times {s1 - s2}
    end
end


$ ruby set_bm.rb
Rehearsal -----------------------------------------------
array minus   1.370000   0.010000   1.380000 (  1.398643)
set minus    10.880000   3.060000  13.940000 ( 14.100127)
------------------------------------- total: 15.320000sec

                  user     system      total        real
array minus   1.410000   0.010000   1.420000 (  1.428664)
set minus    10.990000   3.070000  14.060000 ( 14.188415)

Could it be because Array is written in C, while Set is in Ruby
iterating over an Enumerable object? Did I do something wrong again?

Jesus.