When a task repeatedly asks whether a value occurred, a Python set can replace a list of observations. A set retains one copy of each distinct value, so duplicates no longer enlarge the collection being searched. section 2.3.2
Searching recorded temperatures
A station’s temperature list contained 141,082 readings but only 400 distinct values. Converting it with `set(first_all_temperatures)` reduced the collection about 350-fold. Membership checks for two temperatures then took 62.1 ns and 26.6 ns per loop in the reported runs. Much of this improvement came from removing duplicates, not merely changing the lookup mechanism. section 2.3.2
To isolate lookup behavior, compare a list and set containing the same 100,000 distinct integers. In the reported runs, finding 50,000 took 455 µs in the list versus 40.1 ns in the set; checking for absent 500,000 took 936 µs versus 28.1 ns. CPython implements sets using hashes, making membership lookup roughly constant-time as a practical intuition, though not a guarantee. A dictionary offers similar key lookup. For an interval query, an ordered list with bisection can be preferable to checking each candidate in a set. section 2.3.3
a_list_range = list(range(100000)) a_set_range = set(a_list_range) %timeit 50000 in a_list_range %timeit 50000 in a_set_range %timeit 500000 in a_list_range %timeit 500000 in a_set_range
Run the equal-size list and set membership checks to separate the effect of hash lookup from the effect of removing duplicates. section 2.3.3
