Collections: Advanced

A scheduler holding 50,000 waiting jobs keeps asking which job runs next. Calling min(jobs) reads all 50,000 every time, and re-sorting after each arrival reorders the whole list to answer a question about a single item. The heapq module keeps an ordinary list arranged so the smallest item always sits at index 0. After a push or a pop, a short walk through the list repairs that arrangement.

Picture index i as a parent whose 2 children live at indexes 2*i + 1 and 2*i + 2. A list is a heap when every parent is less than or equal to both children. That rule puts the minimum at index 0 and says nothing about the order of the rest. Watch the list after each heappush:

The final list [1, 2, 9, 7, 4] is out of order, since 9 sits before 7 and 4, yet heap[0] holds the minimum. When 1 arrived it was appended at index 4, compared with its parent at index 1, swapped, then compared with index 0 and swapped again. A pop runs the other direction: the last item moves to index 0 and sinks, swapping with its smaller child at each level.

Those walks stay short because each level of the tree holds twice as many items as the level above it: 1, then 2, then 4, so 20 levels hold over 1,000,000 items. A push or pop on a 1,000,000-item heap visits roughly 20 levels at most, where min() reads every item. For data already sitting in a list, heapq.heapify(items) rearranges it into a heap in place, in a single pass.

Heaps compare items with <, so a tuple (priority, job) orders by priority first and compares job names only on a tie. Lower numbers leave first. The 2 jobs below share priority 1; decide which pops first, then play it.

Both priority-1 jobs tied, so Python compared the names, and 'backfill_events' sorts before 'fix_schema'. That fallback fails when the second item can't be compared, such as a dict describing the job. Put a sequence number between the priority and the payload: no 2 entries share a number, so Python never reaches the payload, and equal priorities leave in arrival order.

heapq builds min-heaps only. For largest-first order, push each number negated and negate it again on the way out, because the most negative stored value is the largest original.

When you need a top k once and have no queue to keep alive, heapq.nlargest(k, items) and heapq.nsmallest(k, items) answer in a single call. Both take key= the way sorted() does. The last line gets the same answer by sorting all 5 values to keep 2.

Only index 0 has a fixed meaning. The largest item always sits among the leaves, the slots with no children. In a list of n items those run from index n // 2 to n - 1, and nothing says which leaf holds the maximum. In [1, 2, 9, 7, 4] the maximum, 9, is at index 2. Meanwhile heap[-1] holds 4, the item that 1 displaced on its climb to the top. Asking a min-heap for its largest item still means scanning half the list.

Counting by hand means a dict plus, for every item, a membership check before the += 1. collections.Counter is a dict subclass built for tallies: pass it any iterable and it counts each item, and reading a key it never saw returns 0 instead of raising KeyError.

The repr runs from most to least common, so 404 precedes 301 only because it was seen first. counts[418] returned 0 without storing 418, which is why 418 in counts stays False. And most_common(2) returns (item, count) pairs, highest count first, ties in first-seen order.

Counters support arithmetic, which suits daily tallies that roll up into weekly ones. + adds counts key by key. - subtracts and then drops every key whose result is 0 or below, while the subtract() method changes the counter in place and keeps negatives. Before running this, decide which keys survive monday - tuesday.

search fell from 25 to -5, so - dropped it and subtract() kept it. refund never appeared on Monday: - ignored it, while subtract() recorded -2. Reach for - when a negative count means nothing, such as units left in a warehouse bin, and for subtract() when falling below zero is the signal you want to see.

A Counter counts whatever its iterable yields, and a string yields characters, so passing a raw log line tallies letters and spaces. Split the line to count words. update() adds another batch to an existing counter, which fits log lines arriving item by item.

Python 3.10 added Counter.total(). On 3.9, sum(words.values()) gives the same number, as the last line does.

Reads and writes behave differently on a Counter. A read of a missing key, counts['x'], answers 0 without storing anything. Any assignment stores. That includes += 1, which assigns 1 after fetching the 0. An assigned 0 stays stored as well. Once counts['x'] = 0 runs, 'x' in counts is True, and the key counts toward len(counts), which grows by 1. Unary plus, +counts, returns a new Counter with every zero and negative count removed, which tidies up after subtract().

Grouping rows under a key runs through most aggregation code: orders by customer, files by date, errors by service. With a plain dict, every append needs a check that the key's list exists yet. defaultdict moves that check inside the dict. You give it a factory, and a lookup on a missing key calls the factory, stores the result under that key and returns it.

The same grouping with defaultdict:

You pass list, the type itself, with no parentheses. The dict calls it with no arguments each time it meets a new key, so every customer gets a fresh list of their own. Converting with dict() before printing gives a plain dict, which also goes back to raising KeyError on a mistyped key.

int() returns 0, so defaultdict(int) is a tally you bump with += 1. set collects distinct values. A function you define works too, provided it takes no arguments. As the 2 dicts below fill, watch when each key first appears in each.

'us' joined by_region on the second event and clicks only on the fifth, the first time anything looked up clicks['us']. A key comes into existence at its first lookup. When each value is a small record, write the factory as a function:

That rule has a side effect you must predict: d[key] on a missing key inserts it, even inside an if that was only meant to look. .get() and in never call the factory, so they are the safe ways to ask about a key.

The if saw an empty list and printed nothing, yet 'dan' now sits in the dict with no orders, and a report counting customers would count dan. Converting to dict() once grouping ends shuts this door, because later lookups go back to raising KeyError.

A defaultdict keeps its factory in an attribute, default_factory. Setting d.default_factory = None once grouping ends makes missing keys raise KeyError again, and d stays the same object. That helps when other code already holds a reference to it, which a dict() copy would leave behind. .get(key, 0) takes a fallback of your own. Like plain .get(), it never calls the factory and stores nothing.

The insert moved 4 references to make room for 1 item. On a list of 1,000,000 items, a front insert moves 1,000,000 references, and a queue drained with pop(0) pays that again on every call, each a little shorter than the last. Over a whole drain the moves add up:

collections.deque, pronounced "deck" and short for double-ended queue, stores items in a chain of fixed-size blocks, 64 references each in CPython, with each block linked to the blocks on both sides. Adding at either end writes into the end block, or links a new block when that one is full. No stored item moves, so a front operation costs the same on 10 items as on 10,000,000.

The methods mirror each other. append and pop work on the right end, and their left-end twins are appendleft and popleft. Predict the last line before you play it, keeping in mind that extendleft adds its items to the front item by item.

extendleft([-1, -2]) put -1 at the front and then -2 in front of it, so the batch landed reversed. Pass reversed(batch) when its order has to survive.

A deque built with maxlen=n never holds more than n items. Adding to a full one drops an item from the opposite end, with no error. That makes it the usual holder for recent history, whether the last few events are retries or readings.

The last line shows the rule from the other side: appendleft on a full deque pushed e5 off the right. A rolling average of the last 3 latency readings needs nothing more:

Blocks make the ends fast and the middle slower. d[0] and d[-1] read an end block directly, while d[500000] on a 1,000,000-item deque walks block by block from the nearer end. Slicing raises an error:

rotate(-1) moves the front item to the back, which gives a round-robin over workers with no index arithmetic:

The limit is set once, when the deque is built. d.maxlen reads it back, and assigning to it raises AttributeError, so a buffer that must grow is rebuilt as deque(d, maxlen=new_size). Building from a long iterable applies the rule from the start: deque([1, 2, 3, 4, 5], maxlen=3) keeps [3, 4, 5]. Each item was appended in turn, and the oldest fell off the left as each new one arrived.

On a sorted list, you can find where a value belongs without reading every item. Compare the target with the middle item: if the middle is smaller, the target belongs to its right; otherwise it belongs at or left of it. Each comparison halves what remains. The bisect module runs that loop in C; written out in Python, you can watch the range shrink.

Both return an insertion index, the position where the value could go and keep the list sorted, and they differ only when the value is already present. bisect_left returns the index of the first equal item; bisect_right, also callable as bisect.bisect, returns the index right after the last one.

To check membership, compute i = bisect.bisect_left(ts, x) and then test i < len(ts) and ts[i] == x. The bounds check matters because a value above everything returns len(ts). To count values from lo up to but excluding hi, subtract: bisect_left(ts, hi) - bisect_left(ts, lo). On sorted event timestamps, that counts a time window's events with no loop.

A sorted list of thresholds turns bisect_right into a decision table: the index it returns is the bucket number. A value equal to a threshold lands in the bucket above it; switch to bisect_left when boundary values belong below.

bisect.insort(lst, x) finds the position with bisect_right and inserts there, so the list is sorted after every new item.

The search half of insort takes a few comparisons, but the insert half is list.insert, which shifts every later item like the front insert in the deque section. For a few thousand items that cost is small. When a large list takes many inserts, append everything and sort once; that is usually faster. If you only ever need the smallest item, use a heap instead.

Bisect never checks the order, so check it yourself once, where sorted data enters your code. all(a <= b for a, b in zip(ts, ts[1:])) compares each neighbouring pair and returns False at the first pair out of order. That pass reads the whole list, which is the cost bisect saves you, so run it when the list is built, never inside a loop of searches. A list kept only through insort stays sorted by construction and needs no check.