Lecture Notes
Introduction to Programming and Algorithm Design (COP-1000)

Dictionaries

This chapter introduces dictionaries a compound type whose elements are indexed not by an integer (like strings, lists, and tuples), but by almost any type. You can think of a Python dictionary as you would a real one: a sequence of pairs. In a real dictionary, the pairs consist of a word and its definition. In Python, the pairs are made up of a key (the index) and its associated value. The only difference between a Python dictionary and a real one is that a Python dictionary is not kept in any order it is not a sequence type like a string or list.


Dictionary operations

  • To create a dictionary, start with an empty one, designated by a set of empty braces; then you can add key-value pairs to it:

>>> d = {}         # create an empty dictionary, d
>>> type(d)
<type 'dict'>
>>> d['a'] = 'able'    # add a key-value pair
>>> d['b'] = 'bravo'   # and another
>>> print d
{'a': 'able', 'b': 'bravo'}

  • Another way to create a dictionary is to use the built-in funtion dict:
     
    >>> d2 = dict()
    >>> print d2
    {}
     
  • You can also create a dictionary using a list of key-value pairs with this syntax:

>>> m = {'gibson':'mel', 'thornton':'billy bob'}
>>> print m
{'thornton': 'billy bob', 'gibson': 'mel'}

  • Add as many key-value pairs as you want, in any order:

>>> d['e'] = 'echo'
>>> d['d'] = 'dog'
>>> print d
{'a': 'able', 'b': 'bravo', 'e': 'echo', 'd': 'dog'}

  • You can access any pair by specifying the key as the index (but you can't slice a dictionary, since there is no order to the indexes):

>>> print d['b']
bravo
>>> print d['b'] + d['d']
bravodog

  • Dictionaries are mutable, by assignment or with the del operator:

>>> d['a'] = 'alpha'     # change element
>>> del d['b']           # delete element
>>> print d
{'a': 'alpha', 'e': 'echo', 'd': 'dog'}

  • And the len() function works, too, just like for all compound types:

>>> print len(d)
3

  • The in and not in operators can be used as conditions to determine whether a particular key is in the dictionary or not:

>>> 'e' in d
True
>>> 'f' in d
False
>>> 'f' not in d
True

  • You can always get a list of methods for dictionary objects with help(dict); some of these methods are used below

Dictionary as a set of counters

  • One important use of a dictionary is as a compact set of counters; each key-value pair indicates how many times (the value) the item (the key) appears
  • A dictionary used like this is compact, because we will only create the keys for those items we actually encounter, rather than all possible items
  • See countch.py
  • One very useful method for working with dictionaries is get, which returns the value of the argument key, or a specified default value otherwise:
     
       x = d.get(key, default)

    If key exists in dictionary d, its associated value is returned; if it does not exist, default is returned
  • See countch2.py

Looping and dictionaries

  • You can traverse a dictionary with a for loop, which accesses each key
  • But since a dictionary is not a sequence, you don't know what order you will see them
  • See countch3.py
  • Dictionaries have a method keys that returns a list of the keys in the dictionary; this list can then be sorted and used to index into the dictionary to obtain the corresponding values in sorted order
  • See countch4.py

Reverse lookup

  • It is easy to retrieve a value from a dictionary given its key; this is called a forward lookup
  • But the reverse is more difficult: to find a key associated with a particular value; this is called a reverse lookup and requires a search
  • See revlookup.py
    • Uses dictionary traversal to search the dictionary
    • If no matching value found, an exception is raised, which terminates the program; we will learn how to handle exceptions later
  • Reverse lookups are very slow compared to forward lookups for large dictionaries

Dictionaries and lists

  • Since a reverse lookup is expensive (in terms of execution time), it may be necessary to invert a dictionary; that is, turn the values into keys, and their corresponding keys into values
  • Because different keys can have the same value, when we invert a dictionary, we would have just one value map to a list of keys (that had that value)
  • See invert.py

Memos

  • This section explains how you can sometimes use dictionaries to improve on the efficiency of an algorithm
  • In a previous chapter, the Fibonacci sequence was discussed, defined as:

    fib(0) = 1
    fib(1) = 1
    fib(n) = fib(n - 1) + fib(n - 2)

  • The example program fibonacci2.py generates the Fibonacci sequence using recursion; for small Fibonacci numbers, this algorithm was fine, but starting about fibonacci(30), the time required to calculate the number increases very quickly, because the algorithm requires, for each new number, the recalculation of every preceding number in the sequence
  • If we could store each Fibonacci number in a dictionary as it is generated, in a key-value pair, then we could simply extract the Fibonacci numbers needed to generate a new one
  • A previously computed value that is stored for later use is called a memo
  • The dictionary (of memos) can be started like this:

fibNumbers = {0:1, 1:1}

  • See example program fibonacci3.py that uses a global dictionary to hold all the Fibonacci numbers found so far

Global variables

  • The previous example used a global variable one declared outside of any function
  • Global variables retain their value through the duration of program execution, and are accessible by any function that include this syntax at the beginning of the function:
     
       global variable_name
     
  • Use of global variables can simplify calling functions, because such variables do not have to be included as arguments in the function call
  • However, use of global variables greatly reduces the reusability of functions that depend on them
  • Rule of thumb: do not use global variables unless there is a specific, necessary reason why you should do so

Long integers

  • The built-in type int can hold an integer in the range -2,147,483,648 to +2,147,483,647; if an integer result is outside of this range, modern versions of Python automatically assign the result to be of type long, which has an essentially unlimited range (but less efficient than int in execution, because long types are manipulated primarily with software, not hardware circuitry)
  • See example program fibonacci4.py; note where results change from int to long
 Updated: 12.13.2010