skip to content

In Ruby, a booking check calls blocked_dates.include?(date) on a 50,000-element Array per request; why is that slow, and when do uniq, Set or Hash fit?

level: seniorimportance: should knowfreq 40%

answer

  1. Array#include? scans with ==
  2. uniq still returns an Array
  3. Set and Hash look up by hash and eql?
  4. build once, not per call
  5. [2].include?(2.0) vs Set[2]

basics

~20 s

Array#include? scans every element with ==, so each lookup is linear. uniq only removes duplicates and still returns an Array. A Set built once, or a Hash when each date needs a value, answers by hash lookup in roughly constant time.

solid answer

~40 s

`Array#include?` walks the array comparing with `==`, so 50,000 elements means up to 50,000 comparisons per request. `uniq` does not help: it spends a linear pass building a temporary hash and returns another Array, which `include?` scans again. Build a `Set` once, for example `BLOCKED = blocked_dates.to_set`, and `BLOCKED.include?(date)` becomes a hash lookup using `hash` and `eql?`. Use a Hash with `key?` when each date carries data, such as the reason it is blocked. Two traps: converting inside the request (`blocked_dates.to_set.include?`) is linear again, and Set uses `eql?`, so `[2].include?(2.0)` is `true` but `Set[2].include?(2.0)` is `false`. Contiguous blocks are better as ranges with `cover?`.

code

ruby · 15 lines
ruby
BLOCKED = Set.new(%w[2026-12-24 2026-12-25])  # built once at boot
REASONS = { "2026-12-25" => :holiday }  # when each date needs data

def blocked?(date)
  BLOCKED.include?(date)                 # hash lookup, not a scan
end

[2].include?(2.0)      # => true, Array uses ==
Set[2].include?(2.0)   # => false, Set uses eql?

slots = Set[[540, 600]]
slots.first << 660     # mutates a stored element
slots.include?([540, 600, 660])  # unreliable until...
slots.reset
slots.include?([540, 600, 660])  # => true

go deeper

for a junior

Recall that Array#include? scans every element while Set and Hash look up by hash, and that uniq returns an Array.

for a middle

Explain hash plus eql? lookup, why [2].include?(2.0) and Set[2].include?(2.0) differ, and the cost of building the set.

for a senior

Spot per-request conversions and mutable elements in production code, and pick Set, Hash or Range from the shape of the data.

for a principal

Weigh loading reference data into in-memory sets against querying the database, including refresh and memory per process.

## Why Array#include? is slow here `Array#include?(obj)` returns whether some element `== obj`. It has no index to consult, so it **walks the array from the start** until it finds a match or runs out: - A date that is not blocked, the common case, costs a comparison against **every** element. - With 50,000 blocked dates and one check per request, each request does tens of thousands of `==` calls. - The cost grows linearly with the list, so it gets worse as the clinic adds dates. ## Why uniq does not fix it `Array#uniq` returns a **new Array** without duplicates, keeping the first occurrence. Internally it builds a temporary hash, which is a linear pass, and then throws the hash away: 1. `blocked_dates.uniq.include?(date)` does a linear `uniq` and then a linear `include?`, so it is slower than before. 2. Deduplicating shrinks the list only if it has many duplicates; lookups stay linear. `uniq` is the right tool when you need an Array without duplicates, not when you need fast membership. ## Set and Hash: lookup by hash A **`Set`** stores only keys in a hash table. `Set#include?` (aliases `member?` and `===`) computes the argument's `hash`, jumps to that bucket and confirms with `eql?`, so a lookup costs about the same for 50 or 50,000 elements. In Ruby 4.0 Set is a core class written in C. | Structure | Membership call | Typical cost | Comparison | |---|---|---|---| | `Array` | `include?` | linear scan | `==` | | `Array#uniq` result | `include?` | linear scan after a linear build | `==` | | `Set` | `include?` | hash lookup | `hash` + `eql?` | | `Hash` | `key?` / `include?` | hash lookup | `hash` + `eql?` | | `Range` | `cover?` | two comparisons | `<=>` | Choose a **Hash** instead of a Set when each key carries data, such as `{"2026-12-25" => :holiday}`; `key?` answers membership and `[]` returns the reason. ## Traps when switching - **Build once.** Keep the Set in a constant or a memoised object. `blocked_dates.to_set.include?(date)` inside the request rebuilds it every time, a linear cost again. - **`eql?` is stricter than `==`.** `[2].include?(2.0)` is `true`, but `Set[2].include?(2.0)` is `false`, because `2.eql?(2.0)` is `false`. Normalise key types, for example all ISO strings or all integers, before storing. - **Do not mutate stored elements.** Set assumes an element's hash does not change while stored. If you mutate one, such as an Array inside the Set, lookups become unreliable until you call `Set#reset`, which reindexes the set. - **Strings are copied.** When an unfrozen String is added, the Set stores a frozen copy, so later changes to your original string do not reach the set. - **Identity comparison** is available with `compare_by_identity` when elements should match only as the same object. ## Measuring before switching The switch is worth making when the list is large and the check runs often, as here. For a list of a dozen values checked once per request, `Array#include?` is fine and keeps the code simple. When in doubt: 1. Count how often the check runs per request, not just how long the list is. 2. Compare the cost of building the Set against the number of lookups it serves. 3. Keep the structure where it is reused: a constant for static data, a cache with a refresh for data an admin edits. ## When a range beats both If blocked dates form contiguous blocks, such as a two-week closure, a range of ordinal day numbers or ISO strings with `cover?` answers in two comparisons and stores nothing per date. Converting an endless range to a set is impossible anyway: `(1..).to_set` raises `RangeError`. ## Summary for the clinic 1. Load blocked dates once into `BLOCKED = Set.new(rows)`, or a Hash when reasons matter. 2. Keep the key type consistent with what requests pass in. 3. Represent long closures as ranges and check them with `cover?` before the set.

  • Why is blocked_dates.to_set.include?(date) inside a request no better than Array#include??
    `to_set` walks the whole array to build the hash table, which is linear, and the table is thrown away after one lookup. The hash lookup only pays off when the Set is built once and reused, for example in a constant or a cache refreshed when dates change.
  • When would you keep a Hash instead of a Set for blocked dates?
    When each date carries information, such as the reason or who blocked it. A Hash answers membership with `key?` at the same cost and returns the value with `[]` or `fetch`, so you avoid a second lookup structure.

An Array is a paper guest list read from the top for every visitor. A Set is a coat check: the ticket number, like an object's hash, leads straight to one hook, and the attendant still checks the coat, like eql?, before handing it over.

saying these in an interview costs you the question

  • uniq makes include? fast because it removes duplicates
  • Set#include? compares with == just like Array#include?
  • Building a Set inside each request still gives constant-time checks
  • Mutating an element inside a Set updates its lookup automatically
  • Array#include? stops early, so it is constant time on average