Lookup in One Pass

Many questions about a list are really questions about two of its items. Do any two prices add up to the money I have? Has this visitor been here before? Which of these words are made of the same letters? The obvious program compares every item with every other, and for a long list that is far too much work. There is a way to answer most of these questions while reading the list once: remember what has gone past, in a form you can ask a question of at once. This module is about that one idea, and about the choice that makes it work, which is what to remember.

Before this, you can: count with a dictionary and test membership with a set; loop with the position and the item together, and sort with a key; count the work a loop does by asking what happens to each item.

By the end you will be able to say what comparing every pair costs, turn a question about pairs into a lookup, put the asking and the storing in the right order, spot a repeat as it happens, group items by something they share, and choose that something.

Before you read on, decide what this prints:

prices = [8, 3, 5, 12, 7]
found = False
for a in prices:
    for b in prices:
        if a + b == 10:
            found = True
print(found)

True

It says that two of the prices add up to 10, and it is right: 3 and 7 do. But look at what else would make it say so. It also tried 5 with 5, the same price taken twice, and found 10 that way as well. With the list [8, 5, 12] it would still print True, although there is only one 5. A program about pairs has to be careful about what counts as a pair. This one is wrong in a way that does not show on its first test, and it is slow. The rest of the lesson fixes both.

Every pair is too many

To consider each pair of different positions once, the second loop starts just after the first:

def any_pair(prices, total):
    comparisons = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            comparisons = comparisons + 1
            if prices[i] + prices[j] == total:
                return True, comparisons
    return False, comparisons

print(any_pair([8, 3, 5, 12, 7], 10))
print(any_pair([8, 5, 12], 10))
print(any_pair(list(range(1000)), -1))

(True, 7)
(False, 3)
(False, 499500)

This one is correct: a position is never paired with itself. It is still slow. A list of 1,000 numbers has 499,500 pairs, and when no pair adds up, every one of them is tried. In general n items have n × (n − 1) / 2 pairs: for ten times the items, about a hundred times the work.

Ask for what you need

Turn the question round. Standing at a price of 3 with a target of 10, you do not need to try every other price. You know exactly what you are looking for: a 7. The only question is whether there is one.

"Is there a 7?" is a membership test, and a set answers a membership test without looking through its items. It works out, from the value itself, where that value would be kept, and looks there. So the time an answer takes does not grow with the size of the set. (That is how it goes on average, for ordinary values such as numbers and strings. It is not a promise about every single lookup: now and then several values land in the same place and have to be told apart.) So keep a set of the prices that have gone past, and at each price ask whether its partner, the total minus the price, is in the set.

def has_pair(prices, total):
    seen = set()
    for price in prices:
        if total - price in seen:
            return True
        seen.add(price)
    return False

print(has_pair([8, 3, 5, 12, 7], 10), has_pair([8, 5, 12], 10), has_pair([5, 5], 10))

True False True

One loop. Each price is looked at once: one subtraction, one question, one add. For 1,000 prices that is about 1,000 steps where the two loops took up to 499,500.

It did not look for pairs. It looked, at each price, for the one value that would complete a pair, in a structure built to answer exactly that. Nearly every problem in this module is solved by the same move: work out what you need, and ask for it.

Look, then store

The order of the two lines inside the loop matters. has_pair asks about a price before adding it to the set. Swap them and see:

def stores_first(prices, total):
    seen = set()
    for price in prices:
        seen.add(price)
        if total - price in seen:
            return True
    return False

print(stores_first([8, 5, 12], 10), has_pair([8, 5, 12], 10))

True False

There is one 5. Stored before the question is asked, it finds itself: 10 − 5 is 5, and 5 is in the set, because it has just been put there. This is the opening program's mistake again.

Asking first is what makes two equal values work properly. With [5, 5], the first 5 finds an empty set and is stored. The second 5 asks for a 5, and finds the first. Two different positions, so it is a real pair. The set holds only what came earlier, and a pair is one item together with an earlier one. That sentence is the whole reason the method is correct.

Seen it before

The same set answers a different question with no arithmetic at all: has this value appeared already?

def has_repeat(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

print(has_repeat([4, 9, 2, 9, 4]), has_repeat([4, 9, 2]))

True False

Here the partner of a value is the value itself. The loop stops at the first value that finds itself among the earlier ones, which is the second 9: the first repeat to happen, reading left to right.

"First" is a word to be careful with. In [4, 9, 2, 9, 4] the first repeat to happen is the 9 at position 3. But the value that repeats and appeared earliest is 4. Those are different questions with different answers, and a problem will always mean one of them.

Groups

A set records that a value was seen. A dictionary can record more: where it was seen, how often, or which items belong with it. To put items into groups, use a dictionary whose values are lists. The key says which group, and the list holds its members.

words = ["apple", "bear", "avocado", "cat", "bison"]
groups = {}
for word in words:
    letter = word[0]
    if letter not in groups:
        groups[letter] = []
    groups[letter].append(word)
print(groups)

{'a': ['apple', 'avocado'], 'b': ['bear', 'bison'], 'c': ['cat']}

Each word is looked at once. The if gives a key an empty list the first time it is met, and the append after it runs every time. A group is found by its key in the same way a set finds a value, so on average it takes no longer with ten thousand groups than with ten.

The groups come out in the order their keys were first met, and the words inside each in the order they came. A dictionary keeps the order in which keys were added, so nothing has to be sorted to get that.

Choosing the key

In all of this the loop is the same: one pass, one lookup, one store. What changes from problem to problem is the key: what is put into the set or the dictionary, and what is asked for. Choosing it is the design.

The question to ask is: what must two items have in common to belong together? Whatever it is, compute it from one item alone, and use that as the key.

def group_by(words, key):
    groups = {}
    for word in words:
        k = key(word)
        if k not in groups:
            groups[k] = []
        groups[k].append(word)
    return groups

def lower(word):
    return word.lower()

words = ["Tea", "ate", "tea", "Eat", "TEA"]
print(group_by(words, len))
print(group_by(words, lower))

{3: ['Tea', 'ate', 'tea', 'Eat', 'TEA']}
{'tea': ['Tea', 'tea', 'TEA'], 'ate': ['ate'], 'eat': ['Eat']}

The same five words, two keys, two different groupings. By length, all five belong together. By their lower-case form, the three spellings of tea do.

A key has to be something a set or dictionary can hold: a number, a string, or a tuple of those. A list cannot be a key, because it can change. When the thing two items share has several parts, a first name and a year, say, make a tuple of the parts.

A good key is the same for every item that belongs together and different for every item that does not. When a grouping comes out wrong, the loop is almost never the cause. Print the key for two items that were wrongly put together, or wrongly kept apart, and the mistake is in front of you.

In the lab

You will count the comparisons two loops make, work out partners by hand, and see a value find itself. You will write a pair finder that reads its list once and says where the pair is, find the first visitor to come back, group words that are made of the same letters, and count pairs without listing them, with a chart of the work saved. Then four assignments: two times a given distance apart, a pair finder with two mistakes, people who share a birthday, and one problem that does not tell you a lookup is the way in.