Sets and set operations

A set is a hash of keys

A Set is a collection with no duplicates and no order. Under the hood it is a hash whose values are all true, so a lookup costs the same as a hash lookup instead of a scan.

ruby -e 'require "set"; p Set[1, 2, 2, 3].size'

set is part of the standard library but not loaded by default; the require at the top of the file is expected. Ruby 3.2 and newer also has Set available without a require in some contexts, but writing it explicitly costs nothing.

Union, intersection, difference

ruby -e 'require "set"; p Set[1, 2] | Set[2, 3]'

#<Set: {1, 2, 3}>

ruby -e 'require "set"; p Set[1, 2] & Set[2, 3]'

#<Set: {2}>

ruby -e 'require "set"; p Set[1, 2, 3] - Set[2]'

#<Set: {1, 3}>

ruby -e 'require "set"; p Set[1].subset?(Set[1, 2])'

true

The four operations cover the questions a program asks about groups: which tags are on both lists, which are only on one, which are on all of them. superset? and intersect? are the other two predicates, and to_a turns the result back into an array for output.

When a set beats an array scan

array.include?(value) walks the array, so a loop over one list that checks another is quadratic. Turn the list that gets checked into a set once and the loop becomes linear:

require "set" allowed = Set.new(%w[admin editor]) users = ["admin", "guest", "editor"] puts users.select { |role| allowed.include?(role) }.inspect

ruby set_demo.rb

["admin", "editor"]

With three items the array would be fine; with thirty thousand the set is the difference between a page that loads and one that times out. The code reads the same either way, which is why the change is easy to make late.

What to watch for

A set uses eql? and hash to decide identity, the same as a hash key. A class with a custom == but no hash keeps two equal objects as two members.

A set has no order, so first is a request the data cannot answer. Call to_a and sort, or keep the array when the order carries meaning.

Next: Lazy enumerators

Article author: Arthur Isaev