MiddlePerformanceOccasionalNot answered yet
Why is a per-value list.count tally far slower than one hash-based Counter pass?
data.count(v) is an O(n) scan; running it once per distinct value makes the tally O(n·u) — near O(n²) when values vary. Counter(data) (or a plain dict) hashes each element once in one O(n) pass, so the tally drops from 40s to under a second.
- ✗Blaming loop or interpreter overhead, not the O(n) rescan
- ✗Calling
list.countorinonce per unique value - ✗Thinking Counter wins by a constant factor, not complexity class
- →When is a
list.countinside a loop actually acceptable? - →How does
Counterbehave on unhashable elements?
The slow version calls data.count(v) for each unique value, and each call rescans the whole list — so the work is O(n · u), quadratic when almost every element is distinct.
# Slow: count() rescans the whole list for every distinct value → O(n * u)
counts = {v: data.count(v) for v in set(data)}Counter (or a hand-rolled dict) makes one pass, hashing each element to its bucket in amortised O(1), for O(n) overall — the same tally in a fraction of the time.
from collections import Counter
counts = Counter(data) # one O(n) pass, each element hashed exactly onceThe gap is a complexity class, not interpreter overhead — no comprehension, dict pre-sizing, or sort makes the rescanning version competitive.
