You are here

Reverse lookup

4 September, 2015 - 14:38

Given a dictionary d and a key k, it is easy to find the corresponding value v = d[k]. This operation is called a lookup.

But what if you have v and you want to find k? You have two problems: first, there might be more than one key that maps to the value v. Depending on the application, you might be able to pick one, or you might have to make a list that contains all of them. Second, there is no simple syntax to do a reverse lookup; you have to search.

Here is a function that takes a value and returns the first key that maps to that value:

def reverse_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise ValueError

This function is yet another example of the search pattern, but it uses a feature we haven’t seen before, raise. The raise statement causes an exception; in this case it causes a ValueError, which generally indicates that there is something wrong with the value of a parameter.

If we get to the end of the loop, that means v doesn’t appear in the dictionary as a value, so we raise an exception.

Here is an example of a successful reverse lookup:

>>> h = histogram('parrot')
>>> k = reverse_lookup(h, 2)
>>> print k
r

And an unsuccessful one:

>>> k = reverse_lookup(h, 3)Traceback (most recent call last):File "<stdin>", line 1, in ?File "<stdin>", line 5, in reverse_lookupValueError

The result when you raise an exception is the same as when Python raises one: it prints a traceback and an error message.

The raise statement takes a detailed error message as an optional argument. For example:

>>> k = reverse_lookup(h, 3)
Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    File "<stdin>", line 5, in reverse_lookup
ValueError

A reverse lookup is much slower than a forward lookup; if you have to do it often, or if the dictionary gets big, the performance of your program will suffer.

Exercise 11.4.Modify reverse_lookupso that it builds and returns a list of all keys that map to v, or an empty list if there are none.