Multisets and counted dicts in Python

Why this matters

Many programs hold a pile of items where the same item can appear more than once. A warehouse has three copies of one part and two of another. A print queue has four jobs for the same file. A game deck has several cards with the same number. In each case the program needs to answer simple questions: how many copies are there, how do I take one away, and which value is the smallest or largest?

A plain set cannot help here, because a set keeps only one copy of each value. A plain list keeps duplicates, but finding the smallest value or taking out one copy means looking through the list, which gets slower as the list grows.

The tool for this job is called a multiset. A multiset is a collection that keeps duplicates and records how many copies of each value it holds. C++ has a built-in version called std::multiset. Python's standard library has collections.Counter, which is a dict from each value to its count, and it does most of the counting work for you. Python has no sorted dict in its standard library, so this lesson keeps the values in sorted order with a list, and uses bisect for the questions about order.

The idea: store each value once, with a count

Think of a shelf with three red balls and one blue ball. You could write down the list red, red, red, blue, which takes four lines. Or you could write red = 3, blue = 1, which takes two lines. The second way keeps the same information with less writing when values repeat often.

A counted dict does the same thing. The key is the value, and the value stored under it is the count.

values added: 5, 3, 5, 9, 3, 5
counted dict: 3 -> 2, 5 -> 3, 9 -> 1

The dict has three keys, because there are three different values. The total number of items is 6, which is the sum of the three counts. len of the dict is the number of distinct values, not the total.

Example 1: adding values and reading the total

The code below adds values to the dict and reads back some facts from it. bag is the name for the multiset in this lesson. It is a plain dict, so you can see exactly what happens. Counter does the same work with less code, and the next section shows it.

bag = {3: 2, 5: 3, 9: 1}
size = 6 len = 3
smallest = 3 largest = 9

add works the same way as the counting step in the Top K lesson. If x is not in the dict, bag.get(x, 0) returns 0, and the count becomes 1. If x is already there, the count goes up by 1.

size adds up all the counts. It does not use len(bag), because len counts keys, not copies. For the bag above, len(bag) returns 3, and the bag's size is 6.

The bag is printed in sorted order only through sorted_view. A dict keeps insertion order, so the plain print would show {5: 3, 3: 2, 9: 1}. Sorting is a separate step, and the program asks for it when it needs it.

The same bag with Counter

collections.Counter accepts any iterable (anything you can loop over, such as a list) and counts it. It is a dict subclass, so the lookups and loops are the same. It also has a total() method (Python 3.10 and later), which adds the counts, and an elements() method, which lists each value as many times as its count.

Counter({5: 3, 3: 2, 9: 1})
size = 6
expanded = [3, 3, 5, 5, 5, 9]

Counter prints its counts in order of the most common value first, so its printed form is not sorted by value. Use sorted(bag.elements()) when you need the copies in order.

Example 2: removing one copy at a time

Removing one copy is the main job of a multiset. If the count is more than 1, the count goes down by 1. If the count is exactly 1, the key must be removed from the dict, so that no key with count 0 is left behind. If the value is not in the bag at all, the function should say so.

remove 5 -> True {3: 2, 5: 2, 9: 1}
remove 9 -> True {3: 2, 5: 2}
remove 9 -> False {3: 2, 5: 2}
size now = 4

The check x not in bag comes first. Reading bag[x] for a missing key would raise KeyError, so the function looks first and returns False for a missing value. The method returns True or False, so the caller can react when the value was not there.

After the second removal of 9, the key 9 is gone. The third call finds no key, returns False, and leaves the bag unchanged.

The cost is small. The lookup, the store and the delete each look for one key, which takes about the same time whatever the number of keys. The sort used by the order questions is a separate cost, covered in the next example.

With Counter, the same function is shorter, but it leaves a zero count behind. The mistakes section shows why that matters.

Example 3: asking questions about sorted copies

The keys must be in order to answer questions about the smallest, the nearest and the ranges. The first question is the k-th smallest copy. Copies are counted with their repeats, so with the bag 3, 3, 5, 5, 5, 9, the 3rd smallest is 5: the first two copies are the two 3s, and the third copy is the first 5.

5
9

The function walks the keys from the smallest up. Each key adds its count to seen. When seen reaches k, the current key is the answer. This walk looks at keys, not at copies, so it is fast when there are few distinct values. The sorted(bag) call costs about m times log m steps for m distinct values. A structure that keeps its keys sorted as it changes would avoid that cost on every question, and the section on the sorted list below shows how.

The second question is how many copies lie in a range, such as all copies from 4 to 7. Python has no subMap method, so the code keeps the keys that fall in the range and adds up their counts. The bisect module finds the nearest keys in a sorted list of keys, which answers the questions ceilingKey and floorKey answer in Java.

copies in [4, 7] = 5
ceiling(5) = 6 floor(5) = 4

bisect_left(keys, 5) returns the position where 5 would go before any equal key, so keys[...] at that position is the smallest key that is 5 or more. bisect_right(keys, 5) - 1 is the position of the largest key that is 5 or less. Lesson 2 explained both functions.

The range count adds the counts for the keys 4 and 6, which is 2 plus 3, or 5. The bag holds two 4s and three 6s, so the answer is 5.

Example 4: taking a list of requests from stock

The next example puts the pieces together. A store has some items in stock, and a list of requests comes in. Each request takes one item of that kind. A request for an item that is out of stock fails, and the stock stays the same.

take 3: ok
take 1: ok
take 7: missing
take 3: ok
left = {1: 1, 2: 1, 3: 1}

Each take removes exactly one copy. The request for 7 fails because 7 was never in the stock. The final dict shows what is left: one 1, one 2 and one 3.

Two harder examples

The first four examples used one bag at a time. The next two combine the pieces in a new way.

Example 5: subtracting one list from another

Take two lists. The first is the stock, and the second is the list of items to remove. For each value in the second list, remove one copy from the stock if one is there. If the value is not there, skip it. What is left is the answer. This is called a multiset difference.

Take the stock 1, 1, 2, 3, 3, 3 and the removal list 1, 3, 4. The stock loses one 1 and one 3. The 4 is not in the stock, so it is skipped. The answer is 1, 2, 3, 3.

Counter does this directly. Subtracting one Counter from another keeps only the positive counts, so the 4 drops out on its own.

subtract = [1, 2, 3, 3]

The answer comes out in sorted order, because sorted is applied to the expanded copies. A Counter subtraction drops every count that is zero or below, so the key for 4 is never created. The mistakes section shows what happens with a plain dict, where the zero count stays.

Example 6: the median of a bag

The median is the middle value when the values are sorted. For an odd number of values, it is the middle one. For an even number, it is the average of the two middle ones. A bag can answer this with kth_smallest, without building a sorted list of every copy.

For a bag with n copies, the middle position is n // 2 + 1 when n is odd. When n is even, the two middle positions are n // 2 and n // 2 + 1. The // operator is integer division, which drops the fraction. For 5 values, 5 // 2 is 2, and the middle position is 2 + 1, which is 3.

median of {3: 2, 5: 3, 9: 1} = 5.0
median of {3: 1, 5: 1, 9: 1} = 5
median of {3: 1, 9: 1} = 6.0

The first bag has six copies, 3, 3, 5, 5, 5, 9. It is an even count, so the median is the average of the third and fourth copies. Both are 5, so the average is 5.0. The second bag has three copies, 3, 5, 9, and the middle is 5. The third bag has two copies, 3, 9, so the median is the average of 3 and 9, which is 6.0.

Python's / always gives a float, so the even case prints 5.0 or 6.0, and the odd case prints an integer, because it returns a value taken from the bag. If the caller needs a float every time, wrap the result in float(...).

The bag form is cheap to build when values repeat. With m distinct values, kth_smallest walks at most m keys, so the median costs about m times log m steps, because of the sort, not about n.

A sorted list for the order questions

The examples above sort the keys every time a question is asked. That is simple, and it is fine for a few questions. A program that asks many questions on a bag that changes slowly can keep the keys in a sorted list instead, and update the list as values come and go. bisect.insort inserts a key into a sorted list in its correct place.

keys = [3, 5, 9]
counts = {3: 2, 5: 3, 9: 1}

The keys list is always in order, so the smallest key is keys[0] and the nearest key to any value can be found with bisect. Inserting into the middle of a Python list costs time that grows with the list, so this structure suits a few thousand distinct values. For larger data, a balanced tree or a third-party sorted container is the usual tool.

Common mistakes

Leaving a key with count 0

If you lower the count to 0 but leave the key in the dict, the key still appears in min, sorted and the printed dict. Here is a small example.

after bad removal: {4: 0, 7: 2} first key = 4

The value 4 is not in the bag, but min still reports it. The fix is the bag[x] == 1 branch in remove_one, which deletes the key when the last copy goes.

A Counter has the same trap in one case. Subtracting one Counter from another drops zero counts, but lowering a count by hand with c[x] -= 1 keeps the key:

Counter keeps zero key: Counter({7: 2, 4: 0}) elements: [7, 7]

The elements() output is correct, because a zero count adds no copies. The 4: 0 entry still shows in the printed form and in keys(). Delete the key when the count reaches zero, as remove_one does.

Adding to a count that does not exist yet

The line bag[x] = bag[x] + 1 fails for a plain dict when x is not in it. The dict raises KeyError on the read:

counts = {}
counts[9] = counts[9] + 1

KeyError: 9

Use bag[x] = bag.get(x, 0) + 1, as add does. It stores 1 when the key is missing and adds 1 when the key is present. A Counter avoids the problem for reads, because a missing key counts as 0, so Counter()[9] + 1 gives 1. That convenience is the reason to pick Counter for counting.

Using len instead of the sum of counts

len(bag) counts the distinct values. The number of copies is the sum of the counts, which is sum(bag.values()), or bag.total() for a Counter. The example below uses one bag with two different answers:

len: 2 size: 5

Calling key-based questions on a dict's keys view

A dict's keys() view cannot be indexed, so bag.keys()[0] fails. Sort the keys first, as the examples do:

bag = {3: 2, 5: 3}
print(bag.keys()[0])

TypeError: 'dict_keys' object is not subscriptable

Use sorted(bag)[0] for the smallest key, or min(bag).

Comparing numbers with is

Python's is checks whether two names refer to the same object. CPython keeps shared objects only for small integers, so is can look right for small numbers and fail for large ones. Use == for values:

True False

Practice

Exercise 1. Add the values 4, 4, 2, 7 and 4 to an empty bag. Then remove one copy of 4 twice. Write down the bag after each step.

Show the answer

After the adds, the bag is {2: 1, 4: 3, 7: 1}. After the first removal, it is {2: 1, 4: 2, 7: 1}. After the second removal, it is {2: 1, 4: 1, 7: 1}. The key 4 is still there, because it still has a count of 1.

Exercise 2. For the bag {2: 1, 4: 2, 9: 3}, what is kth_smallest(bag, 4)?

Show the answer

Walk the keys from the smallest. Key 2 adds 1, so seen is 1. Key 4 adds 2, so seen is 3. Key 9 adds 3, so seen is 6. The first time seen reaches 4 or more is at key 9. The answer is 9.

Exercise 3. Write a function count_at_least(bag, x) that returns how many copies have a value of x or more. Test it on the bag {2: 1, 4: 2, 9: 3} with x equal to 4, then with x equal to 5.

Show the answer

Keep the keys that are at least x, and add their counts. For x equal to 4, the answer is 5, because the copies of 4 and 9 are 2 plus 3. For x equal to 5, the answer is 3, because only the three 9s qualify.

5 3

Exercise 4. Why does remove_one delete the key when the count is 1, instead of storing 0 under it?

Show the answer

A key with count 0 still appears in min, in sorted and in the keys of the dict. Any question about the smallest or nearest value would then return a value that is not really in the bag.

Exercise 5. Rewrite counts[x] = counts[x] + 1 so that it works when x is not in the dict yet, without get.

Show the answer

Use a Counter, which returns 0 for a missing key: counts[x] += 1. Or use a defaultdict(int), which creates the key with the value 0 on first access. Either way, the line works the first time.

2

Summary

• A multiset keeps duplicates. Python's Counter is a dict from each value to its count, and it does most of the counting work.
• Adding a copy raises the count. Removing a copy lowers the count, and the key is deleted when the count reaches 0.
• The total number of items is the sum of the counts, not len of the dict.
• A sorted list of keys with bisect answers order and range questions, and a Counter subtraction drops zero counts for you.
• Compare numbers with ==, not is.