A hash table as a counter in Python

Problem

The best-selling products of the day

The shop dashboard shows the three best-selling products of the day. The log is a list of orders, one per line. The code keeps two lists, the names and the counts, and for every order it looks for the product from the start of the names:

log = log_of(1000)
names = []
counts = []
comparisons = 0
for item in log:
    i = 0
    while i < len(names):
        comparisons += 1
        if names[i] == item:
            break
        i += 1
    if i == len(names):
        names.append(item)
        counts.append(1)
    else:
        counts[i] += 1
print(f"orders: {len(log)}")
print(f"products: {len(names)}")
print(f"comparisons: {comparisons}")

orders: 1000
products: 251
comparisons: 125255

A thousand orders and 251 different products: 125,255 comparisons. The catalog grows with the shop, and so does the list every order walks through. On a big day with 100,000 orders the dashboard takes minutes to load.

Where the log comes from

The log follows a formula, so that the programs in all four languages and the comparison in the browser below build exactly the same one. The catalog has n / 4 + 1 products:

def log_of(n):
    catalog = n // 4 + 1
    return [f"SKU-{(i * 7919) % catalog}" for i in range(n)]

The idea

The map counts

In the lesson “dict and set” you counted orders with a map. Here it becomes a technique: a hash table as a counter (a frequency map). The key is what you count, the value is how many times you have seen it.

One pass over the data. For every element: find its counter (or 0) and add 1.
The lookup is in a hash table: O(1) on average, however many products there are. O(n) in total instead of O(n · m).
After that you answer the questions from the counts, not from the data: which one is most common, which one appears once, whether two things have the same counts.

The memory is O(m): one pair for every different product.

See it

The counter fills up

from collections import defaultdict

log = [
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset",
]
counts = defaultdict(int)
for item in log:
    counts[item] += 1
top = sorted(counts.items(),
             key=lambda e: e[1], reverse=True)
for item, n in top[:3]:
    print(item, n)

mouse 4
headset 3
monitor 2

counts = defaultdict(int)
for item in log:
    counts[item] += 1
top = sorted(counts.items(),
             key=lambda e: e[1], reverse=True)
for item, n in top[:3]:
    print(item, n)

Step by step, in words

An empty map: product → how many times it was sold. The log has 10 orders.
Order 1: mouse. It is not in the map yet, so it gets a count of 1.
Order 2: headset. It is not in the map yet, so it gets a count of 1.
Order 3: mouse, 1 → 2. One lookup in the hash table, without walking the other products.
Order 4: monitor. It is not in the map yet, so it gets a count of 1.
Order 5: keyboard. It is not in the map yet, so it gets a count of 1.
Order 6: mouse, 2 → 3. One lookup in the hash table, without walking the other products.
Order 7: headset, 1 → 2. One lookup in the hash table, without walking the other products.
Order 8: monitor, 1 → 2. One lookup in the hash table, without walking the other products.
Order 9: mouse, 3 → 4. One lookup in the hash table, without walking the other products.
Order 10: headset, 2 → 3. One lookup in the hash table, without walking the other products.
10 orders, 10 counter updates. Only the 4 distinct products get sorted by count, not the orders.
The top three: mouse 4, headset 3, monitor 2.

defaultdict(int) creates a counter of 0 the first time a new key is read, so counts[item] += 1 also works for a new product. The top three come from sorting the pairs by count: only the different products are sorted, not the orders.

Try it

Fill in

The line that counts:

counts = defaultdict()

defaultdict(int) calls int() for a new key, and int() is 0.

See it

The tools of your language

Python has a ready-made counter: collections.Counter. It takes the list and counts by itself, gives 0 for a missing key, and most_common(k) returns the top k by count. Equal counts stay in the order of first appearance:

from collections import Counter

log = [
    "mouse", "headset", "mouse", "monitor",
    "keyboard", "mouse", "headset", "monitor",
    "mouse", "headset",
]
counts = Counter(log)
print(counts["mouse"], counts["tablet"])
print(counts.most_common(3))

4 0
[('mouse', 4), ('headset', 3), ('monitor', 2)]

defaultdict(int) is the more general tool: the same counter, but the value can also be a sum or a list.

See it

Measure: a list of pairs against a map

The same thousand orders with the map:

log = log_of(1000)
counts = defaultdict(int)
updates = 0
for item in log:
    counts[item] += 1
    updates += 1
print(f"orders: {len(log)}")
print(f"products: {len(counts)}")
print(f"counter updates: {updates}")

orders: 1000
products: 251
counter updates: 1000

1,000 updates instead of 125,255 comparisons. Run both in the browser. n is the number of orders, and the catalog grows with it:

A list of product and count pairs O(n²)
A map as a counter O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
A list of product and count pairs	16	125,255	≈ 1,252,550,000
A map as a counter	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

counts = defaultdict(int)
for item in log:
    counts[item] += 1
top = sorted(counts.items(),
             key=lambda e: e[1], reverse=True)
for item, n in top[:3]:
    print(item, n)

More precisely, if you are curious

The top k without sorting everything. Sorting m different products is O(m log m). If there are millions of products and you need the top 10, you keep a heap with at most k pairs: every pair goes in, and when there are k + 1, the smallest goes out. That is O(m log k).

A key with several parts. You count sales by city and product: the key is the pair. In Python it is a tuple (city, item): it is immutable and has a hash.

The idea

The basket and the kit

The “home office” kit is a monitor, a keyboard, a mouse and two cables. The warehouse checks that the basket to be shipped is exactly the kit: nothing extra, nothing missing. The order does not matter, the counts do.

One counter: +1 for every product of the kit, −1 for every product in the basket. The basket matches if all counts end up at 0.

def matches(kit, basket):
    return Counter(kit) == Counter(basket)

A Counter compares with == by its counts, so the whole check is one line.

The same check finds anagrams: “listen” and “silent” have the same letters with the same counts. The counter is over letters instead of products.

Try it

Predict the check

from collections import Counter

kit = ["monitor", "keyboard", "mouse", "cable", "cable"]
basket1 = ["cable", "mouse", "monitor", "cable", "keyboard"]
basket2 = ["monitor", "keyboard", "mouse", "mouse", "cable"]
print(f"basket 1: {'complete kit' if matches(kit, basket1) else 'does not match'}")
print(f"basket 2: {'complete kit' if matches(kit, basket2) else 'does not match'}")

Answer

basket 1: does not match
basket 2: complete kit

basket 1: complete kit
basket 2: complete kit

basket 1: complete kit
basket 2: does not match

The idea

The first customer with a single order

Marketing sends a “come back” voucher to the customers who ordered only once. It wants the first one in time. The counter gives the counts, but not the order:

def first_single(customers):
    counts = Counter(customers)
    for c in customers:
        if counts[c] == 1:
            return c
    return None

from collections import Counter

customers = [
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30",
]
print(f"first customer with one order: {first_single(customers)}")

first customer with one order: C-21

Two passes: the first one counts, the second walks the log, in the order of the orders, and stops at the first one with a count of 1. O(n), with no nested loop.

More precisely, if you are curious

Why does the second pass walk the log and not the map? A dict keeps insertion order (promised since Python 3.7), so here walking counts would give the same answer. The log is still clearer: the order comes from it.

The idea

Two products for exactly €50

The customer has a voucher for exactly €50 and wants two products that use it up. The prices in the catalog are not sorted.

You walk through the prices and for each one you ask: have I already seen the price that tops this one up to 50? The map keeps the prices seen so far and their positions:

def voucher_pair(prices, voucher):
    seen = {}
    for i, price in enumerate(prices):
        j = seen.get(voucher - price)
        if j is not None:
            return j, i
        seen[price] = i
    return None

prices = [27, 14, 33, 25, 8, 36, 19]
a, b = voucher_pair(prices, 50)
print(f"products {a} and {b}: €{prices[a]} + €{prices[b]}")

products 1 and 5: €14 + €36

One pass: O(n) time and O(n) memory. With two pointers it works without a map, with O(1) memory, but the prices must be sorted. If they are not, sorting costs O(n log n) and loses the position of every product in the catalog. So: sorted data, two pointers; unsorted data, a map.

Try it

Find the bug

Someone swapped two lines. Now for a €50 voucher the program offers one product twice:

prices = [27, 14, 33, 25, 8, 36, 19]
a, b = voucher_pair(prices, 50)
print(f"products {a} and {b}: €{prices[a]} + €{prices[b]}")

products 3 and 3: €25 + €25

Pick the line with the bug.

Exercise

Who spends the most

Solve the task in your own editor.

Revenue per customer. The log has pairs of customer and amount: C-4 for €30, C-17 for €55, C-4 for €20, C-9 for €80, C-17 for €10 and C-4 for €45. Add up the amounts per customer with a map (the value is a sum, not a count) and print the two who spent the most:

C-4: €95
C-9: €80

More tasks

Anagrams. Write a check whether two words are anagrams (“listen” and “silent”) by counting the letters with a map. How many operations does it take for words of length n?
The first repeat. Find the first order whose customer has already ordered before. Do you need a counter, or is a set enough?
Periods with equal counts. From prefix sums you know how to count periods with a given sum. Count the periods of consecutive days in which the number of returned orders equals the number of delivered ones.

Test

Check yourself

1. The log has 100,000 orders and 25,000 different products. How many counter updates does the map make?25,000: one per product100,000 · 25,000100,000: one per order

2. How do you check with one map that the basket is exactly the kit?+1 for every product of the kit, −1 for every product in the basket, and every count must be 0Sort both lists and compare them, no map neededCheck that every product in the basket is in the kit

3. In voucherPair the price goes into the map after the lookup for its pair. Why not before?Because of speedIt does not matterOtherwise a €25 product finds itself for a €50 voucher

4. When are two pointers the better choice for a pair with a given sum?Always, because they are fasterWhen the prices are already sorted: no map and no extra memoryNever

5. You need the top 10 of 2,000,000 different products. What is cheapest?Look for the largest ten timesSort all 2,000,000 pairsA heap with at most 10 elements: O(m log k)

A hash table as a counter

Cookies