From: Robert Klemme <shortcutter@...>
Date: 2010-08-31T22:33:45+09:00
Subject: Re: A small problem for arrays

2010/8/31 Jesús Gabriel y Galán <jgabrielygalan@gmail.com>:
> 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?

Probably.  Could be that your collections were not large enough to
show the advantage of Set or value distributions are unfortunate for
Set.

Please keep in mind that performance is not the only advantage of
using Set - it's also the semantics to have each value only once in
the set and it helps documenting requirements.

> Did I do something wrong again?

Not as far as I can see.  I changed it a bit to look at different sizes:

require 'benchmark'
require 'set'

n = 100

Benchmark.bmbm 30 do |x|
  size = 1000

  while size < 100_000

    a1 = (1..size).sort_by { rand }
    a2 = ((size / 2)..(size / 2 + size)).sort_by { rand }
    s1 = a1.to_set
    s2 = a2.to_set

    x.report("array minus #{size}") do
      n.times {a1 - a2}
    end

    x.report("set minus #{size}") do
      n.times {s1 - s2}
    end

    x.report("array & #{size}") do
      n.times {a1 & a2}
    end

    x.report("set & #{size}") do
      n.times {s1 & s2}
    end

    size *= 2
  end
end

Kind regards

robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/