Pointer Walk

The Real Cost of Python Operations

Eight everyday list, dict and set operations with what they cost. Swapping [ ] for { } turns 5,000 checks into 1.

Languages and RuntimesBeginner9 min read

Short code is not always fast code

Python lets you do a great deal in one line. x in items. items.insert(0, x). Each looks like a single step. Some of them are, and some of them quietly walk through the entire collection.

The difference is invisible in the code. You have to know it.

The big one: in

Checking whether something is in a collection is one of the most common things a program does. Its cost depends entirely on what kind of collection it is.

39 in [ ... ]Interactive
Stored in
031
18
252
317
444
53
626
760
812
939
105
1147

Start. Is 39 in the list? A list has no shortcuts. Python starts at the first item and compares each one in turn.

Items compared
0

A list is a row of items with no index. The only way to find out whether a value is present is to look at the items one by one. If the value is near the end, or missing, every item is checked.

A set is a hash table. It works out where the value would be stored and looks only there. See Hash Tables.

Example

Two characters

python
banned = ["spam@a.com", "junk@b.com", ...]      # a list of 5,000 addresses
if email in banned:                             # up to 5,000 comparisons
python
banned = {"spam@a.com", "junk@b.com", ...}      # the same, as a set
if email in banned:                             # about 1

The square brackets became curly ones. Inside a loop over 100,000 emails, that is the difference between 500 million comparisons and 100,000.

Eight everyday operations

n is the number of items in the collection.

OperationCostWhat happens
items[i]One stepJumps straight to position i
items.append(x)One step, on averageWrites into spare room at the end
items.pop()One stepRemoves the last item
x in items (a list)Up to n stepsCompares with each item in turn
items.insert(0, x)n stepsEvery item shifts one place right
items.pop(0)n stepsEvery item shifts one place left
x in my_set, key in my_dictOne step, on averageHashes and looks in one place
my_dict[key]One step, on averageHashes and looks in one place

Two of the most common list operations, in and anything at the front, are linear. Everything else in the table is constant.

A few more worth knowing:

OperationCost
len(items)One step: the length is stored, not counted
min(items), max(items), sum(items)n steps
items[a:b]One step per item copied: a slice is a new list
sorted(items)About n × log n steps
list_a + list_bCopies both into a new list
text_a + text_bCopies both into a new string

The hidden quadratic

A linear operation on its own is fine. The trouble starts when one sits inside a loop.

python
unique = []
for item in items:              # n times
    if item not in unique:      # up to n comparisons each time
        unique.append(item)

There is one visible loop. But not in unique is a second loop, hidden inside one line. Together they are n × n. For 10,000 items that is up to 100 million comparisons.

python
seen = set()
unique = []
for item in items:
    if item not in seen:        # about 1 step
        seen.add(item)
        unique.append(item)

Same result, about 10,000 steps.

Fixing the common cases

If you keep doing thisUse this instead
x in some_list, many timesA set
Looking things up by an id or nameA dict
pop(0) or insert(0, x): a queuecollections.deque
min() again and again as items changeheapq
s += piece in a loop"".join(pieces)

Key takeaways

  • Some one-line Python operations are a single step and some scan the whole collection.
  • x in a list is linear. x in a set or dict is about one step.
  • Adding or removing at the front of a list shifts every item.
  • A linear operation inside a loop is quadratic, even when only one loop is visible.
  • Use a set for membership, a dict for lookups and a deque for queues.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress