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.
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
banned = ["spam@a.com", "junk@b.com", ...] # a list of 5,000 addresses
if email in banned: # up to 5,000 comparisonsbanned = {"spam@a.com", "junk@b.com", ...} # the same, as a set
if email in banned: # about 1The 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.
| Operation | Cost | What happens |
|---|---|---|
items[i] | One step | Jumps straight to position i |
items.append(x) | One step, on average | Writes into spare room at the end |
items.pop() | One step | Removes the last item |
x in items (a list) | Up to n steps | Compares with each item in turn |
items.insert(0, x) | n steps | Every item shifts one place right |
items.pop(0) | n steps | Every item shifts one place left |
x in my_set, key in my_dict | One step, on average | Hashes and looks in one place |
my_dict[key] | One step, on average | Hashes 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:
| Operation | Cost |
|---|---|
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_b | Copies both into a new list |
text_a + text_b | Copies 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.
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.
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 this | Use this instead |
|---|---|
x in some_list, many times | A set |
| Looking things up by an id or name | A dict |
pop(0) or insert(0, x): a queue | collections.deque |
min() again and again as items change | heapq |
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.