Dictionaries and Sets

You have a list of four hundred photographers and you need the one called "Ana Duarte". With a list, the only way to find her is to start at position zero and check every entry until you hit a match. For four hundred that is fine. For four hundred thousand, done inside a loop, it is the reason your program takes a minute instead of a second.

The problem is that a list files things by position, and you want to look things up by name. By the end of this lesson you will have the two collections that solve that — one for looking things up, one for answering "have I seen this before" — and know why both are fast in a way that scanning a list never is.

Looking things up by name

A dictionary stores pairs: a key you look things up by, and a value you get back. Curly braces, with a colon between each pair:

You get a value by putting its key in square brackets:

Compare that to the list version of the same record:

Both work. Only one is readable in six months, and only one survives someone inserting a field at the front.

Adding and changing use the same square-bracket notation:

The trailing comma after the last pair in the example above is deliberate, by the way. Python allows it, and it means adding a line later is a one-line change in the diff rather than two.

The missing key, and how to survive it

Asking for a key that is not there is an error:

That is usually what you want — a missing key is normally a bug, and you would rather know. But often the key is genuinely optional, and there are two better tools.

get never raises. With one argument it hands back None for a missing key; with two, whatever you specified.

Bad — using get with a default for something that must exist.

Good — demanding what is required, defaulting only what is optional.

The first version turns a malformed order into a successful charge of zero against an empty card token. No exception, no log line, and a payment record that looks fine. KeyError is not an inconvenience to be defaulted away — it is the system telling you the data is not what you think, at the moment it can still be cheaply fixed.

Going through a dictionary

Three views, for three different jobs:

items() is the one you will use most, and it pairs with the unpacking you met in the last lesson — each item is a tuple of key and value, taken apart into two names in the for line.

Dictionaries keep their insertion order, so what you get back comes in the order you added it. That is guaranteed in modern Python and worth knowing, because a lot of older writing on the internet says the opposite.

Counting things, the common shape

Tallying comes up constantly, and it is where get earns its keep:

Read the middle line as "whatever the count is now, or zero if this is the first time, plus one". Without get, you would need an if to handle the first occurrence separately.

The standard library has a purpose-built version:

Knowing the manual version first is worth it, because the shape — look up, default, put back — applies to far more than counting.

What can be a key

Values can be anything. Keys cannot.

A key must be immutable — unchangeable. Strings, numbers and tuples qualify; lists and dictionaries do not.

That restriction looks arbitrary until you see how a dictionary actually finds things, at which point it becomes the only possible rule.

1. 1

   Compute a number from the key

   Storing "name" turns those four characters into a number. The same key always produces the same number.

2. 2

   Use that number to pick a slot

   The value goes straight there. Looking it up later repeats the calculation and jumps to the same slot — which is why one key among four hundred thousand costs the same as one among four.

3. 3

   So the key must never change

   If it could, the number would change with it, and the next lookup would jump to a slot that holds nothing. The value would be lost inside its own dictionary.

This is also the third reason tuples exist, promised in the last lesson: (1920, 1080) can be a key and [1920, 1080] can never be.

Sets: membership and uniqueness

A set is a collection with no duplicates and no order. Curly braces, but single values rather than pairs:

Two jobs, both very common.

Removing duplicates, which is a one-liner:

Asking whether something is present, which is where the performance difference shows up:

in on a set takes about the same time no matter how large the set is, for the same reason as dictionary lookup. in on a list scans from the start. Inside a loop over four hundred thousand photos, checking a list of four hundred thousand names is billions of comparisons; checking a set is four hundred thousand.

Sets also do the operations you remember from Venn diagrams:

These replace loops you would otherwise write by hand. "Which files are on disk but not in the database" is on_disk - in_database, in one line that says what it means.

Choosing between the three

One question decides it almost every time: how will you find things again?

By where it is

A list.

Order matters and duplicates are allowed. First, last, the third one — position is a meaningful handle.

By a name or an id

A dictionary.

One value per key, found instantly whatever the size. Insertion order is kept, so looping still reads sensibly.

You will not find it at all

A set.

You only ever need to know whether you have seen it before, or you need the duplicates gone. No order, no values.

A cheat sheet to keep

Where to go next

You now have all four of Python's everyday collections, and more importantly a way to choose between them: ask how you will find things again. You also know why dictionaries and sets are fast, which is the same fact as why their keys must be immutable — two things that look unrelated and are one.

Next is Loops That Do Not Run Away, which is what makes collections worth having. Every collection in this lesson was built or read one item at a time; that lesson is the machinery for doing it, including the loops that never stop and how to avoid writing one.

Before you move on, take the counting example and run it on something real — the words in a paragraph, the file extensions in a folder. Then take two lists of names and use set operations to find what is in one and not the other. Both are five-minute exercises and both are things you will genuinely reach for within a week of writing real Python.

photographer = {
    "name": "Ana Duarte",
    "city": "Lisbon",
    "photo_count": 400,
}

DICTIONARY
  d = {"name": "Ana", "count": 400}
  d = {}                          empty
  d["name"]                       get - KeyError if absent
  d.get("name")                   get - None if absent
  d.get("name", "unknown")        get - your default
  d["city"] = "Lisbon"            add or replace
  del d["city"]                   remove
  "name" in d                     is that key there
  len(d)                          how many pairs

  for k in d:                     keys
  for v in d.values():            values
  for k, v in d.items():          both               <- the usual one

  keys must be immutable          str, int, tuple - never a list
  insertion order is kept

  d[k] = d.get(k, 0) + 1          the counting shape

SET
  s = {"a", "b"}
  s = set()                       empty - NOT {}
  s.add(x)                        add one
  s.discard(x)                    remove, no error if absent
  s.remove(x)                     remove, KeyError if absent
  x in s                          fast at any size
  list(set(items))                remove duplicates

  a & b     in both
  a | b     in either
  a - b     in a, not in b
  a ^ b     in one but not both

CHOOSING
  find by position    -> list
  find by name or id  -> dict
  only "seen it?"     -> set

THE ONE THAT MATTERS
  `in` on a set or dict is fast whatever the size
  `in` on a list scans - fine once, expensive inside a loop

print(photographer["name"])         # Ana Duarte
print(photographer["photo_count"])  # 400

photographer = ["Ana Duarte", "Lisbon", 400]
print(photographer[2])              # 400 - but 2 means what?

photographer["country"] = "Portugal"     # add a new pair
photographer["photo_count"] = 401        # change an existing one
del photographer["city"]                 # remove one

print(photographer["email"])
# KeyError: 'email'

if "email" in photographer:
    send_to(photographer["email"])

email = photographer.get("email")            # None if absent
email = photographer.get("email", "unknown") # your own default

def charge(order):
    amount = order.get("amount", 0)
    card = order.get("card_token", "")
    return take_payment(card, amount)

def charge(order):
    amount = order["amount"]              # must be there
    card = order["card_token"]            # must be there
    currency = order.get("currency", "EUR")   # genuinely optional
    return take_payment(card, amount, currency)

counts = {"ana": 400, "bruno": 128, "carla": 92}

for name in counts:                     # keys, by default
    print(name)

for count in counts.values():           # values
    print(count)

for name, count in counts.items():      # both, unpacked
    print(f"{name} has {count} photos")

tags = ["sunrise", "tram", "sunrise", "square", "sunrise"]
counts = {}

for tag in tags:
    counts[tag] = counts.get(tag, 0) + 1

print(counts)     # {'sunrise': 3, 'tram': 1, 'square': 1}

from collections import Counter
print(Counter(tags))     # Counter({'sunrise': 3, 'tram': 1, ...})

good = {"name": "Ana", 42: "the answer", (1920, 1080): "HD"}

bad = {["a", "b"]: "value"}
# TypeError: unhashable type: 'list'

tags = {"sunrise", "tram", "sunrise", "square"}
print(tags)        # {'sunrise', 'tram', 'square'}  - one sunrise
print(len(tags))   # 3

unique_tags = list(set(all_tags))

processed = set()

for photo in photos:
    if photo.name in processed:      # fast, whatever the size
        continue
    process(photo)
    processed.add(photo.name)

a = {"sunrise", "tram", "square"}
b = {"tram", "bridge"}

print(a & b)     # {'tram'}                      in both
print(a | b)     # all five                      in either
print(a - b)     # {'sunrise', 'square'}         in a, not in b
print(a ^ b)     # in one but not both

tags.add("bridge")           # add one
tags.discard("tram")         # remove, no error if absent
tags.remove("tram")          # remove, KeyError if absent