Python Module 5 – Built-in data structures: lists, dicts, sets and more

Choosing the right data structure

Pick a list, tuple, dict, set, deque, heap or sorted list from the operations your program repeats, compare their costs, and check the choice with timeit.

Intermediate
20 minutes
Examples run with Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

Compare the cost of common operations on list, dict, set and deque
Choose a structure from the operations a problem needs
Measure instead of guessing with timeit
Detect a membership test that makes a loop quadratic, and fix it
Estimate the memory of a container with sys.getsizeof()

Before you start

What you’ll learn · Before you start

What you will learn

Compare the cost of common operations on list, dict, set and deque
Choose a structure from the operations a problem needs
Measure instead of guessing with timeit
Detect a membership test that makes a loop quadratic, and fix it
Estimate the memory of a container with sys.getsizeof()

Before you start

On this page

Asking whether a value is in a list of 100,000 items took about 2.7 ms in the run recorded below, and asking a set the same question took 16 ns. So choose a data structure by the operations your program repeats most, not by habit. Write down what happens to the data again and again: is it looked up by a key, checked for membership, taken from the front, kept in order, or read by position? Then pick the structure for which those operations are cheap: a dict for lookups by key, a set for “have I seen this?”, a deque for queues, a heap: A list kept in heap order: the item at index k is no larger than the items at 2k + 1 and 2k + 2, its children. The smallest item is then at index 0, and the rest of the list is only partly sorted. More in “heapq, bisect and array for efficient data” for “the smallest next”, a sorted list with bisect for ordered data and ranges, and a list (or a tuple, if it never changes) for everything read by position.

A quick measurement with timeit settles any doubt. Below, the structures of this module stand side by side, with their costs, two measured traps and their memory.

Start from the operations your program repeats

The questions below put the structures in an order that settles most cases. Ask them from the top and stop at the first “yes”:

A first choice of structure from the operation a program repeats most

Text description of the diagram

The diagram is one column of five questions, read from the top. Each box names the structure to use when the answer is yes; a "no" leads down to the next question.

Do you always take the smallest or most urgent item next? Yes: heapq on a list.
Do you need sorted order or questions about ranges? Yes: a sorted list searched with bisect.
Do you take items from the front? Yes: collections.deque.
Do you look values up by a key? Yes: dict.
Do you only ask whether an item was seen before? Yes: set.

When every answer is no, a list is the right start, or a tuple if the collection never changes.

The same rules fit into a small function, which also shows how to keep such a decision honest: write the cases down as tests.

The decision table as a function, with six programs Python · chooser.py

def choose(needs):
    """The structure to start from, given the operations a program needs most often."""
    if "smallest next" in needs:
        return "heapq on a list"
    if "in order" in needs or "range" in needs:
        return "sorted list with bisect"
    if "take from front" in needs:
        return "collections.deque"
    if "look up by key" in needs:
        return "dict"
    if "seen before?" in needs:
        return "set"
    if "dict key" in needs:
        return "tuple"
    return "list"


# Six programs and the operations each one repeats most:
scenarios = [
    ("print queue, jobs leave from the front", {"add at back", "take from front"}, "collections.deque"),
    ("student records by roll number", {"look up by key", "update"}, "dict"),
    ("unique visitors of a page", {"seen before?", "count"}, "set"),
    ("leaderboard shown in score order", {"add", "in order", "range"}, "sorted list with bisect"),
    ("next train by departure time", {"add", "smallest next"}, "heapq on a list"),
    ("map cell as a dictionary key", {"dict key"}, "tuple"),
]

for program, needs, expected in scenarios:
    picked = choose(needs)
    assert picked == expected, (program, picked)
    print(f"{program:38} -> {picked}")
print("all", len(scenarios), "checks passed")

Output

print queue, jobs leave from the front -> collections.deque
student records by roll number         -> dict
unique visitors of a page              -> set
leaderboard shown in score order       -> sorted list with bisect
next train by departure time           -> heapq on a list
map cell as a dictionary key           -> tuple
all 6 checks passed

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 chooser.py

The order of the questions matters. A leaderboard also looks scores up, but what it repeats most is showing them in order, so the sorted list wins over a dict. A program with two equally frequent needs often uses two structures: a dict to find a ticket by its id, plus a heap to find the most urgent one. Keeping two structures in step costs a little code, and it is still much cheaper than scanning one structure that suits neither need. Press Edit, add a seventh program to scenarios with the operations you think it repeats, and run it: the assert tells you at once whether choose() agrees with you.

Checkpoint

Check: Choosing by the repeated operations

Question 1 of 2 A library app finds books by ISBN thousands of times a day and lists them in title order once a week. Which structure should hold the books?
Choose one answer.

A dict from ISBN to book, sorted with sorted() when the weekly list is made A list of books, scanned for each ISBN A set of ISBNs A sorted list searched with bisect

Show the answer: Question 1 of 2

Answer: A dict from ISBN to book, sorted with sorted() when the weekly list is made

Pick by the operation the program repeats most, here the lookup by ISBN, so a dict. A rare need, the weekly list in title order, is met by sorting when it comes up.
Question 2 of 2 A help desk finds tickets by id all day, and it also always serves the most urgent ticket next. What does this lesson suggest?
Choose one answer.

Only a dict, with min() to find the most urgent ticket A sorted list of tickets, sorted again after every change Only a heap, scanned whenever a ticket must be found by id A dict from id to ticket, plus a heap of (urgency, counter, id) for the next ticket

Show the answer: Question 2 of 2

Answer: A dict from id to ticket, plus a heap of (urgency, counter, id) for the next ticket

Two equally frequent needs often call for two structures kept in step: a dict for the lookups and a heap for the order.

Each structure’s costs follow from how it is built

The costs come from how CPython builds each structure:

A list is an array of references in one block of memory, with spare room at the end. Reading or replacing a[i] costs the same for any i, and append() is cheap because the spare room means the array only rarely has to grow, so its cost is amortised cost: The cost of an operation averaged over a long run of them. list.append() is amortised O(1): most appends use spare room at the end of the list, and the rare one that grows the array is paid for by the many before it. O(1). Inserting or deleting near the front moves everything behind that position.
A dict is a hash table: A table of slots in which each key is kept at a place worked out from its hash, so a lookup looks in one slot or a few instead of comparing every key. Python's dict and set are hash tables. More in “Dictionaries: keys, values and views”: hash(key) decides where an entry lives, so finding a key does not depend on how many others there are. A set works the same way, with keys and no values. These are average costs, which assume that keys rarely share a hash value; if every key hashed to the same value, each operation would degrade to O(n).
A deque is built for both ends: adding or removing there costs the same at any length, while reaching the middle by index costs O(n).

Average costs in CPython for a collection of n items
Operation	Time	Extra space	Note
list: a[i], a[i] = x, len(a)	O(1)	O(1)
list: append(x), pop()	O(1)	O(1)	amortised: an occasional append resizes the array
list: insert(0, x), pop(0), x in a	O(n)	O(1)
dict: d[k], d[k] = v, del d[k], k in d	O(1)	O(1)	average; O(n) if every key collides
set: add(x), discard(x), x in s	O(1)	O(1)	average, as for dict
deque: append, appendleft, pop, popleft	O(1)	O(1)
deque: d[i] in the middle	O(n)	O(1)
heapq: heappush, heappop	O(log n)	O(1)
sorted list: bisect_left, bisect_right	O(log n)	O(1)
sorted list: insort	O(n)	O(1)

The list, dict and set rows come from the Python documentation’s own page of operation costs, which also covers slices, sorting and the set operations; the deque rows come from the collections documentation, and the heap and bisect rows from the documentation of those modules, as in the previous lesson.

big-O notation: A way to say how the work of an algorithm grows with the size of its input: O(n) grows at most in proportion to n, O(√n) with the square root of n. More in “Solving problems with loops step by step” describes how a cost grows. The model below turns each growth rate of the table into a time, for a machine that does 100 million simple steps a second. It starts at 100,000 items, the largest size this lesson measures:

Interactive · change it and see How long each growth rate takes at the lesson's sizes Pick an input size and how many simple operations the machine does a second. Each bar is the time for that many operations, on a log scale.

For n = 100 thousand at 100 million operations a second: O(n log n) takes 17 ms, O(n²) 1.7 minutes and O(2ⁿ) forever. Within a second: O(1), O(log n), O(n), O(n log n).

Finishes within a second O(n log n) and faster

O(n²) takes 1.7 minutes

O(n log n) takes 17 ms

The numbers as a table

Time for n = 100 thousand
Growth rate	Operations	Time
O(1)	1	10 ns
O(log n)	16.6	166 ns
O(n)	100 thousand	1 ms
O(n log n)	1.7 million	17 ms
O(n²)	10 billion	1.7 minutes
O(n³)	1,000 trillion	115.7 days
O(2ⁿ)	too many to count	forever

At 100,000 items an O(1) operation is one step, about 10 ns, O(log n) about 17 steps and O(n) a millisecond, while O(n²) work, such as a scan of the list for every one of its items, takes 1.7 minutes. Big-O says nothing about the constant in front, though, and for small collections the constant is what you measure.

Key idea

The costs follow from the build: a list is an array, cheap at its end and by position; a dict and a set are hash tables, cheap for any key on average; a deque is cheap at both ends.

Checkpoint

Check: What each structure costs

Question 1 of 2 Which of these list operations costs O(n)?
Choose one answer.

a[i] a.pop(0) len(a) a.append(x)

Show the answer: Question 1 of 2

Answer: a.pop(0)

A list is an array of references with spare room at the end: cheap at the end and by position, slow at the front, where every later item has to move.
Question 2 of 2 In the model, at 100,000 items and 100 million simple steps a second, how many seconds does O(n²) work take?
Type a number.
Your answer seconds

A hint

n² is 100,000 × 100,000 steps.

Show the answer: Question 2 of 2

Answer: 100 seconds

100,000² is 10 billion steps, and at 100 million steps a second that is 100 seconds, the 1.7 minutes the model shows. O(n) work at the same size takes 1 ms.

Measured: a set answers in the same time at every size

timeit runs a statement many times and reports the time. Its documentation advises taking the best of several repeats, because slower runs are usually caused by other programs rather than by Python, and this example follows that advice:

x in list, set and dict, for 10, 1,000 and 100,000 items Python · membership_timing.py

import timeit


def per_lookup_ns(stmt, names):
    """Nanoseconds per run of stmt: the best of 5 repeats, each about 20 ms long."""
    timer = timeit.Timer(stmt, globals=names)
    once = max(timer.timeit(number=1), 1e-7)
    number = max(1, int(0.02 / once))
    return min(timer.repeat(repeat=5, number=number)) / number * 1e9


print(f"{'items':>7}  {'list, absent':>12}  {'list, first':>11}  {'set':>5}  {'dict':>5}  {'set(list) once':>14}")
for n in [10, 1_000, 100_000]:
    names = {"data": list(range(n))}
    names["as_set"] = set(names["data"])
    names["as_dict"] = dict.fromkeys(names["data"])
    cells = [
        per_lookup_ns("-1 in data", names),  # a value that is not there: every item is checked
        per_lookup_ns("0 in data", names),  # the first item: found at once
        per_lookup_ns("-1 in as_set", names),
        per_lookup_ns("-1 in as_dict", names),
        per_lookup_ns("-1 in set(data)", names),  # building a set for one question
    ]
    print(f"{n:>7,}  {cells[0]:>10,.0f}ns  {cells[1]:>9,.0f}ns  {cells[2]:>3,.0f}ns  {cells[3]:>3,.0f}ns  {cells[4]:>12,.0f}ns")

Output

  items  list, absent  list, first    set   dict  set(list) once
     10          99ns         12ns   16ns   16ns           185ns
  1,000      10,626ns         12ns   16ns   15ns        25,830ns
100,000   2,657,080ns         12ns   16ns   16ns     2,648,754ns

This output changes from run to run: it measures time, which differs from one run to the next and from one computer to another; the computer of this run is named below the output.

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 membership_timing.py

Four things stand out in the recorded run, and in yours they will have the same shape even where the numbers differ:

A set and a dict take the same time at every size. Their columns barely move from 10 items to 100,000.
A list scan grows with the list. Looking for a value that is not there checks every item, so the time grows in step with the length of the list. At 100,000 items the scan takes more than ten thousand times as long as the set lookup.
Where the item is matters to a list. The first item is found after one comparison, as fast as a set lookup. For a handful of items, or for lists where the item searched for is usually near the front, a list is fine.
Building a set for one question saves nothing. x in set(data) has to visit every item to build the set before it can look, so its column grows with the list just like the scan does. Convert a list to a set when you will ask many questions, and keep the set.

Checkpoint

Check: Measuring membership with timeit

Question 1 of 2 In the recorded run, how did finding the first item of a 100,000-item list compare with a set lookup?
Choose one answer.

Twice as slow at every size It raised an error for the large list About the same: 12 ns against 16 ns About 100,000 times slower

Show the answer: Question 1 of 2

Answer: About the same: 12 ns against 16 ns

Where the item is matters to a list: at the front it is found at once. Only a value far back, or a missing one, makes the scan grow with the list.
Question 2 of 2 Why did -1 in set(data) take longer as the list grew, although a set lookup takes the same time at every size?
Choose one answer.

Large sets are slower to search -1 is missing, so the set is scanned Building the set visits every item of the list before the one lookup set() sorts the items first

Show the answer: Question 2 of 2

Answer: Building the set visits every item of the list before the one lookup

Converting a list to a set costs a pass over every item. Do it once and keep the set when you will ask many questions.

A membership test on a list makes its loop quadratic

The most common slow program in Python has a membership test on a list inside a loop. Each test scans the list, the list grows with every new item, and so the comparisons add up to an amount that grows with the square of the input size, quadratic time: Work that grows with the square of the input size, O(n²): ten times the input takes about a hundred times as long. A membership test on a list inside a loop over the items is the usual cause.. Removing duplicates from a list of ids is the classic case:

Removing duplicates with a list of seen ids, and with a set Python · dedupe_timing.py

import time

ids = [i * 7919 % 2_000 for i in range(2_000)] * 2  # 2,000 different ids, each seen twice


def unique_with_list(values):
    seen = []
    for v in values:
        if v not in seen:  # scans the whole list every time
            seen.append(v)
    return seen


def unique_with_set(values):
    seen = set()
    order = []
    for v in values:
        if v not in seen:  # one hash lookup
            seen.add(v)
            order.append(v)
    return order


for unique in (unique_with_list, unique_with_set):
    start = time.perf_counter()
    result = unique(ids)
    print(f"{unique.__name__}: {len(result):,} unique ids in {(time.perf_counter() - start) * 1000:.1f} ms")

Output

unique_with_list: 2,000 unique ids in 50.9 ms
unique_with_set: 2,000 unique ids in 0.2 ms

This output changes from run to run: it measures time, which differs from one run to the next and from one computer to another; the computer of this run is named below the output.

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 dedupe_timing.py

Both functions return the same ids in the same order: the set only answers “seen before?”, and a list keeps the order. With 2,000 ids seen twice each, the list version already takes many times longer, and because its work grows with the square of the count, ten times as many ids would make it about a hundred times slower, while the set version would take only about ten times as long. The model in the section on costs shows the same step: set its size to 2,000 and then to 20,000, and O(n²) goes from 40 ms to 4 s while O(n) goes from 20 µs to 200 µs.

A list as the memory of a loop

if v not in seen: seen.append(v) with seen = [] scans every id seen so far, on every pass. Keep a set for the question, seen = set() and seen.add(v), and a list only for the order, as unique_with_set does.

Every time a loop contains if x in some_list or some_list.index(x), ask whether a set or a dict could answer the question instead.

Duplicate Line Remover Remove repeated lines from pasted text while keeping the first copy of each in order, the job unique_with_set does.

Checkpoint

Check: The quadratic membership trap

Question 1 of 2 unique_with_list took 50.9 ms for 4,000 ids in the recorded run. About how long would ten times as many ids take?
Choose one answer.

About 5 seconds, a hundred times as long About 50 seconds, a thousand times as long About the same, because the ids are still small numbers About 0.5 seconds, ten times as long

Show the answer: Question 1 of 2

Answer: About 5 seconds, a hundred times as long

50.9 ms × 10² is about 5.1 s. In the model, O(n²) grows from 40 ms at 2,000 to 4 s at 20,000 for the same tenfold step.
Question 2 of 2 Which of these is quadratic in the number of names?
Choose one answer.

for n in names: with if n not in seen_list: seen_list.append(n) inside names.sort() for n in names: with if n not in seen_set: seen_set.add(n) inside total = sum(len(n) for n in names)

Show the answer: Question 2 of 2

Answer: for n in names: with if n not in seen_list: seen_list.append(n) inside

The pattern to watch for is a membership test, or index(), on a list inside a loop over a similar number of items.

Sets and dicts take four to five times the memory of a list

Speed is not the only cost. A hash table keeps spare slots so that collisions stay rare, which makes sets and dicts larger than lists of the same items:

The size of five containers of 1,000 ints Python · memory_sizes.py

import sys
from collections import deque

items = list(range(1_000))
containers = {
    "list": list(items),
    "tuple": tuple(items),
    "deque": deque(items),
    "set": set(items),
    "dict": dict.fromkeys(items),
}
# getsizeof counts each container itself, not the 1,000 int objects it refers to.
for name, container in containers.items():
    print(f"{name:5} of 1,000 items: {sys.getsizeof(container):>6,} bytes")

Output

list  of 1,000 items:  8,056 bytes
tuple of 1,000 items:  8,048 bytes
deque of 1,000 items:  8,680 bytes
set   of 1,000 items: 32,984 bytes
dict  of 1,000 items: 36,952 bytes

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 memory_sizes.py

sys.getsizeof() measures the container alone, not the 1,000 int objects it refers to, which are the same for all five. On this 64-bit build the list, the tuple and the deque take about 8 KB, mostly one 8-byte reference per item, while the set takes about four times as much and the dict about four and a half times. The browser runner is a 32-bit build with other sizes, so this example shows a recorded run instead of a Run button. For a few thousand items the difference rarely matters; for tens of millions, it decides whether the data fits in memory, and the array module of the previous lesson saves even more for plain numbers.

Checkpoint

Check: Memory of the containers

Question 1 of 2 In the recorded run, a set of 1,000 ints took 32,984 bytes and a list of the same ints 8,056. Why is the set larger?
Choose one answer.

The set stores each int twice A hash table keeps spare slots so that collisions stay rare getsizeof() counts the ints for the set but not for the list A set keeps its items sorted

Show the answer: Question 1 of 2

Answer: A hash table keeps spare slots so that collisions stay rare

A hash table works well only while it has empty slots, so a set or a dict needs four to five times the memory of a list of references for the same items.
Question 2 of 2 What does sys.getsizeof(a_list) measure?
Choose one answer.

The list object itself, its references included, but not the objects they refer to The memory of the whole program The list and every item in it The number of items

Show the answer: Question 2 of 2

Answer: The list object itself, its references included, but not the objects they refer to

sys.getsizeof() counts the container alone: for a list, mostly one 8-byte reference per item on a 64-bit build, about 8 KB for 1,000 items.

Match the structure to your own program

The table pairs common situations with the structure to choose and the one to avoid:

Situation	Choose	Avoid
Find records by an id or a name	`dict`	a list searched with a loop
Remove duplicates, count distinct values, test membership	`set` (or `dict.fromkeys()` to keep order)	`if x not in some_list` in a loop
Process jobs in arrival order	`collections.deque`	`list.pop(0)`
Count how often each value occurs	`collections.Counter`	a dict updated by hand
Always take the most urgent or the earliest item	`heapq` on a list	sorting the whole list each time
Answer range questions on data that rarely changes	a sorted list with `bisect`	scanning for every question
A fixed record, or a key made of several values	`tuple`	a list, which cannot be a key
Items read and replaced by position	`list`	a dict with numbers 0 to n - 1 as keys

For a program of your own, answer the two questions above the next table. It marks the structures that fit, rules the others out with the reason, and shows the cost of each in the lesson’s own numbers:

Interactive · answer and compare Which structure fits the operation your program repeats? Answer two questions about your program. The table marks the structures that fit and says why the others do not.

Answer the questions above: the table then marks what fits your case and says why the rest does not.

Six structures against the five operations of this lesson, with the numbers of the recorded runs
Structure	Find a value by key	Ask "is it there?"	Take the first in	Take the smallest	Sorted order and ranges
list Built as: an array of references	Poor no keys: finding a record means a scan, O(n)	Poor x in a scans: 2.66 ms at 100,000 items in the run	Poor pop(0) moves every other item, O(n)	Poor min() reads every item, O(n)	Mixed sort() once, then bisect it
dict Built as: a hash table of keys and values	Good d[k] is one hash lookup, O(1) on average	Good k in d took about 16 ns at every size in the run	Poor keeps insertion order, but it is not a queue	Poor min() reads every key, O(n)	Poor insertion order only, never sorted order
set Built as: a hash table of keys	Poor keys only: there is no value to look up	Good x in s took about 16 ns at every size in the run	Poor no order to take the items in	Poor min() reads every item, O(n)	Poor no order at all
collections.deque Built as: a sequence built for both ends	Poor no keys: a scan, O(n)	Poor x in d scans, O(n)	Good popleft() and appendleft() in O(1)	Poor min() reads every item, O(n)	Poor arrival order only
heapq on a list Built as: a list kept in heap order	Poor no keys: a scan, O(n)	Poor x in h scans, O(n)	Poor takes the smallest, not the first in	Good heappop() in O(log n), h[0] in O(1)	Poor only the smallest item has a known place
sorted list + bisect Built as: a list kept in sorted order	Mixed bisect on sorted keys, O(log n)	Mixed bisect: about 17 comparisons at 100,000 items	Poor pop(0) moves every other item, O(n)	Mixed a[0] costs O(1), but each insort is O(n)	Good two bisects answer a range question, O(log n)

How the answers decide

“Which operation does your program repeat most often?” Find a value by its key: rules out list, set, collections.deque and heapq on a list and adds a caveat to sorted list + bisect. A dict finds the value for a key with one hash lookup at any size. A sorted list of keys can bisect for one in O(log n); the others must scan.
“Which operation does your program repeat most often?” Ask whether it holds an item: rules out list, collections.deque and heapq on a list and adds a caveat to dict and sorted list + bisect. A set answers x in s with one hash lookup, about 16 ns at every size in the run. A dict does too but keeps values you never use, and bisect needs about 17 comparisons at 100,000 items.
“Which operation does your program repeat most often?” Take the item that arrived first: rules out list, set, dict, heapq on a list and sorted list + bisect. Only a deque is built to take items from the front in constant time: list.pop(0) moves every other item, and the other structures keep no queue.
“Which operation does your program repeat most often?” Take the smallest or most urgent item: rules out list, set, dict and collections.deque and adds a caveat to sorted list + bisect. A heap gives the smallest next in O(log n) per push and pop, however the items arrive. A sorted list has it at index 0, but every insort costs O(n).
“Does it also need the items in sorted order, or answers about ranges?” Yes: rules out set, dict, collections.deque and heapq on a list and adds a caveat to list. Ranges and sorted order need sorted data: two bisects answer each range question in O(log n). A plain list has to be sorted first.

In short: a dict for keys, a set for membership, a deque for arrival order, a heap for the smallest next and a sorted list for ranges. When the answers leave nothing that fits, as for jobs taken in arrival order that also need ranges, the program has two needs, and two structures kept in step serve it better than one.

Python Online Compiler Time your own structures: change the sizes in membership_timing.py and run it in the browser.

Checkpoint

Check: Matching a structure to a situation

Question 1 of 2 A print server handles jobs in the order they arrive. Which structure holds the waiting jobs?
Choose one answer.

A heap of jobs collections.deque, with append() and popleft() A set of jobs A list, with append() and pop(0)

Show the answer: Question 1 of 2

Answer: collections.deque, with append() and popleft()

First in, first out is the deque's job: append() at the back, popleft() at the front, both O(1).
Question 2 of 2 A program stores the price of each seat by its row and its number. Which works as the dict key?
Choose one answer.

A list such as [12, 4] A tuple such as (12, 4) A set such as {12, 4} The string str(12) + str(4)

Show the answer: Question 2 of 2

Answer: A tuple such as (12, 4)

A fixed record, or a key made of several values, is a tuple. Lists and sets cannot be keys, because they can change.

Practise: unique visitors in constant time

The exercise asks for a class that counts visitors with the structure this lesson recommends for “have I seen this?”. Its sample tests count how often ids are compared, so a list that is scanned on every visit fails them:

Exercise · Easy · Python

Count unique visitors in constant time

A website counts its visitors. Complete the class UniqueVisitors in visitors.py:

add(visitor_id) records one visit and returns True when this visitor has not been seen before, False when they have.
count() returns how many different visitors have been seen.
visits() returns how many visits were recorded in all, repeats included.
visitor_id in tracker is True for a visitor who has been seen.

Each of these must take constant time on average, however many visitors there are. The sample tests check that with visitor ids that count how often they are compared: an add() that compares the new id with every id seen so far fails long before 2,000 visitors, while one that uses a hash lookup compares almost nothing.

Starter code · visitors.py

class UniqueVisitors:
    """Visits to a website, with the number of different visitors, each operation in constant time."""

    def __init__(self):
        self.seen = []  # choose a better structure for this
        self.total = 0

    def add(self, visitor_id):
        """Record a visit; True if this visitor is new, False if they were seen before."""
        return True

    def count(self):
        """How many different visitors have been seen."""
        return 0

    def visits(self):
        """How many visits were recorded, repeats included."""
        return self.total

    def __contains__(self, visitor_id):
        return False

The sample tests · test_visitors.py

from visitors import UniqueVisitors

COMPARISON_BUDGET = 10_000


class CountedId:
    """A visitor id that counts how often it is compared with another id for equality."""

    comparisons = 0

    def __init__(self, number):
        self.number = number

    def __hash__(self):
        return hash(self.number)

    def __eq__(self, other):
        CountedId.comparisons += 1
        if CountedId.comparisons > COMPARISON_BUDGET:
            raise AssertionError(
                f"more than {COMPARISON_BUDGET:,} comparisons between ids: add() and `in` must not compare the new id "
                "with every id seen so far; use a hash lookup"
            )
        return isinstance(other, CountedId) and self.number == other.number


def test_add_and_count():
    """counts each visitor once and reports whether a visit is a first visit"""
    tracker = UniqueVisitors()
    assert tracker.add("asha") is True
    assert tracker.add("ravi") is True
    assert tracker.add("asha") is False
    assert tracker.count() == 2
    assert tracker.visits() == 3


def test_contains():
    """answers `in` for seen and unseen visitors"""
    tracker = UniqueVisitors()
    for visitor in ["u1", "u2", "u1"]:
        tracker.add(visitor)
    assert "u1" in tracker
    assert "u3" not in tracker


def test_empty():
    """starts with no visitors and no visits"""
    tracker = UniqueVisitors()
    assert tracker.count() == 0
    assert tracker.visits() == 0
    assert "anyone" not in tracker


def test_mixed_id_types():
    """treats ids of different types as different visitors"""
    tracker = UniqueVisitors()
    assert tracker.add(7) is True
    assert tracker.add("7") is True
    assert tracker.add((7, "mobile")) is True
    assert tracker.add(7) is False
    assert tracker.count() == 3


def test_constant_time():
    """handles 2,000 visitors, each visiting twice, with few id comparisons"""
    CountedId.comparisons = 0
    tracker = UniqueVisitors()
    for round_ in range(2):
        for n in range(2_000):
            assert tracker.add(CountedId(n)) is (round_ == 0)
    for n in range(0, 2_000, 7):
        assert CountedId(n) in tracker
    assert CountedId(5_000) not in tracker
    assert tracker.count() == 2_000
    assert tracker.visits() == 4_000

A hint

self.seen starts as a list, and visitor_id in self.seen on a list compares the id with every item until it finds a match. Which structure answers "have I seen this before?" with one hash lookup instead? With that structure, count() is just its length, and add() only needs to look before it adds, and to count every visit.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

The self-check below draws on every section. It asks first about the idea your answers show you know least, and every choice it offers explains itself once you pick it:

Interview questions

Fresher · Which Python structures would you use for a stack, a queue and a priority queue, and why?

A stack, last in first out, is a plain list: append() pushes and pop() takes the last item, both O(1) at the end of the list. A queue, first in first out, is a collections.deque: append() adds at the back and popleft() takes from the front in O(1), whereas list.pop(0) moves every other item and costs O(n). A priority queue, where the smallest or most urgent item leaves first, is a list kept as a heap with heapq: heappush() and heappop() take O(log n). A good answer adds that equal priorities need a tie-breaker such as a running counter in the tuple, and that queue.Queue and queue.PriorityQueue are the versions to use when several threads share the queue.

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

Mid to senior

A game server keeps 2 million (score, player) pairs in a list and calls sorted() on every request to show the top 10 and the requesting player's rank. Scores change thousands of times a second. Redesign the in-memory structures and give the cost of each operation.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

Design an in-process rate limiter: each user may make at most 100 requests in any 60-second window. Which structures hold the state, what does one request cost, and how do you stop memory from growing with users who have stopped calling?

Model answer, Pro. First step and follow-ups

Key takeaways

List the operations your program repeats, then choose the structure that makes those cheap: dict for keys, set for membership, deque for queues, heap for the smallest next, sorted list with bisect for order and ranges, list for positions.
A list is an array of references: indexing and append() are O(1), while insert(0, x), pop(0) and in are O(n). Dicts and sets are hash tables with O(1) average lookups.
Measure with timeit and keep the best of several repeats: a set and a dict answered in the same time at every size, and building a set for one question costs a pass over every item.
x in some_list inside a loop makes the whole loop O(n²); a set or a dict turns it back into O(n).
Sets and dicts take four to five times the memory of a list of the same items, which matters for tens of millions.
When two operations matter equally, two structures kept in step, such as a dict and a heap, beat one that suits neither.

Terms in this lesson

amortised cost: The cost of an operation averaged over a long run of them. list.append() is amortised O(1): most appends use spare room at the end of the list, and the rare one that grows the array is paid for by the many before it.
quadratic time: Work that grows with the square of the input size, O(n²): ten times the input takes about a hundred times as long. A membership test on a list inside a loop over the items is the usual cause.

References

Time complexity of operations on built-in types (Python documentation) (Python Software Foundation)
Design and History FAQ: how are lists implemented in CPython? (Python Software Foundation)
Design and History FAQ: how are dictionaries implemented in CPython? (Python Software Foundation)
collections.deque (The Python Standard Library) (Python Software Foundation)
heapq: heap queue algorithm (The Python Standard Library) (Python Software Foundation)
bisect: array bisection algorithm (The Python Standard Library) (Python Software Foundation)
timeit: measure execution time of small code snippets (Python Software Foundation)
queue: a synchronized queue class (The Python Standard Library) (Python Software Foundation)
sys.getsizeof() (The Python Standard Library) (Python Software Foundation)

Report a problem with this lesson

In this module: Built-in data structures: lists, dicts, sets and more

Lists: create, index, slice and modify Free: 25 minutes
References, aliasing, shallow and deep copies Free lesson, Pro answers: 20 minutes
Sorting with key functions and stability Free lesson, Pro answers: 20 minutes
Tuples, unpacking and named tuples Free lesson, Pro answers: 20 minutes
Dictionaries: keys, values and views Free: 20 minutes
Sets and frozensets for membership and maths Free lesson, Pro answers: 20 minutes
List, dict and set comprehensions Free lesson, Pro answers: 25 minutes
collections: deque, Counter, defaultdict and more Free lesson, Pro answers: 20 minutes
heapq, bisect and array for efficient data Free lesson, Pro answers: 25 minutes
Text vs bytes: Unicode, encodings, bytearray Free lesson, Pro answers: 25 minutes
Choosing the right data structure Free lesson, Pro answers: 20 minutes

Your country

Choosing the right data structure

What you will learn

Before you start

What you will learn

Before you start

Start from the operations your program repeats

Each structure’s costs follow from how it is built

Measured: a set answers in the same time at every size

A membership test on a list makes its loop quadratic

Sets and dicts take four to five times the memory of a list

Match the structure to your own program

Practise: unique visitors in constant time

Count unique visitors in constant time

Results of the sample tests

Interview questions

A game server keeps 2 million (score, player) pairs in a list and calls sorted() on every request to show the top 10 and the requesting player's rank. Scores change thousands of times a second. Redesign the in-memory structures and give the cost of each operation.

Design an in-process rate limiter: each user may make at most 100 requests in any 60-second window. Which structures hold the state, what does one request cost, and how do you stop memory from growing with users who have stopped calling?

Key takeaways

References

Related tools