MiddleПроизводительностьИногдаЕщё не отвечали
Почему подсчёт через list.count на каждое значение намного медленнее одного прохода Counter?
data.count(v) — это скан O(n); запуск на каждое различное значение делает подсчёт O(n·u), почти O(n²). Counter(data) (или обычный dict) хеширует каждый элемент один раз за проход O(n), поэтому подсчёт падает с 40с до долей секунды.
- ✗Винить накладные расходы цикла, а не O(n)-пересканинг
- ✗Звать
list.countилиinна каждое уникальное значение - ✗Считать, что Counter выигрывает константу, а не класс сложности
- →Когда
list.countвнутри цикла всё же приемлем? - →Как
Counterведёт себя на нехешируемых элементах?
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.
