Module 20

More on Dictionaries

Dictionaries allow easy access to keys and values. Python 3 is quite sophisticated, it will for instance not create a list of keys or a list of values, but instead an iterator. The difference is that all elements in a list are already created, whereas in an iterator, the element is only created if it is needed.

There is no restrictions on the values in a dictionary. For example, if we want to create an index of important words in a text, we can create a list of all pages on which a certain word appears. Thus, the word would be the key and the list would be the value in a dictionary.

To access all values in a dictionary, we can just use the .values() method and in order to access all the keys, we can use the .keys() method.

Dictionaries as Counters

A frequent application of dictionaries is that of a counter that counts all things in a sequence type such as a list. In fact, it is so frequent that the collections method provides a specialized counter object. Let us see how we can use a dictionary as a counter without using this class. We set ourselves the task of counting the number of occurrences of all elements in the list. We associate each element in the list with a count of originally 1 in a dictionary, whenever we encounter an element. If the element is already in the dictionary, then we know that we saw the element before and can increment the counter. After we have counted all elements, we walk through the dictionary remembering the element with the highest count and the count itself. Here is the code with heavy comments:

def most_frequent(lista):
                                          #Step 1: Count all elements
    counter = {}  #create an empty dictionary
    for x in lista:
           counter[x]=counter.get(x, 0)+1  #if necessary, this creates a new key
                                           #with value 1. otherwise, it adds 1 to
                                           #the counter
                                           #Step 2: Find the highest count
	highest_seen = 0                       #This variable contains the highest count
	for x in counter:                      #Look at all counts
           if counter[x]>highest_seen:     #if we see a higher count, remember it
                     best_key = x
                     highest_seen = counter[x]
	return best_key							

The same task is much easier using a Counter from collections.

from collections import Counter

def most_frequent(lista):
    ctr = Counter()
    for item in lista:
        ctr[item] += 1
    return ctr.most_common(1)[0][0]

This code is simpler first because the value of a not yet existing key is assumed to be zero and second, because of the method most_common.

Dictionaries for Memoization

Recursion is an elegant way of defining powerful functions. In recursion, we call the function itself once or more in the definition of the function. If we call it more than once, then we can create a performance nightmare, as we recalculate and recalculate the same values over and over again. The solution is memoization, where we use a dictionary in order to remember function values that we have calculated before. Memoization will change ill-behaving recursive functions in reasonably well-behaved functions. In order to make it work, we just create the dictionary of previously calculated function values as a global variable, so that different calls to the function can access them.

Recursion Limit

Python is aware that recursion can be excessive. It therefore sets a limit to how often a function can count itself. If this limit is exceeded, then an error is thrown. But sometimes we want to have a large number of times that a function calls itself. In this case, we have to set the recursion limit ourselves to a higher value by using sys.setrecursionlimit(10000).