Three modules people reimplement badly, with one sharp edge each.
statistics
| Function | Note |
|---|---|
mean, median, mode |
median averages the two middle values on an even count |
stdev / variance |
sample, divides by $n-1$ |
pstdev / pvariance |
population, divides by $n$ |
quantiles(data, n=4) |
returns the $n-1$ cut points, not $n$ buckets |
fmean, geometric_mean, correlation, linear_regression |
3.8-3.10 additions |
The stdev/pstdev distinction is a real correctness question, not a
formality: use stdev when your data is a sample from a larger population,
pstdev when it is the entire population. Getting it backwards inflates or
deflates every downstream confidence interval, and the two agree closely
enough at large $n$ that no test catches it.
quantiles(data, n=4) returns three values — the cut points between four
buckets. People reach for [0] expecting the minimum and get Q1.
mean of a list of Decimal returns a Decimal, and of Fraction a
Fraction. That is correct and occasionally surprising when the result is fed
to something expecting a float.
And the honest advice: beyond this, use numpy. statistics is exact,
readable, and works on any numeric type; it is also one to two orders of
magnitude slower than a vectorised equivalent. For a summary of a few hundred
values it is right. For a column of ten million it is not.
bisect
Binary search over a sorted sequence. bisect_left / bisect_right give
the insertion index; insort_left / insort_right insert there. key= has
been supported since 3.10, which removed the old decorate-sort-undecorate
dance.
The trap:
for item in stream:
insort(sorted_list, item) # O(n) per insert -- O(n^2) overallThe search is $O(\log n)$, which is what people remember. The insertion into a list is $O(n)$, because everything after the insertion point shifts. Building a sorted list this way is quadratic; appending everything and sorting once is $O(n \log n)$ and, on CPython’s Timsort with partially-ordered input, usually much better than that.
insort earns its place when you need the collection to stay sorted
between insertions — because something reads it — and the insert count is
small relative to the read count.
💡bisect_left(data, x) versus bisect_right(data, x) — when does
click to reveal
the choice matter?
Only when x is already present, and then it matters a lot. bisect_left
returns the index of the first element not less than x, so for an
existing value it points at it; bisect_right points just past the last
equal element.
For a membership test you want left:
i = bisect_left(data, x); found = i < len(data) and data[i] == x. Writing
that with bisect_right finds the wrong slot and reports False for a value
that is present.
For “insert while keeping equal elements in arrival order” you want right —
which is what plain insort does, and it is why insort is an alias for
insort_right.
For counting duplicates, the pair gives you the run in $O(\log n)$:
bisect_right(data, x) - bisect_left(data, x).
heapq, and the tuple trap
heapq is a min-heap on a plain list. heappush, heappop,
heapify (O(n)), nlargest / nsmallest, and merge for lazily merging
sorted iterables.
The trap that ships to production:
heappush(heap, (1, Task("a")))
heappush(heap, (1, Task("b"))) # TypeError: '<' not supported between Task instancesTuples compare element by element. When the priorities differ, the comparison stops at the first element and never looks at the payload — so the code works perfectly. The moment two items share a priority, Python falls through to comparing the payloads, and if they are not orderable it raises. If they are orderable — strings, say — it does something worse: it silently orders by payload, so your “FIFO among equal priorities” queue becomes alphabetical.
The documented fix is a monotonic counter as the tiebreaker, and the typed expression of it is a dataclass:
@dataclass(order=True, slots=True)
class Entry:
priority: int
sequence: int
name: str = field(compare=False)
order=True compares the fields as a tuple in declaration order;
field(compare=False) excludes the payload. It is precise, self-documenting,
and — unlike a bare tuple — the intent survives a reader who has not thought
about tuple comparison semantics.
⚠ 3.14 adds heapify_max, heappush_max and heappop_max, so max-heaps
no longer need the negate-the-priority trick.
💡heapq has no remove. How do you cancel a queued task?
click to reveal
Lazy deletion, and it is the documented approach.
Removing an arbitrary element from a heap is $O(n)$ to find plus $O(\log n)$
to re-heapify — and the stdlib does not expose a re-heapify-from-index
primitive, so you would be calling heapify on the whole list.
Instead, record the cancellation in a set and skip cancelled entries as they come out of the top:
def pop(self) -> str:
while self._heap:
entry = heappop(self._heap)
if entry.name in self._cancelled:
self._cancelled.discard(entry.name)
continue
return entry.name
raise IndexError("pop from an empty TaskQueue")Cancellation is $O(1)$, and the cost is deferred to the pop that eventually discards the entry — amortised $O(\log n)$ across the queue’s lifetime. The price is memory: a heap full of cancelled entries stays large. If cancellation is common, periodically rebuild the heap from the live entries.
Note the discard inside the loop: without it the cancelled-set grows
forever, which is the same leak in a different container.