Finding One Thing Among Many

Scanning a pile costs whatever the pile holds. Computing where the thing lives costs the same whatever the pile holds, and the whole subject is about earning that second option.

There are two ways to find something. Look through the pile until it turns

up, or know where it is and go there.

The first costs what the pile holds. The second costs nothing much at all,

and the entire difficulty is earning the right to use it.

FIG 1Finding one item among a million

	items examined	needs the data in order	cost grows with the coll	memory used
scan an unordered list	500000	0	1	1
halve a sorted list	20	1	1	1
index a block by positio	1	0	0	2
compute a position from	1	0	0	1

The first column is the number of items looked at to find one among a million, and the last codes memory as proportional to what is stored or to every key that could exist. The first marked cell is the whole promise: one item examined, not five hundred thousand and not twenty. The second marked cell is the zero that matters most, since a cost that does not grow with the collection means the system does not get slower as it gets more useful. The third row buys that with memory it cannot afford for real keys, and the fourth row is the rest of this course.

The three ways and what they cost

The second row is already good. Twenty comparisons for a million items is the

halving search, and it is why sorted order is worth keeping.

But twenty is not one, the twenty becomes thirty at a thousand million, and

the order has to be maintained on every insertion. The third and fourth rows

do not examine anything.

FIG 2The same lookup, two ways

step	step	scanning a list of a million	indexing a block by position
1	1	read the first item, compare, not it	multiply the position by the item size
2	2	read the second item, compare, not it	add that to the start address
3	3	read the third item, compare, not it	read that address
4	...	and so on, about half a million times	finished
5	cost	grows with the collection	the same at any size

5 steps

The right hand column never mentions how many items are stored, which is the whole point: the arithmetic that turns a position into an address takes the same time whether the block holds ten slots or ten million. The left hand column mentions the size in every line. These are not a slow and a fast version of the same operation, they are different operations, and the second one is available only when the position can be worked out from the key without consulting the collection.

When the key is already a position

If the keys are small whole numbers, there is nothing left to do. Make a

block with one slot per possible key and put each item at its own number.

FIG 3The direct table, and the memory it demands

: the key, used directly as the position
: the size of one slot in bytes
: the number of keys that could possibly occur, not the number stored
: the memory the table occupies

The first expression is why the lookup is instant, and the second is why this only works for small key ranges. Storing a thousand records under keys that are nine digit identifiers needs a thousand million slots, almost all empty, which is gigabytes of nothing to hold a few kilobytes of something. For keys that are email addresses or file paths the count of possible keys is larger than any memory that will ever exist. So the direct table is correct, instant, and unavailable for almost every key anybody actually has.

FIG 4The three options, measured

python

import bisect, random, time

n = 100_000
keys = random.sample(range(10_000_000), n)
as_list, as_sorted, as_dict = keys, sorted(keys), {k: 1 for k in keys}
wanted = random.sample(keys, 1000)

def timed(name, f):
    t = time.perf_counter()
    for k in wanted:
        f(k)
    print(name, round(time.perf_counter() - t, 4))

timed('scan', lambda k: k in as_list)
timed('halving', lambda k: as_sorted[bisect.bisect_left(as_sorted, k)] == k)
timed('dictionary', lambda k: as_dict[k])

days = [None] * 7                      # a direct table, one slot per possible key
days[3] = 'Thursday'
print(days[3])

The same lookup is performed against a list, against a sorted list with the halving search, and against a dictionary. The list is thousands of times slower than the other two at a hundred thousand items, and the gap grows with the collection. The dictionary and the halving search look similar on this one run, and they are not the same: at a thousand million items the halving search takes half as many comparisons again, while the dictionary takes exactly what it took here. The last two lines show the direct table, which is what a dictionary is pretending to be.

The gap

Real keys are email addresses, order identifiers, paths and words. There are

astronomically many of them possible and a handful actually stored, so a slot

per possible key is not an option.

What is needed is a rule that turns any key into a position in a small block,

computed from the key alone. Since there are more possible keys than

positions, such a rule must sometimes send two keys to the same place.

That is not a flaw to be engineered away. It is a certainty, and the next two

lessons build the rule and then deal with its consequence.

Recap

Searching by looking at items costs in proportion to how many there are, and no amount of care inside the loop changes that.
Computing a position from the key and going straight to it costs the same whether the collection holds ten items or ten million, because nothing is examined on the way.
That second option is only available when the key can be turned into a position, which is immediate for small whole numbers and is the entire problem for everything else.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextTurning a Key Into an Address →