Dictionaries

Keys and values, dictionaries built on hash tables, and information retrieval: commands looked up by name.

A3.6Data structuresA level20 min

You have already used Python dictionaries as look-up tables, such as OPPOSITE["left"] giving "right" in lesson A3.2. At A level a dictionary is an abstract data type with its own operations, usually built on the hash table from the last lesson, and it is one of the most useful structures a programmer has. In this lesson BugBot reads a message of commands and looks each one up by name.

The dictionary ADT

A dictionary is a collection of key-value pairs. Each key is unique and is used to find its value, the way a word in a real dictionary finds its definition. Its operations:

Operation	Python
add a new key with a value	`tags[23] = "gate"`
look up the value for a key	`tags[17]`
change the value for a key	`tags[17] = "slope"`
remove a key and its value	`del tags[12]`
test whether a key is present	`17 in tags`
go through every key	`for key in tags:`

tags = {12: "dock", 17: "ramp"}        # marker id -> name
tags[23] = "gate"                      # add
tags[17] = "slope"                     # change
del tags[12]                           # remove
print(tags)
print(17 in tags, 12 in tags)          # is the key present?
print(tags.get(99, "unknown"))         # look up, with a default for a missing key
print(list(tags.keys()), list(tags.values()))

Run this in the simulator

Looking up a key that is not there, tags[99], raises a KeyError. Check with in first, or use get with a default.

The abstract data type has no order: a dictionary is for finding values by key, not by position. Python happens to keep keys in the order they were added, which is handy for printing, but an exam answer should not rely on it.

How it works: a hash table underneath

Python builds its dictionaries as hash tables. The key is hashed to find the slot, so adding, looking up and removing all take about the same time however many pairs there are: O(1) on average. A list of pairs would need a linear search for every look-up.

That is why a key must be immutable. If a key could change after it was stored, its hash would change, and it would never be found in its slot again. Numbers, strings and tuples can be keys; lists cannot.

try:
    grid = {[0, 0]: 42}
except TypeError as e:
    print("TypeError:", e)

grid = {(0, 0): 42, (0, 10): 38}       # a tuple is immutable, so it can be a key
print(grid[(0, 10)])

Run this in the simulator

Information retrieval

A classic use of a dictionary is information retrieval: finding things in text. Counting how often each word appears turns a document into a dictionary from word to frequency, which is the first step of a search engine or a spam filter. Here the text is BugBot's log:

log = """wall ahead turning left
clear ahead driving
wall ahead turning right
marker seen driving
clear ahead driving"""

counts = {}
for word in log.split():
    if word in counts:
        counts[word] = counts[word] + 1
    else:
        counts[word] = 1

print(counts)
print("ahead appears", counts["ahead"], "times")
print("reversing" in counts)
top = sorted(counts, key=counts.get, reverse=True)[:3]
print("most common:", top)

Run this in the simulator

Two logs can be compared by their word counts: logs that use the same words in similar amounts are probably describing similar runs. Each dictionary is really a list of numbers, one per word, which is a vector, the subject of the next lesson.

A sparse map

The robot's world is mostly empty. Instead of a 2D array with a cell for every square centimetre, a dictionary can store only the places that have been measured, with an (x, y) tuple as the key:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

seen = {}                              # (x, y) -> distance ahead, only where measured
for step in range(4):
    x, y = position()
    seen[(round(x), round(y))] = distance()
    right(50, distance=10)

for place in seen:
    print("at", place, "the wall was", seen[place], "cm ahead")
print("measured at (10, 0)?", (10, 0) in seen)

Run this in the simulator

This is a sparse structure: memory is used only for the data that exists.

Look-up tables

A dictionary can replace a long if/elif chain. Instead of testing a value against every case, the program looks the answer up in one step, and adding a case means adding one pair, not another branch. Here note names are looked up to find their pitch:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

PITCH = {"C": 262, "D": 294, "E": 330, "F": 349, "G": 392}   # note name -> frequency in Hz

tune = "E D C D E E E"
for note in tune.split():
    if note in PITCH:
        tone(PITCH[note], 0.25)
    else:
        print("no pitch for", note)
print("played", len(tune.split()), "notes")

Run this in the simulator

Other uses: a compiler's symbol table from each variable name to its type and address (module A10), a cache from a function's arguments to its answer so it is only worked out once, and settings files in JSON, which is a text form of a dictionary.

In the exam

Questions ask you to explain what a dictionary is, to give a suitable use and say why a dictionary suits it, to show a dictionary after some operations, and to explain why look-ups are fast. Name the key and the value, and remember that keys are unique.

OCR A level 1.4.2

OCR's data structures list does not name dictionaries separately, but a dictionary is a hash table in use, and questions on hash tables can be set in the context of looking values up by key.

AQA A level 4.2.1.4 4.2.7.1

AQA asks you to be familiar with the concept of a dictionary and with simple applications, for example information retrieval, and to have experience of using a dictionary data structure in a programming language. It also lists dictionaries among the abstract data types you should be able to use in simple contexts.

Eduqas A level 1.1

Eduqas asks you to describe and use data structures and to choose a suitable one for a problem. A dictionary is a hash table in use, so the hash table ideas behind it are the ones to know well.

Task: commands by name

MESSAGE is a string of words in pairs: a command, then a whole number. The known commands are:

forward, backward, left and right: the number is a distance in cm. Carry them out with slide(dx, dy, cm), where (dx, dy) is the direction: (0, 1) forward, (0, -1) backward, (-1, 0) left, (1, 0) right.
tone: the number is a pitch in Hz. Play it with tone(hz, 0.2).

Make a dictionary DIRECTIONS from each of the four direction words to its (dx, dy) tuple. Do not compare the word with each direction name: one look-up must find the direction.
Go through the words two at a time. Carry out a known command. For any other word print unknown command <word> and skip the pair.
Keep a second dictionary counting how many times each known command was carried out.
At the end, print one line per command in the order each was first carried out, as <command>: <count>, for example forward: 2.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

MESSAGE = "forward 20 right 15 tone 880 forward 10 left 15 tone 660 spin 90 backward 30"

def slide(dx, dy, cm):
    """Drive cm in the direction (dx, dy): (1, 0) is right, (-1, 0) left, (0, 1) forward, (0, -1) backward."""
    if dx > 0:
        right(50, distance=cm * dx)
    if dx < 0:
        left(50, distance=-cm * dx)
    if dy > 0:
        forward(50, distance=cm * dy)
    if dy < 0:
        backward(50, distance=-cm * dy)

words = MESSAGE.split()

Challenges

Add diagonal commands such as upright, with direction (0.7, 0.7). What did you have to change, and what did you not?
Change the count so it uses get with a default of 0 instead of an if.
Two robots' logs each become a word-count dictionary. Write a function that returns the words that appear in both.