A Quick Intro to Ruby's Set, Part 2: Object Lookups and Efficiency
Tags: ruby, tutorial, set, datastructures
Published: 2019-10-20 05:13:27

---
title: "A Quick Intro to Ruby's Set, Part 2: Object Lookups and Efficiency"
published: true
description: a quick intro to ruby sets: different object lookup methods and benchmarking their efficiency
tags: ruby, tutorial, set, datastructures
series: "A Quick Intro to Ruby's Set"
---

Continuing from the previous article, we will now explore some of Set's methods, and compare their benchmarks with equivalent operations on arrays.

To review, some key details about sets:

* All objects in a Set are **guaranteed unique** *(arrays can have duplicates)*
* Objects in a Set are **not** ordered *(arrays are ordered by index)*
* Sets are built on top of Hashes for **super-fast object lookup** *(arrays are just dynamic arrays under-the-hood)*

Or, [summarized by RubyGuides' article on the Set class:](https://www.rubyguides.com/2018/08/ruby-set-class/)

> A set is a class that stores items like an array…
> 
> But with some special attributes that make it  **10x faster**  in specific situations!
>
> On top of that:
> 
> All the items in a set are  **guaranteed to be unique**.

As we will see, my particular benchmarks don't quite reach 10x faster efficiency--but we'll explore situations where sets are certainly **more** efficient than an array!


# Overview

In this second article, we'll compare the following operations between Ruby sets and arrays:

**Operations where sets are _faster_ than arrays:**
* `set.include?()` vs. `array.include?()`
* `set.add()` vs. `array.push()`
* `set.delete()` vs. `array.delete()`
* `set.subset?()` vs. `(array1 & array2) == array2`

**Operations where sets are _slower_ than arrays:**
* `set.replace()` vs. `array.replace()`
* `set1 == set2` vs. `array1 == array2`


# Operations where sets are _faster_ than arrays

Let's start with methods where sets are more efficient than arrays.

**Note: If you're coding along at home, remember to include `require 'benchmark'` to avoid an error with the `Benchmark` class!**

## `set.include?()` vs. `array.include?()`
Since sets are built on top of Ruby's hash, the `.include()` method is where they really shine. It simply checks if an element is present, returning a boolean.

The [RubyGuides article above](https://www.rubyguides.com/2018/08/ruby-set-class/) reports these benchmarks:

```ruby
set   include: 8381985.2 i/s
array include: 703305.5  i/s - 11.92x  slower
```
And goes on to explain:
> The reason for this difference is that  **an array has to check every single element**...

> ...if you have a 1 million element array it's going to be checking 1 million elements every time you call  `include?`.

> A set doesn't have to do that.

Here's how we'll be testing it, using the same sets and arrays from our previous article. Each operation will be performed within `Benchmark.bm` 5 million times, and will be reported with `.report`. *(The large spacing is for pretty-printing in the console!)*

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]

Benchmark.bm(34) do |x|
    x.report("Set   .include? (beginning)       :")     { n.times do; filter_set.include?("a")   ; end}
    x.report("Array .include? (beginning)       :")     { n.times do; filter_array.include?("a")   ; end}
    x.report("Set   .include? (middle)          :")     { n.times do; filter_set.include?("they"); end}
    x.report("Array .include? (middle)          :")     { n.times do; filter_array.include?("they"); end}
    x.report("Set   .include? (end)             :")     { n.times do; filter_set.include?("at")  ; end}
    x.report("Array .include? (end)             :")     { n.times do; filter_array.include?("at")  ; end}
end
```

Above, we have the array checking for an element at the beginning, middle, and end of the array. For kicks, we have the set looking up elements that are *hard-coded* in the same order--but, **because sets are built on top of hashes**, there is no object order in a set!

Here's our output:

```
                                         user     system      total        real
Set   .include? (beginning)       :  0.796039   0.001551   0.797590 (  0.799956)
Array .include? (beginning)       :  0.632907   0.000869   0.633776 (  0.637059)
Set   .include? (middle)          :  0.786981   0.000610   0.787591 (  0.788172)
Array .include? (middle)          :  1.294061   0.001416   1.295477 (  1.298378)
Set   .include? (end)             :  0.792309   0.000866   0.793175 (  0.795283)
Array .include? (end)             :  2.476954   0.002786   2.479740 (  2.484839)
```

As expected, the array takes longer to find the closer the element is to the end. Meanwhile, the set's lookup time is essentially constant.

**In the worst-case scenario, `set.include?()` will perform over 3x faster than `array.include?()`.**

## `set.add()` vs. `array.push()`
Next, let's compare the `set.add()` method introduced in the previous article to `array.push()`. 

The array `push` method will add an element to the end of an array--this is the most efficient way to add elements (assuming you [don't have to increase the array's capacity under-the-hood](https://www.sitepoint.com/rubys-missing-data-structure/)). 

`set.add()`, on the other hand, simply adds a key-value pair to its under-the-hood hash, with the key being the added element, and its value being a boolean `true`.

**Note:** In this and several following tests, you'll notice that these operations include a first step of duplicating the original set/array. This is to ensure that the _same_ operation is being performed--as opposed to the set adding an element _only once_ and then rejecting it the other 4999999 times!

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]

Benchmark.bm(34) do |x|
    x.report("Set   .add  (successful)          :") { 
        n.times do
            set = filter_set
            set.add("big")
        end
    }
    x.report("Array .push (successful)          :") { 
        n.times do
            array = filter_array
            array.push("big")                                     
        end
    }
    x.report("Set   .add  (failed)              :") { 
        n.times do
            set = filter_set
            set.add("they")
        end
    }
    x.report("Array .push (if not present)      :") { 
        n.times do
            array = filter_array
            if !array.include?("they")
                array.push("they")
            end   
        end
    }
end
```

Here's our output:

```
                                         user     system      total        real
Set   .add  (successful)          :  0.929103   0.000749   0.929852 (  0.931718)
Array .push (successful)          :  0.909708   0.094546   1.004254 (  1.005897)
Set   .add  (failed)              :  0.979433   0.029193   1.008626 (  1.011531)
Array .push (if not present)      :  1.327389   0.001286   1.328675 (  1.330673)
```

At  best, our set adds elements approximately as fast as an array's `push`. **In situations where we need to check an array for an element before adding it, we see sets outperforming arrays by about 36%.**


## `set.delete()` vs. `array.delete()`

Both `set.delete()` and `array.delete()` require a lookup for an element before removing it, so this is a great comparison of their equivalent abilities!

Here's our code:

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]

Benchmark.bm(34) do |x|
    x.report("Set   .delete (beginning)         :") { 
        n.times do 
            set = filter_set
            set.delete("a")           
        end
    }
    x.report("Array .delete (beginning)         :") { 
        n.times do
            array = filter_array
            array.delete("a")
        end
    }
    x.report("Set   .delete (middle)            :") { 
        n.times do 
            set = filter_set
            set.delete("they")        
        end
    }
    x.report("Array .delete (middle)            :") { 
        n.times do
            array = filter_array
            array.delete("they")  
        end
    }
    x.report("Set   .delete (end)               :") { 
        n.times do 
            set = filter_set
            set.delete("at")          
        end
    }
    x.report("Array .delete (end)               :") { 
        n.times do
            array = filter_array
            array.delete("at")    
        end
    }
end
```

Once again, we're measuring an array's ability to delete elements at their beginning, middle, and end (and illustrating that sets have no such order).

Here's our output:

```
                                         user     system      total        real
Set   .delete (beginning)         :  0.812703   0.000889   0.813592 (  0.816582)
Array .delete (beginning)         :  1.932468   0.001862   1.934330 (  1.938841)
Set   .delete (middle)            :  0.811337   0.000912   0.812249 (  0.814055)
Array .delete (middle)            :  2.053270   0.001698   2.054968 (  2.059913)
Set   .delete (end)               :  0.813986   0.000986   0.814972 (  0.816330)
Array .delete (end)               :  2.203437   0.002076   2.205513 (  2.210077)
```

**As expected, sets can delete elements in constant time.** Interestingly, arrays are able to delete elements at the end almost as fast as ones at their beginning!


## `set.subset?()` vs. `(array1 & array2) == array2`

One of sets' most useful features is the `subset?` method. A subset is a set where all of its elements are also elements of its superset.

While arrays don't have an exactly equivalent method, [this excellent StackOverflow answer](https://stackoverflow.com/a/10567468) illustrates how the array `&` method can be used for the same effect.

Here's our code:

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
sub_set = Set["a", "they", "at"]
sub_array = ["a", "they", "at"]
replace_set = Set["big", "sword", "knight"]
replace_array = ["big", "sword", "knight"]

Benchmark.bm(34) do |x|
    x.report("Set   .subset?          (true)    :")     { n.times do; sub_set.subset?(filter_set)                       ; end}
    x.report("Array (a1 & a2) == a2   (true)    :")     { n.times do; (filter_array & sub_array) == sub_array           ; end}
    x.report("Set   .subset?          (false)   :")     { n.times do; replace_set.subset?(filter_set)                   ; end}
    x.report("Array (a1 & a2) == a2   (false)   :")     { n.times do; (filter_array & replace_array) == replace_array   ; end}    
end
```

Our code compares sets and arrays in situations where `subset?` and `(a1 & a2) == a2` return both true and false.

Here's our output:

```
                                         user     system      total        real
Set   .subset?          (true)    :  2.076477   0.001450   2.077927 (  2.080519)
Array (a1 & a2) == a2   (true)    :  7.961141   0.180642   8.141783 (  8.158982)
Set   .subset?          (false)   :  1.554540   0.001360   1.555900 (  1.558715)
Array (a1 & a2) == a2   (false)   :  5.280627   0.006986   5.287613 (  5.297066)
```

Wow! **In both situations, we see sets performing `subset?` over 3x as fast as the array's equivalent!**



# Operations where sets are _slower_ than arrays

Now, let's turn our attention to some situations where sets *do not* perform as well as arrays.

Unfortunately, I cannot offer under-the-hood explanations for these results at this time. **Please feel free to comment below and share your wisdom of why arrays outperform sets in the following operations! :)**

## `set.replace()` vs. `array.replace()`

In both structures, the `replace` method [completely replaces the contents of the given structure with the elements from a supplied enumerable](https://ruby-doc.org/stdlib-2.6.5/libdoc/set/rdoc/Set.html#method-i-replace). In our code, we will be replacing a set with a set, and an array with an array.

Here's our code:

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
replace_set = Set["big", "sword", "knight"]
replace_array = ["big", "sword", "knight"]

Benchmark.bm(34) do |x|
    x.report("Set   .replace                    :")     { n.times do; filter_set.replace(replace_set)       ; end}
    x.report("Array .replace                    :")     { n.times do; filter_array.replace(replace_array)   ; end}
end
```

Here's our output:

```
                                         user     system      total        real
Set   .replace                    :  2.318287   0.001841   2.320128 (  2.327267)
Array .replace                    :  0.441079   0.000528   0.441607 (  0.442994)
```

Ouch! **Arrays implement `replace` 5x faster than sets!** As stated above, I'd love to have someone fill me in on why!



## `set1 == set2` vs. `array1 == array2`

Finally, let's look at `==`, where each pair of structures is checked for having the same elements--and for arrays, the same order. Once again, we will benchmark both true and false situations for each.

Here's our code:

```ruby
n = 5000000

filter_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
filter_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
match_set = Set["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
"them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
match_array = ["a", "an", "the", "and", "is", "of", "to", "be", "in", "they", "their", 
    "them", "or", "if", "this", "like", "had", "but", "what", "with", "at",
]
replace_set = Set["big", "sword", "knight"]
replace_array = ["big", "sword", "knight"]

Benchmark.bm(34) do |x|
    x.report("Set   ==  (true)                  :")     { n.times do; filter_set == match_set       ; end}
    x.report("Array ==  (true)                  :")     { n.times do; filter_array == match_array   ; end}
    x.report("Set   ==  (false)                 :")     { n.times do; filter_set == replace_set     ; end}
    x.report("Array ==  (false)                 :")     { n.times do; filter_array == replace_array ; end}
end
```

Here's our output:

```
                                         user     system      total        real
Set   ==  (true)                  :  7.219614   0.004376   7.223990 (  7.234709)
Array ==  (true)                  :  4.119128   0.003112   4.122240 (  4.128884)
Set   ==  (false)                 :  1.097661   0.000751   1.098412 (  1.099235)
Array ==  (false)                 :  0.391299   0.000482   0.391781 (  0.393029)
```

**In the best case, array's perform better than sets by about 75% when checking for true cases--and at worst, for false situations, arrays check about 275% faster than sets!**  Equality is definitely a situation to prefer arrays over sets. (Anyone care to explain why? <3)



# Conclusion

Now you're more familiar with Set's methods and cases where they may be advantageous to arrays! The two key situations to look for are:
* **Needing to check via `include?` in a collection of unique elements**
* **Needing to check for subsets of elements**

Thanks for reading!

## Links and Sources

[Excellent introduction to Ruby Sets by Al Scott](https://spin.atomicobject.com/2012/09/04/when-is-a-set-better-than-an-array-in-ruby/)

[Ruby docs - Sets](https://ruby-doc.org/stdlib-2.6.5/libdoc/set/rdoc/Set.html)

[RubyGuides intro to Sets](https://www.rubyguides.com/2018/08/ruby-set-class/)

[DotNetPerls - Ruby Set examples](https://www.dotnetperls.com/set-ruby)


### Got any tips, tricks, or instances where you like to use sets? Please feel free to share in the comments below!