Counting with a dict

Picture an evening at the fruit stall. The seller wants to know how much of each fruit they sold today. They have the list of sales and a clean board.

For each sale, they look for the row with the fruit's name on the board and add one to its count. If there is no such row yet, they first write the name and count from zero.

In Python this is a job for a dict: the key is a word, the value a count. When a word comes up for the first time, it is not in the dict yet. The get method with the second argument 0 covers this case:

words = ["red", "blue", "red", "green", "red"]
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)  # {'red': 3, 'blue': 1, 'green': 1}

How the counting line works

All the work happens in one line of the loop. The line counts[w] = counts.get(w, 0) + 1 does three things in order:

1. counts.get(w, 0) reads the word's old count, and gives 0 for a new word.
2. + 1 adds one to it.
3. counts[w] = … writes the result back under the same key.

For a new word the key ends up holding 1, and for a known word a count one greater than before. The key does not move: new words go to the end of the dict in the order they first come up.

Press "Next step" and watch counts: a new key appears with the count 1, and a known one grows by one.

Why not write counts[name] instead of get? Square brackets read the key, and on the first step there is no key 'pear' yet. The read would stop the program with a KeyError, while get calmly returns 0 in this case.

Counter

The collections module ships with Python and holds ready-made kinds of dict. It is loaded with the line import collections, like math. collections.Counter counts the elements of a list in one call, like a seller whose board has already been filled in:

import collections

words = ["red", "blue", "red", "green", "red"]
counts = collections.Counter(words)
print(counts["red"], counts["black"])  # 3 0
print(counts.most_common(2))  # [('red', 3), ('blue', 1)]

Let's go through it line by line:

1. collections.Counter(words) goes through the list and builds a dict of counts.
2. counts["red"] gives 3, and counts["black"] gives 0: a missing key in a Counter gives 0, not a KeyError.
3. counts.most_common(2) returns a list of two "element—count" pairs from the highest count to the lowest.

A Counter is a dict: it has get, items and reading by key. With equal counts, most_common puts first the element that came up earlier, so 'blue' stands before 'green'. You can also count the characters of a string: in collections.Counter("hello"), the key 'l' holds 2.

defaultdict

Sometimes a key collects not a number but a list, for example the words that start with one letter. collections.defaultdict(list), when a missing key is read, calls list(), puts the empty list under the key and returns it. The parentheses hold the function list itself, not a call: the dict calls it whenever it needs a new empty list.

import collections

words = ["apple", "bean", "avocado", "beet", "corn"]
groups = collections.defaultdict(list)
for w in words:
    groups[w[0]].append(w)
print(groups["a"])  # ['apple', 'avocado']
print(len(groups))  # 3

Let's go through the loop:

1. w[0] is the first letter of the word: "a", "b" or "c".
2. groups[w[0]] creates an empty list for a new letter and returns the list collected so far for a known one.
3. .append(w) adds the word to that list.

defaultdict(int) creates 0 the same way, since int() returns 0. The counter from the first example is then written as counts[w] += 1. A key appears even from a plain read: groups["z"] adds a pair with an empty list. So check whether a key is there with in.

Interviewers like to ask this: "How do you count how many times each element of a list occurs?" A good answer names three ways:

• a plain dict and counts[x] = counts.get(x, 0) + 1;
• collections.Counter(items): one call, plus most_common;
• collections.defaultdict(int) and counts[x] += 1.

Common mistake

The count is increased with += in a plain dict:

words = ["red", "blue", "red"]
counts = {}
for w in words:
    counts[w] += 1  # ✗

KeyError: 'red'

The statement counts[w] += 1 first reads counts[w], and the first time a word comes up, the key is not there yet. It is like adding one to a row that is not on the board. Use get with 0, a Counter or a defaultdict(int).

Key points

• counts[k] = counts.get(k, 0) + 1 reads the old count or 0 and writes it back one greater.
• counts[k] += 1 in a plain dict raises a KeyError on a new key.
• A Counter counts elements in one call and gives 0 for a missing key.
• defaultdict(list) and defaultdict(int) create the value for a new key themselves.