Card 05/ 07
Choosing a Structure Out of Habit
Free appointment slots kept in a set out of habit turn "the next free slot after ten" into a scan of every slot.
Choosing the structure you always reach for works until the program needs an operation that structure does not offer, and then the missing operation is written by hand as a scan of every item. This card covers how that habit shows itself, using a clinic's free appointment slots, why a hash set cannot answer a question about order, and the fix: go back to the list of operations.
A clinic keeps its free slots for the day as minutes after opening: 15, 40, 70, 95, 130, 160, 200 and 245. The first question anyone asked was "is the slot at 70 free?", and a Python set, a hash set, answers that in O(1) on average, so the slots went into a set. Then the booking page asked for the first free slot at or after a given time. A hash set keeps its keys in no order, so the only way to answer is to look at every slot and keep the smallest that qualifies.
The listing writes that scan, then answers the same question from a sorted list with bisect_left, which halves the list until it finds the position of the first slot not smaller than the time. Each version counts the keys it compares.
from bisect import bisect_left
class CountedKey(int):
examined = 0
def _count(self):
CountedKey.examined += 1
def __lt__(self, other):
self._count()
return int(self) < int(other)
def __ge__(self, other):
self._count()
return int(self) >= int(other)
__hash__ = int.__hash__
def first_free_by_scan(slots, time):
best = None
for slot in slots:
if slot >= time and (best is None or int(slot) < int(best)):
best = slot
return best
def first_free_by_search(sorted_slots, time):
index = bisect_left(sorted_slots, time)
return sorted_slots[index] if index < len(sorted_slots) else None
def examined(find, slots, time):
CountedKey.examined = 0
slot = find(slots, time)
return slot, CountedKey.examined
minutes = [15, 40, 70, 95, 130, 160, 200, 245]
slot_set = {CountedKey(m) for m in minutes}
slot_list = sorted(CountedKey(m) for m in minutes)
for time in (50, 100, 250):
scan_slot, scan_keys = examined(first_free_by_scan, slot_set, time)
search_slot, search_keys = examined(first_free_by_search, slot_list, time)
print(f"first free at or after {time}: scan found {scan_slot or 'no slot'} after {scan_keys} keys, "
f"search found {search_slot or 'no slot'} after {search_keys} keys")
for count in (1_000, 1_000_000):
keys = [CountedKey(5 * i) for i in range(count)]
time = 5 * (count // 2) + 1
_, scan_keys = examined(first_free_by_scan, set(keys), time)
_, search_keys = examined(first_free_by_search, keys, time)
print(f"{count:,} slots: scan examined {scan_keys:,} keys, search examined {search_keys}")first free at or after 50: scan found 70 after 8 keys, search found 70 after 3 keys
first free at or after 100: scan found 130 after 8 keys, search found 130 after 3 keys
first free at or after 250: scan found no slot after 8 keys, search found no slot after 3 keys
1,000 slots: scan examined 1,000 keys, search examined 10
1,000,000 slots: scan examined 1,000,000 keys, search examined 20Both find 70, 130 and no slot. The scan compared all 8 keys for every query, and the search compared 3. The table shows what happens as the day fills up, with evenly spaced slots and a time in the middle.
| Slots | Keys examined by the scan | Keys examined by the search |
|---|---|---|
| 8 | 8 | 3 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
The scan is O(n) and the search O(log n), and nothing about the set was wrong for the question it was chosen for. It was chosen for one operation and then asked a different kind of question.
The fix is the method, applied again: list the operations, including the new one. "The next slot at or after a time" needs the keys in order, so the slots belong in a sorted list searched by halving while they rarely change, or in Java's TreeMap, whose ceilingKey returns the smallest key at or above a value in O(log n), when slots are added and booked all day.
To spot the habit, look for a loop over a whole set or dictionary that keeps the smallest, the largest or the next value. That loop is an operation the structure does not offer, written by hand.
← → move through sections and cards