Skip to content
wannacode

dict and set

Problem

Who is this user?

The users of the site are in a list. At every login you look up the email by the username:

def find_email(users, username):
    for u in users:
        if u.username == username:
            return u.email
    return None

With three users this is instant. With 2,000,000, every login compares up to 2,000,000 names, and there are thousands of logins a minute. You do not read a phone book from the first page. You go straight to the letter.

The idea

Dictionary: key → value

You want to ask "what is the email of georgiev?" and get the answer right away. The collection for this is called a dictionary (map). It holds pairs: a key and a value. In Python the dictionary is built in, and it is called dict:

emails = {}
emails["ivanov"] = "ivanov@example.com"
emails["mpetrova"] = "mpetrova@example.com"
emails["georgiev"] = "georgiev@example.com"


print(emails["georgiev"])
print(emails.get("nobody"))
print("Users:", len(emails))
Output
georgiev@example.com
None
Users: 3
  • {} is an empty dictionary. emails[key] = value puts in a pair, and emails[key] returns the value.
  • get(key) also returns the value, and for a key that is not there it gives None.
  • len(emails) is the number of pairs. You do not need an import.
  • You do not write types: one dictionary can have any keys and values. If you want to say what they are, there is a type hint: emails: dict[str, str] = {}.

emails[key] for a key that is not there does not give None. It stops the program. You can also write a dictionary all at once, with key: value pairs:

emails = {"ivanov": "ivanov@example.com", "mpetrova": "mpetrova@example.com"}
print(emails["ivanov"])
try:
    print(emails["nobody"])
except KeyError as e:
    print(f"KeyError: {e}")
Output
ivanov@example.com
KeyError: 'nobody'

emails[key] does not loop over all the pairs. It finds the place of the key almost at once, no matter how many there are. How it does that is the next lesson.

The idea

The warehouse: changes and checks

The stock in a warehouse: item → count.

stock = {}
stock["laptop"] = 4
stock["mouse"] = 25
stock["laptop"] = 3


print(stock["laptop"])
print("monitor" in stock)
print(stock.get("monitor", 0))
del stock["mouse"]
print(len(stock))
Output
3
False
0
1
  • Keys are unique. The second stock["laptop"] = 3 does not add a new row. It replaces 4 with 3.
  • key in stock asks whether the key is in the dictionary.
  • get(key, 0) returns the value, or 0 if the key is not there. This protects you from KeyError.
  • del stock[key] removes the pair.
More precisely, if you are curious
  • Values can repeat: the laptop and the mouse can both be 3. Keys cannot.
  • You can also ask 3 in stock.values(). But that loops over all the values, because a dictionary is fast only by key.

Try it

How many are on the menu?

What will the program print?

menu = {}
menu["coffee"] = 2
menu["tea"] = 2
menu["coffee"] = 3
print(len(menu), menu["coffee"])
Answer

The idea

Looping and order

The delivery price by city. items() gives the key and value pairs, and for city, price in splits each one into two names:

delivery = {}
delivery["Sofia"] = 4.5
delivery["Plovdiv"] = 5.2
delivery["Varna"] = 6.0
delivery["Burgas"] = 6.0
delivery["Ruse"] = 5.8


for city, price in delivery.items():
    print(f"{city}: €{price:.2f}")
Output
Sofia: €4.50
Plovdiv: €5.20
Varna: €6.00
Burgas: €6.00
Ruse: €5.80

The cities come out in the order they were added. dict keeps the order of adding, and since Python 3.7 this is promised. :.2f prints the price with two digits after the decimal point. With the same assignments and print(delivery):

delivery = {}
delivery["Sofia"] = 4.5
delivery["Plovdiv"] = 5.2
delivery["Varna"] = 6.0
delivery["Burgas"] = 6.0
delivery["Ruse"] = 5.8
print(delivery)
Output
{'Sofia': 4.5, 'Plovdiv': 5.2, 'Varna': 6.0, 'Burgas': 6.0, 'Ruse': 5.8}

When you need alphabetical order, sorted(delivery) gives a sorted list of the keys. The dictionary does not change:

delivery = {}
delivery["Sofia"] = 4.5
delivery["Plovdiv"] = 5.2
delivery["Varna"] = 6.0
delivery["Burgas"] = 6.0
delivery["Ruse"] = 5.8


for city in sorted(delivery):
    print(f"{city}: €{delivery[city]:.2f}")
Output
Burgas: €6.00
Plovdiv: €5.20
Ruse: €5.80
Sofia: €4.50
Varna: €6.00
More precisely, if you are curious
  • If you need only the keys, loop over delivery. If you need only the values, loop over values():
for city in delivery:
    print(city, end=" ")
print()


print(f"Average: €{sum(delivery.values()) / len(delivery):.2f}")
Output
Sofia Plovdiv Varna Burgas Ruse
Average: €5.50
  • sum(...) adds up the numbers, and len(delivery) is the number of pairs.
  • The dictionary keeps the order of adding, but the set from the end of the lesson does not.

The idea

Counting

How many times was each item ordered? The key is the item, and the value is the count. At each order you take the old count (or 0) and add 1:

orders = "coffee tea coffee cocoa coffee tea"
counts = {}
for item in orders.split(" "):
    counts[item] = counts.get(item, 0) + 1
print(counts)
Output
{'coffee': 3, 'tea': 2, 'cocoa': 1}

This is the most common use of a dictionary: counting words, votes, errors by type, sales by city. The items come out in the order they were first seen.

orders = "coffee tea coffee cocoa coffee tea"
counts = {}
for item in orders.split(" "):
    counts[item] = counts.get(item, 0) + 1
print(counts)
Step by step, in words
  1. 6 orders and an empty dictionary.
  2. "coffee" is not there: get(item, 0) gives 0, and the assignment adds the key with 1.
  3. "tea" is not there: get(item, 0) gives 0, and the assignment adds the key with 1. The dictionary keeps the order of adding: the new key is last.
  4. "coffee" is already there: get gives 1, and the assignment replaces the value with 2.
  5. "cocoa" is not there: get(item, 0) gives 0, and the assignment adds the key with 1. The dictionary keeps the order of adding: the new key is last.
  6. "coffee" is already there: get gives 2, and the assignment replaces the value with 3.
  7. "tea" is already there: get gives 1, and the assignment replaces the value with 2.
  8. Each item is a key once, and the value is how many times it was ordered.
More precisely, if you are curious
  • split(" ") from the lesson on text splits the line into words.
  • Counting is so common that collections has a ready-made dictionary for it, Counter. For a key that is not there, it gives 0, not KeyError: 
from collections import Counter


orders = "coffee tea coffee cocoa coffee tea"
counts = Counter(orders.split(" "))
print(counts)
print(counts["coffee"], counts["juice"])
Output
Counter({'coffee': 3, 'tea': 2, 'cocoa': 1})
3 0

Try it

Find the bug

The program should count the orders. Instead, it stops at the very first one:
Error
KeyError: 'coffee'

Which line has the bug?

Pick the line with the bug.

The idea

set: each one once

How many different people logged in to the site today? If someone logs in five times, they should be counted once. A collection that holds each value only once is called a set:

visits = ["ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com"]
visitors = set()
for email in visits:
    visitors.add(email)
print("Visits:", len(visits))
print("Unique visitors:", len(visitors))
print("vera@example.com" in visitors)
Output
Visits: 5
Unique visitors: 3
True
  • set() is an empty set. {} is not: that is an empty dictionary.
  • add on a value that is already in it does nothing. In both cases it returns None, so it does not tell you whether it added anything:
seen = set()
print(seen.add("F-101"))
Output
None
  • value in visitors is as fast as in on a dictionary. Inside, a set is like a dictionary in which you keep only the keys.
  • There are no indexes. A set answers only the question "is it in here?".
More precisely, if you are curious
  • A set keeps no order. With text, the order changes even between two runs of the same program, because Python computes the hash of text differently on every run. That is why it is printed with sorted(). You can also write a set all at once, in {} with values:
tags = {"java", "sql", "git", "java"}
print(len(tags))
print(sorted(tags))


backend = {"java", "sql", "docker"}
print(sorted(tags & backend))
print(sorted(tags | backend))
Output
3
['git', 'java', 'sql']
['java', 'sql']
['docker', 'git', 'java', 'sql']
  • & keeps only the elements two sets have in common, and | joins them. You will need them in the exercise.

Try it

A duplicate invoice

The accountant wants to see the invoice numbers that were entered twice. What asks whether the number is already in the set?
invoices = ["F-101", "F-102", "F-101", "F-103"]
seen = set()
for number in invoices:
    if number  seen:
        print("Duplicate invoice:", number)
    seen.add(number)

Exercise

Dictionaries at work

Solve the tasks in your editor.

1. A user table. A UserTable class with the methods add(username, email), get(username) and size(). Inside, it is a dictionary. Add ivanov, mpetrova and georgiev with emails in the form ivanov@example.com, and look up mpetrova and nobody. In the next lesson you will also build your own hash table, without dict.

Output
mpetrova: mpetrova@example.com
nobody: no such user
Users: 3

2. Word frequency. Read a line of text, make it lowercase and count each word. Print the words in alphabetical order.

Input
Coffee with milk and coffee without sugar and coffee
Output
and: 2
coffee: 3
milk: 1
sugar: 1
with: 1
without: 1

3. Documents by keyword. A DocumentIndex class with the methods add_document(doc_id, *keywords) and search(keyword), which returns a list of the numbers of the documents with that word. Inside, it is a dictionary of lists: for each word, a list of documents. Add document 1 with "OOP" and "Java", document 2 with "SQL" and "databases", and document 3 with "Java" and "collections". Search for "Java", "SQL" and "Python".

Output
Java: [1, 3]
SQL: [2]
Python: []

4. A contact network. A Contact class with a name and an email, and a ContactNetwork class with the methods add_contact(name, email), add_connection(a, b) (the connection goes both ways), friends_of(name), common(a, b) (mutual friends) and email_of(name). Keep the contacts in a dictionary name → Contact, and the connections in a dictionary name → set of names. friends_of and common return a sorted list. Connect Ivan with Maria and Ivan with Peter.

Output
Ivan: ['Maria', 'Peter']
Maria: ['Ivan']
Mutual friends of Maria and Peter: ['Ivan']
Peter's email: peter@example.com

More tasks

  • A unique ID. A function generate_user_id(email) gives each new email a number, U001, U002 and so on, and for an email it has already seen it returns the same number. Capital and lowercase letters in the email are treated the same. There is a version with a hash function in the next lesson.
  • A book catalog. The key is the ISBN, for example 978-954-28-0001-2, and the value is the title. Add books, look one up and print all of them, sorted by ISBN.
  • A trip planner. For each destination, keep a list of activities: "Paris" → "the Eiffel Tower", "the Louvre". Print the plan in the order the destinations were added. Do you need anything more than a plain dictionary?
  • An online dictionary. Word → definition. Read words until "end" comes. For an unknown word, print "No such word."
  • Grades by subject. Read lines like "Math 6", "Physics 5", "Math 4", and print the average grade for each subject, sorted by name.

Test

Check yourself

1. When is a dictionary (dict) a better choice than a list?
2. The dictionary menu already has the key "coffee" with the value 2. What does menu["coffee"] = 3 do?
3. The key "tea" is not in menu. What do menu["tea"] and menu.get("tea") do?
4. You print a dictionary. In what order do the keys come out?
5. What does add on a set return if the value is already in it?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·