Choosing Data Structures for Speed
15 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)The biggest speed-ups rarely come from tricks. They come from storing data in the structure whose operations are cheap for what you do most.
Membership: list, set and dict
A hash table finds an item by computing a number, the hash, from it and jumping straight to that place. Lookup time stays about the same however many items are stored. Sets and dicts are hash tables.
Asking x in items on a list checks item after item. A set or dict computes a number from x and jumps to the right place, so the time hardly grows with the size.
codes = [f"A{n}" for n in range(1000)]lookup = set(codes)print("A999" in codes)print("A999" in lookup)print("B1" in lookup)Example 1 · List scan against set lookup
import timeit
codes = [f"A{n}" for n in range(20000)]lookup = set(codes)target = "A19999"t_list = min(timeit.repeat(lambda: target in codes, number=200, repeat=3))t_set = min(timeit.repeat(lambda: target in lookup, number=200, repeat=3))print("set lookup is faster:", t_set < t_list)set lookup is faster: True
What this code does
- The target is the last item, which is the worst case for a list.
- The set finds it with one jump.
- On 20000 items the set is usually a few thousand times faster.
Both give the same answers, so the choice is only about speed. A set needs hashable items and does not keep order the way a list does. Build it once, outside the loop.
Queues: deque instead of pop(0)
A deque, short for double-ended queue, lets you add and remove items at both ends quickly. It is the right structure for queues and sliding windows.
Taking the first item of a list with pop(0) shifts every other item one place left. A deque removes from either end without shifting, so use it for queues.
from collections import deque
queue = deque(["order-1", "order-2", "order-3"])queue.append("order-4")print(queue.popleft())print(list(queue))Example 2 · pop(0) against popleft()
import timeitfrom collections import deque
def drain_list(): items = list(range(20000)) while items: items.pop(0)
def drain_deque(): items = deque(range(20000)) while items: items.popleft()
t_list = min(timeit.repeat(drain_list, number=1, repeat=3))t_deque = min(timeit.repeat(drain_deque, number=1, repeat=3))print("deque is faster:", t_deque < t_list)deque is faster: True
What this code does
- Both functions empty a queue of 20000 items from the front.
- Each
pop(0)shifts the remaining items;popleftdoes not. - The gap grows quickly as the queue gets longer.
The cost of list.pop(0) grows with the list. With 100000 waiting items it becomes a real slowdown, and deque.popleft() stays quick.
Sorted data: bisect and heapq
A heap is a structure that keeps its smallest item easy to reach. Python's heapq module uses a plain list as a heap, so you can take the smallest item without sorting everything.
If a list is already sorted, bisect finds a position in about log n steps instead of scanning. If you only need the smallest few items, heapq avoids a full sort.
import bisectimport heapq
scores = [35, 48, 52, 67, 80]print(bisect.bisect_left(scores, 52))bisect.insort(scores, 60)print(scores)print(heapq.nsmallest(2, [9, 3, 7, 1]))Example 3 · Binary search against a scan
import bisectimport timeit
prices = list(range(0, 200000, 2))target = 199998
def scan(): return target in prices
def binary(): i = bisect.bisect_left(prices, target) return i < len(prices) and prices[i] == target
print(scan() == binary())t_scan = min(timeit.repeat(scan, number=50, repeat=3))t_bin = min(timeit.repeat(binary, number=50, repeat=3))print("bisect is faster:", t_bin < t_scan)True bisect is faster: True
What this code does
- The first line proves both functions give the same answer.
bisect_lefthalves the range at every step, so about 17 steps for 100000 items.- This only works because the list is sorted.
bisect_left returns the index where 52 sits. insort keeps the list sorted but still shifts items on insert. Keep the list sorted from the start, because sorting before every search would cost more than it saves.
Counting and grouping
Counting with items.count(x) for each x walks the whole list every time. A Counter or defaultdict reads the data once and keeps a running total per key.
from collections import Counter, defaultdict
sales = ["pen", "book", "pen", "lamp", "pen"]print(Counter(sales).most_common(1))
by_first = defaultdict(list)for item in sales: by_first[item[0]].append(item)print(dict(by_first))Example 4 · Counting once against counting repeatedly
import timeitfrom collections import Counter
words = [f"w{n % 200}" for n in range(4000)]
def with_count(): return {w: words.count(w) for w in set(words)}
def with_counter(): return dict(Counter(words))
print(with_count() == with_counter())t_count = min(timeit.repeat(with_count, number=3, repeat=3))t_counter = min(timeit.repeat(with_counter, number=3, repeat=3))print("Counter is faster:", t_counter < t_count)True Counter is faster: True
What this code does
- Both return the same totals.
words.countwalks all 4000 words for each of the 200 unique words.Counterwalks them once.
One pass over the data is the pattern to look for. If you see a loop that calls count or in list inside another loop, a dict or set can usually remove the inner loop.
Know the cost of each operation
Choosing well means knowing what each operation costs. Here n is the number of items.
- list: index and append are fast;
in,insert(0, x)andpop(0)walk or shift n items. - set and dict:
in, add, remove and get take about the same time for any n, on average. - deque: add and remove at either end are fast; indexing the middle is slow.
- sorted list with bisect: search takes about log n steps; inserting still shifts items.
Next step
Check your understanding
12 quick questions