Suppose we have a list of student names and a list of corresponding grades.

names = ['John', 'Paul', 'Goerge']
scores = [95, 75, 85]

Q. Given a student's name, how do we find his/her grade?

A better way to represent key:value relationship is dictionary.

A dictionary is a mapping

A dictionary contains a collection of indices, which are called keys, and a collection of values. Each key is associated with a single value. The association of a key and a value is called a key-value pair or sometimes an item.

In mathematical language, a dictionary represents a mapping from keys to values, so you can also say that each key “maps to” a value.

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.

grades = dict()
print(grades)

{}

grades['John'] = 90
# creates an item that maps from the key 'John' to the value 90
print(grades)

{'John': 90}

grades ={'John': 90, 'Paul': 75, 'Goerge': 85}
print(grades)
# Changed in Python 3.7: Dictionary order is guaranteed to be insertion order. 

{'John': 90, 'Paul': 75, 'Goerge': 85}

print(grades['Paul'])

75

print(grades['Ringo'])

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-6-abd3b19e719c> in <module>
----> 1 print(grades['Ringo'])

KeyError: 'Ringo'
print(len(grades))

3

'Paul' in grades # only check the keys

True
'Paul' in grades

True
90 in grades.values() # check the values

True

Dictionary as a collection 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:

  1. 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.
  2. 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.
  3. 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:

def histogram(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

h = histogram('Bookkeeper')
print(h)

{'B': 1, 'o': 2, 'k': 2, 'e': 3, 'p': 1, 'r': 1}

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:

number_of_e = h.get('e', 0)
number_of_a = h.get('a', 0)
print(number_of_e)
print(number_of_a)

3
0

Exercise 01

  1. Rewrite function histogram using get. You should be able to eliminate the if statement.

  2. Use function histogram to count the frequency of each word in your favorite song.

Looping and dictionaries 

def print_hist(h):
    for c in h:
        print(c, h[c])
        
h = histogram('Massachusetts')
print_hist(h)

M 1
a 2
s 4
c 1
h 1
u 1
e 1
t 2

for key in sorted(h):
    print(key, h[key])

M 1
a 2
c 1
e 1
h 1
s 4
t 2
u 1

Reverse lookup

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?

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

The raise statement causes an exception; in this case it causes a LookupError, which is a built-in exception used to indicate that a lookup operation failed.

h = histogram('Massachusetts')
key = reverse_lookup(h, 2)
print(key)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-16-864b8db8ec51> in <module>
      1 h = histogram('Massachusetts')
----> 2 key = reverse_lookup(h, 2)
      3 print(key)

NameError: name 'reverse_lookup' is not defined
key = reverse_lookup(h, 3)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-17-a9dd9a7a13ae> in <module>
----> 1 key = reverse_lookup(h, 3)

NameError: name 'reverse_lookup' is not defined

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

raise LookupError('value does not appear in the dictionary')

---------------------------------------------------------------------------
LookupError                               Traceback (most recent call last)
<ipython-input-18-809967c2546f> in <module>
----> 1 raise LookupError('value does not appear in the dictionary')

LookupError: value does not appear in the dictionary

Dictionaries and lists

Lists can appear as values in a dictionary. For example, to invert a dictionary:

def invert_dict(d):
    inverse = dict()
    for key in d:
        val = d[key]
        if val not in inverse:
            inverse[val] = [key]
        else:
            inverse[val].append(key)
    return inverse

hist = histogram('parrot')
print(hist)

{'p': 1, 'a': 1, 'r': 2, 'o': 1, 't': 1}

inverse = invert_dict(hist)
print(inverse)

{1: ['p', 'a', 'o', 't'], 2: ['r']}

Lists can be values in a dictionary, as this example shows, but they cannot be keys. Here’s what happens if you try:

t = [1, 2, 3]
d = dict()
d[t] = 'oops'

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-22-e3ea20954cd2> in <module>
      1 t = [1, 2, 3]
      2 d = dict()
----> 3 d[t] = 'oops'

TypeError: unhashable type: 'list'

The reason is that a dictionary is implemented using a hashtable and that means that the keys have to be hashable.

A hash is a function that takes a value (of any kind) and returns an integer. Dictionaries use these integers, called hash values, to store and look up key-value pairs.

This system works fine if the keys are immutable. But if the keys are mutable, like lists, bad things happen. For example, when you create a key-value pair, Python hashes the key and stores it in the corresponding location. If you modify the key and then hash it again, it would go to a different location. In that case you might have two entries for the same key, or you might not be able to find a key. Either way, the dictionary wouldn’t work correctly.

That’s why keys have to be hashable, and why mutable types like lists aren’t. The simplest way to get around this limitation is to use tuples, which we will see in the next chapter.

Since dictionaries are mutable, they can’t be used as keys, but they can be used as values.

Memos

Recall how we impletement fibonacci using recursion. Count how many times fibonacci(0) and fibonacci(1) are called. This is an inefficient solution to the problem, and it gets worse as the argument gets bigger.

One solution is to keep track of values that have already been computed by storing them in a dictionary. A previously computed value that is stored for later use is called a memo. Here is a “memoized” version of fibonacci:

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

for i in range(10):
    print(fibonacci(i), end=", ")

0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

known is a dictionary that keeps track of the Fibonacci numbers we already know. It starts with two items: 0 maps to 0 and 1 maps to 1.

Whenever fibonacci is called, it checks known. If the result is already there, it can return immediately. Otherwise it has to compute the new value, add it to the dictionary, and return it.

Exercise 2

Play with _fibonaccicounted.py. (You can find the Python file in resources/code on GitHub.)

Global variables

In the previous example fibonacciCounted, known is created outside the function, so it belongs to the special frame called __main__. Variables in __main__ are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next.

It is common to use global variables for flags; that is, boolean variables that indicate (“flag”) whether a condition is true.

Exercise 03

Find out another global variable that is used inside functions. What is the difference between this global variable and known? Why?

A. If a global variable refers to a mutable value, you can modify the value without declaring the variable.

!!BE CAREFUL!!: Global variables can be useful, but if you have a lot of them, and you modify them frequently, they can make programs hard to debug.

Read more about local and global variables: https://docs.python.org/3/faq/programming.html#what-are-the-rules-for-local-and-global-variables-in-python

Exercise 04

  1. Write a function that reads the words in words.txt and stores them as keys in a dictionary. It doesn’t matter what the values are. Then you can use the in operator as a fast way to check whether a string is in the dictionary.

  2. Write a function named has_duplicates that takes a list as a parameter and returns True if there is any object that appears more than once in the list.

  3. (Optional) Here’s another Puzzler from Car Talk:

    This was sent in by a fellow named Dan O’Leary. He came upon a common one-syllable, five-letter word recently that has the following unique property. When you remove the first letter, the remaining letters form a homophone of the original word, that is a word that sounds exactly the same. Replace the first letter, that is, put it back and remove the second letter and the result is yet another homophone of the original word. And the question is, what’s the word?

Now I’m going to give you an example that doesn’t work. Let’s look at the five-letter word, ‘wrack.’ W-R-A-C-K, you know like to ‘wrack with pain.’ If I remove the first letter, I am left with a four-letter word, ’R-A-C-K.’ As in, ‘Holy cow, did you see the rack on that buck! It must have been a nine-pointer!’ It’s a perfect homophone. If you put the ‘w’ back, and remove the ‘r,’ instead, you’re left with the word, ‘wack,’ which is a real word, it’s just not a homophone of the other two words.

But there is, however, at least one word that Dan and we know of, which will yield two homophones if you remove either of the first two letters to make two, new four-letter words. The question is, what’s the word?

You can use the dictionary from Question 1 to check whether a string is in the word list.

To check whether two words are homophones, you can use the CMU Pronouncing Dictionary. You can download it from http://www.speech.cs.cmu.edu/cgi-bin/cmudict or use the file 'c06d' in folder cartalk_homophone and you can also use pronounce.py, which provides a function named read_dictionary that reads the pronouncing dictionary and returns a Python dictionary that maps from each word to a string that describes its primary pronunciation.

Write a program that lists all the words that solve the Puzzler.