Set.insert vs array << x unless array.include?(x)

thomthom

Tom,

very useful actually.
It really looks that the processsing in C is a lot faster than in Ruby.

Thanks

Fredo

Set class makes more processing in C?
What I'm wondering is, the Set class in SU Ruby is not the same Set class you get in Ruby 1.8.0. The Set class in Ruby 1.8.0 includes Enumerable and the set.rb looks to be a pure ruby class that mixes arrays and hashes. From my Ruby 1.8.0. installation, the Set class seem to be a pure Ruby implementation. But maybe the Set class that comes with SU is a C implementation...? Maybe that's why they replaced it?

thomthom

I thought the speed difference was that the Set class used a more efficient Hash lookup as oppose to the Array functions that has to iterate the array every time... but that's just guesswork...

fredo6

@thomthom said:

I thought the speed difference was that the Set class used a more efficient Hash lookup as oppose to the Array functions that has to iterate the array every time... but that's just guesswork...

You're right.
I personally use Hash whenever I want to store lists that have unique elements.
The list itself is obtained via Hash.values.

Maybe, as you are on this, you extend your benchmark to Hash and see how it compares with Set.

Fred

Chris Fullmer

Great info Thom! I had played around with sets and arrays before and I was not impressed with sets. But I did not experiment with amount of unique objects, which apparently has an adverse effect on arrays. Thanks,

Chris

thomthom

@unknownuser said:

Will have a look

Will have a look at that.

thomthom

I'll be damned!
Very interesting Jernej.

...looks like I need to do some more testing of my script and possibly refactor again.

So while the Array.include? is dead slow - the overhead of hash look-up is still faster than just adding everything into one big pile and so a single filtering afterwards...

thomthom

looking at the .uniq! source code: http://ruby-doc.org/core/classes/Array.src/M002215.html


/*
 *  call-seq;
 *     array.uniq! -> array or nil
 *  
 *  Removes duplicate elements from _self_.
 *  Returns <code>nil</code> if no changes are made (that is, no
 *  duplicates are found).
 *     
 *     a = [ "a", "a", "b", "b", "c" ]
 *     a.uniq!   #=> ["a", "b", "c"]
 *     b = [ "a", "b", "c" ]
 *     b.uniq!   #=> nil
 */

static VALUE
rb_ary_uniq_bang(ary)
    VALUE ary;
{
    VALUE hash, v, vv;
    long i, j;

    hash = ary_make_hash(ary, 0);

    if (RARRAY(ary)->len == RHASH(hash)->tbl->num_entries) {
        return Qnil;
    }
    for (i=j=0; i<RARRAY(ary)->len; i++) {
        v = vv = rb_ary_elt(ary, i);
        if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
            rb_ary_store(ary, j++, v);
        }
    }
    RARRAY(ary)->len = j;

    return ary;
}

thomthom

Jernej: how about larger iterations and higher number of random values?

Jernej Vidmar

How about using Array.uniq! method:

Test 1
t=Time.now;a=[];10000000.times{r=rand(10);a<<r unless a.include?(r)};puts Time.now - t
Result: 12.297
t=Time.now;a=Set.new;10000000.times{a.insert(rand(10))};puts Time.now - t
Result: 15.719
t=Time.now;a=[];10000000.times{r=rand(10);a<<r};a.uniq!; puts Time.now - t
Result: 7.753

Test 2
t=Time.now;a=[];100000.times{r=rand(10000);a<<r unless a.include?(r)};puts Time.now-t
Result: 40.97
t=Time.now;a=Set.new;100000.times{a.insert(rand(10000))};puts Time.now-t
Result: 0.377
t=Time.now;a=[];100000.times{r=rand(10000);a<<r};a.uniq!;puts Time.now-t
Result: 0.087

Jernej Vidmar

@thomthom said:

Jernej: how about larger iterations and higher number of random values?

t=Time.now;a=Set.new;10000000.times{a.insert(rand(10000))};puts Time.now - t
Result: 37.911
t=Time.now;a=[];10000000.times{r=rand(10000);a<<r};a.uniq!; puts Time.now - t
Result: 8.282

Still a winner?

thomthom

It's refactoring time!

Nice find!

RickW

That's all great (using .uniq!) until you start dealing with Point3d objects
In that case, always use Set.

TIG

....or make all of your Point3d's into arrays so they will sort!/uniq! etc as arrays...

thomthom

@tig said:

....or make all of your Point3d's into arrays so they will sort!/uniq! etc as arrays...

But is the overhead of converting the Point3d's into arrays and uniq! faster than using a Set?

TIG

Who knows ?
Time for you to do another test...

honoluludesktop

I probably don't know what I am doing, but I ran the following test, and obtained the attached results. I typically use array.push variable, and don't understand the situations when the other examples might be used. Btw, when I applied the other forms to my app, it failed in ways that leave me to believe that those forms are data sensitive. Can anyone explaine to a Ruby beginner what's up?

t=Time.now
a=[]
100000.times do r=rand(10000)
  a<<r
end
a.uniq!
puts Time.now-t

0.125

t=Time.now
a=[]
100000.times do r=rand(10000)
  a.push r
end
a.uniq!
puts Time.now-t

0.141

t=Time.now
a=[]
100000.times do r=rand(10000)
  a.push r
end
puts Time.now-t

0.094

t=Time.now
a=[]
100000.times do r=rand(10000)
  a<<r
end
puts Time.now-t

0.093

Set.insert vs array &lt;&lt; x unless array.include?(x)

Set.insert vs array << x unless array.include?(x)