Home Updates Messages SandBox

Ask for Forgiveness

There is an interesting technique widely used in Python that seems to be counter-intuitive for many programmers who came from different programming languages. The technique is often described as "It's faster to try and ask for forgiveness, than ask for permission every time".


I think it will be best to explain it using the following example:

def value_or_none(dictionary, key):
    """
    Return value associated with given key
    or None if the key is not associated with
    any value.
    """

    if key in dictionary:
        return dictionary[key]
    else:
        return None

This kind of situation is very common. So, let us see what this code actually does. The dictionaries in Python are implemented as hash tables, so the computation of the key in dictionary operation starts with computing of the hash value of our key. Once the hash value is computed, the table is consulted. If it contains something at the position specified by our hash, it is compared with the key (to check for collisions). If there was a collision, a new hash value is computed, taking the collision into account – and so on until the key is actually found (or not found) in the table. At this moment the operation is evaluated to either true or false. If it's true, then the dictionary[key] must be evaluated. The whole operation is repeated, only now we also get the value associated with the key, not just the existence of the key in our table. Once that's done, the function finishes. This is pretty elaborate, because I described it with detail. You can easily see that most of the operations are needlessly repeated two times – precisely because we are "looking before we jump", performing an operation just to see whether it's ok to perform the very same operation. We can as well do it differently:

def value_or_none(dictionary, key):
    """
    Return value associated with given key
    or None if the key is not associated with
    any value.
    """

    try:
        return dictionary[key]:
    except KeyError:
        return None

The first thing I hear from Java programmers is: "This is wrong! You can't do that! It's against The Rules. You can't actually use exceptions in your code! They are supposed to be a nightmare you should avoid, not a useful feature of the language!" Well, figures. Note how in this case the hash value of our key and the collision resolution is always performed exactly once. Setting up the try-except block takes the interpreter a little extra time, but it's usually faster than the extra lookup (it may be slower if most of the keys you check are not in your dictionary – then the first solution is better), often you can improve the speed of your program by putting a whole loop inside such block. This is an example of "just try and say sorry if you fail" approach. Of course, this whole example is a little useless anyways, because Python already has the perfect solution:

    dictionary.get(key, None)

Another common clumsiness are needlessly elaborate loops. For example:

keys = dictionary.keys()
for i in range(len(keys)):
    print keys[i], dictionary[keys[i]]

What happens here? The keys() method of a dict returns a list of all its keys. Then the for loop iterates over that list, the [] operator does a lookup of the key and returns values that are printed on the screen. Simple? Consider this:

for key, value in dictionary.iteritems():
    print key, value

The iteritems() method returns an iterator – an object that will walk trough all the key-value pairs of the dictionary, just like a cursor. That's it. There is no hash table lookup involved, no additional list in memory, the "iterator variable" is conveniently encapsulated in the iterator and we don't have to care about it. Ok, but what if we want to also print the iterator variable?

for i, (key, value) in enumerate(dictionary.iteritems()):
    print i, key, value

This requires a little explanation. The enumerate function is a "wrapper" that, given an iterator or list, will return another iterator that yields pairs consisting of numbers and items yield by the original iterator. In other words, it adds numbers.