Lesson 6, Bit 3: Dictionaries

A dictionary is like a list, but more general. In a list, the index positions have to be integers; in a dictionary, the indices can be (almost) any type.

You can think of a dictionary as a mapping between a set of indices (which are called keys) and a set of values. Each key maps to a value. The association of a key and a value is called a key-value pair or sometimes an item.

As an example, we'll build a dictionary that maps from English to Spanish words, so the keys and the values are all strings.

The function dict creates a new dictionary with no items. Because dict is the name of a built-in function, you should avoid using it as a variable name.

Code	Output
`engl_2_span = dict() print(engl_2_span)`	`{}`

The curly brackets, {}, represent an empty dictionary. To add items to the dictionary, you can use square brackets:

engl_2_span['one'] = 'uno'

This line creates an item that maps from the key 'one' to the value 'uno'. If we print the dictionary again, we see a key-value pair with a colon between the key and value:

Code	Output
`print(engl_2_span)`	`{'one': 'uno'}`

This output format is also an input format. For example, you can create a new dictionary with three items:

engl_2_span = {'one': 'uno', 'two': 'dos', 
'three': 'tres'}

But if you print engl_2_span, you might be surprised:

Code	Output
`print(engl_2_span)`	`{'one': 'uno', 'three': 'tres', 'two': 'dos'}`

The order of the key-value pairs is not the same. In fact, if you type the same example on your computer, you might get a different result. In general, the order of items in a dictionary is unpredictable.

But that's not a problem because the elements of a dictionary are never indexed with integer indices. Instead, you use the keys to look up the corresponding values:

Code	Output
`print(engl_2_span['two'])`	`dos`

The key 'two' always maps to the value 'dos' so the order of the items doesn't matter.

If the key isn't in the dictionary, you get an exception:

Code	Output
`print(engl_2_span['four'])`	`KeyError: 'four'`

The in operator works on dictionaries; it tells you whether something appears as a key in the dictionary (appearing as a value is not good enough).

Code	Result
`'one' in engl_2_span`	`True`
`'uno' in engl_2_span`	`False`

To see whether something appears as a value in a dictionary, you can use the method values, which returns the values as a list, and then use the in operator:

Code	Result
`vals = engl_2_span.values() 'uno' in vals`	`True`

The in operator uses different algorithms for lists and dictionaries.

For lists, it uses a linear search algorithm. As the list gets longer, the search time gets longer in direct proportion to the length of the list.
For dictionaries, Python uses an algorithm called a hash table that has a remarkable property—the in operator takes about the same amount of time no matter how many items there are in a dictionary. I won't explain why hash functions are so magical, but you can read more about it at http://wikipedia.org/wiki/Hash_table.

Dictionaries and Functions

The len function works on dictionaries; it returns the number of key-value pairs:

Code	Result
`len(engl_2_span)`	`3`

The min and max functions also work on dictionaries, but they look at the minimum and maximum value of the key and not the value. Given:

d = {'a':10, 'b':5}

Code	Result
`min(d)`	`'a'`
`max(d)`	`'b'`

So notice that even though the value of d['a'] is a larger number than the value of d['b'], the min and max functions returned the greatest and lowest values of the keys instead.

Looping and Dictionaries

If you use a dictionary as the sequence in a for statement, it traverses the keys of the dictionary. This loop prints each key and the corresponding value:

counts = {'parrot':1 , 'cheese':42, 
'spam':100}

      for key in counts:
      
    print(key, counts[key])

Here's what the output looks like:

spam 100
      parrot 1
    
  cheese 42

Again, the keys are in no particular order.

We can use this pattern to implement the various loop idioms that we have described earlier. For example if we wanted to find all the entries in a dictionary with a value above ten, we could write the following code:

counts = { 'parrot' : 1 , 'cheese' : 42, 'spam': 100}

     
 for key in counts:
          if counts[key] > 10 
:
          print(key, counts[key])

The for loop iterates through the keys of the dictionary, so we must use the index operator to retrieve the corresponding value for each key. Here's what the output looks like:

spam 100
      cheese 42

We see only the entries with a value above 10.

If you want to print the keys in alphabetical order, you first make a list of the keys in the dictionary using the keys method available in dictionary objects, and then sort that list and loop through the sorted list, looking up each key and printing out key-value pairs in sorted order as follows:

counts = {'parrot' : 1 , 'cheese' : 42, 'spam': 100}

   
   key_list = counts.keys()

      print(key_list)

      
key_list.sort()

      for key in key_list:
      
    print(key, counts[key])

Here's what the output looks like:

['spam', 'parrot', 'cheese']
  
    cheese 42
      parrot 1
      spam 100

First you see the list of keys in unsorted order that we get from the keys method. Then we see the key-value pairs in order from the for loop.

Dictionary as a Set of Counters

Suppose you are given a string and you want to count how many times each letter appears. There are several ways you could do it:

You could create 26 variables, one for each letter of the alphabet. Then you could traverse the string and, for each character, increment the corresponding counter, probably using a chained conditional.
You could create a list with 26 elements. Then you could convert each character to a number (using the built-in function ord), use the number as an index into the list, and increment the appropriate counter.
You could create a dictionary with characters as keys and counters as the corresponding values. The first time you see a character, you would add an item to the dictionary. After that you would increment the value of an existing item.

Each of these options performs the same computation, but each of them implements that computation in a different way.

An implementation is a way of performing a computation; some implementations are better than others. For example, an advantage of the dictionary implementation is that we don't have to know ahead of time which letters appear in the string and we only have to make room for the letters that do appear.

Here is what the code might look like:

word = 'brontosaurus'

 
     dictionary = dict()

      for letter in word:
      
    if letter not in dictionary:
      
    dictionary[letter] = 1

      else: 
      
    dictionary[letter] = dictionary[letter] + 1

      
print(dictionary)

We are effectively computing a histogram, which is a statistical term for a set of counters (or frequencies).

The for loop traverses the string. Each time through the loop, if the character letter is not in the dictionary, we create a new item with key letter and the initial value 1 (since we have seen this letter once). If letter is already in the dictionary we increment dictionary[letter].

Here's the output of the program:

{'a': 1, 'b': 1, 'o': 2, 'n': 1, 
's': 2, 'r': 2, 'u': 2, 't': 1}

The histogram indicates that the letters 'a' and 'b' appear once; 'o' appears twice, and so on.

Dictionaries have a method called get that takes a key and a default value. If the key appears in the dictionary, get returns the corresponding value; otherwise it returns the default value. For example:

Code	Result
`counts = {'parrot':1, 'cheese':42, 'spam':100} print(counts.get('spam', 0))`	`100`
`print(counts.get('tim', 0))`	`0`

We can use get to write our histogram loop more concisely. Because the get method automatically handles the case where a key is not in a dictionary, we can reduce four lines down to one and eliminate the if statement.

word = 'brontosaurus'

      
dictionary = dict()

      for letter in word:
      
    dictionary[letter] = dictionary.get(letter,0) + 
1

      print(dictionary)

The use of the get method to simplify this counting loop ends up being a very commonly used "idiom" in Python and we will use it many times. So you should take a moment and compare the loop using the if statement and in operator with the loop using the get method. They do exactly the same thing, but one is more succinct.

Using if and in:

if letter not in dictionary:
   
       dictionary[letter] = 1

      else:
      
    dictionary[letter] = dictionary[letter] + 1

Using get:

dictionary[letter] = 
dictionary.get(letter,0) + 1

Debugging Dictionaries

As you work with bigger datasets it can become unwieldy to debug by printing and checking data by hand. Here are some suggestions for debugging large datasets:

1. Scale down the input:

If possible, reduce the size of the dataset. For example if the program reads a text file, start with just the first 10 lines, or with the smallest example you can find. You can either edit the files themselves, or (better) modify the program so it reads only the first n lines.

If there is an error, you can reduce n to the smallest value that manifests the error, and then increase it gradually as you find and correct errors.

2. Check summaries and types:

Instead of printing and checking the entire dataset, consider printing summaries of the data: for example, the number of items in a dictionary or the total of a list of numbers.

A common cause of runtime errors is a value that is not the right type. For debugging this kind of error, it is often enough to print the type of a value.

3. Write self-checks:

Sometimes you can write code to check for errors automatically. For example, if you are computing the average of a list of numbers, you could check that the result is not greater than the largest element in the list or less than the smallest. This is called a "sanity check" because it detects results that are "completely illogical".

Another kind of check compares the results of two different computations to see if they are consistent. This is called a "consistency check".

4. Pretty print the output:

Formatting debugging output can make it easier to spot an error.

Again, time you spend building scaffolding can reduce the time you spend debugging.

About this Book