Dictionaries

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

A3.6Data structuresA level20 min

Covers OCR H446 1.4.2 Data Structures · AQA 7517 4.2.1.4 Abstract data types/data structures · AQA 7517 4.2.7.1 Dictionaries · Eduqas A500QS 1.1 Data structures

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Hash tables explained

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:

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.

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).

1. 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.
2. 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.
3. Keep a second dictionary counting how many times each known command was carried out.
4. 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

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