Сравнительная таблица: list/tuple/dict/set big-O и memory
Этот урок — single-page reference card по всему модулю M02. Если вы только что прочитали уроки 01-06, эта страница даёт comparative view: рядом четыре структуры, рядом их operations, рядом их big-O. Используйте перед экзаменом для self-assessment, и в production — как cheat-sheet.
Big-O matrix — ключевые operations
| Операция | list | tuple | dict | set | Комментарий |
|---|---|---|---|---|---|
len(x) | O(1) | O(1) | O(1) | O(1) | поле ob_size / ma_used / used |
indexing x[i] | O(1) | O(1) | n/a | n/a | direct array access (positional) |
key lookup x[k] | n/a | n/a | O(1) avg | n/a | hash + probe ~3 шага |
| append / add | amort O(1) | n/a | O(1) avg | O(1) avg | mutable only |
insert(0, x) | O(n) | n/a | n/a | n/a | shift всех elements |
x in container | O(n) | O(n) | O(1) avg | O(1) avg | hash для dict/set |
| iteration | O(n) | O(n) | O(n) | O(n) | sequential scan |
| pop end | O(1) | n/a | varies | n/a | decrement size |
| pop front | O(n) | n/a | varies | n/a | shift всех |
| sort | O(n log n) | n/a | n/a | n/a | Timsort adaptive |
| copy / shallow | O(n) | O(n) | O(n) | O(n) | new container + memcpy указателей |
union | | n/a | n/a | n/a | O(s + t) | iterate обе |
intersection & | n/a | n/a | n/a | O(min(s, t)) | iterate меньшую |
difference - | n/a | n/a | n/a | O(s) | iterate s, exclude если in t |
Worst case для O(1) avg: O(n) при коллизиях. Mitigation: hash randomization (str/bytes), uniform __hash__.
Memory snapshot (на cpython-3.12.7, 64-bit)
| Container | empty | 1 element | 10 elements |
|---|---|---|---|
list | 56 байт | 88 байт | 184 байт |
tuple | 40 байт | 48 байт | 120 байт |
dict | 64 байт | 184 байт | ~376 байт |
set | 216 байт | 216 байт (smalltable) | 216 байт (smalltable) |
frozenset | 216 байт | 216 байт | 216 байт |
(Точные значения см. scripts/python-course/pyodide-baseline.json.)
Наблюдения:
tupleсамый компактный (нет capacity headroom, нетallocatedполя): 40 + 8N байт точно.listимеет capacity headroom (geometric ~1.125x): 56 + 8 × allocated, не 8 × ob_size.dictтяжелее всех на small-end: 64 байт пустой dict, 184 байт после первого insert (PyDictKeysObject + dk_indices + dk_entries отдельно аллоцированы).setимеет встроенную smalltable размера 8 — для маленьких сетов не нужна отдельная malloc’нутая table; sys.getsizeof остаётся 216 байт до выхода из smalltable.
Decision matrix — что выбрать
| Use case | Choose | Why |
|---|---|---|
| Ordered mutable sequence | list | append amortized O(1); indexing O(1) |
| Fixed structured value (record) | tuple | hashable, immutable signal of structure, packed memory |
| Lookup by key | dict | O(1) avg key access |
| Membership / dedup | set | O(1) avg + set ops API |
| Hashable container (dict key, set element) | tuple / frozenset | hashability requires immutability |
| Numerical data, large | array.array / NumPy | no PyObject overhead per element |
| Front-ops mutable | collections.deque | O(1) appendleft/popleft |
| Counter / multiset | collections.Counter | dict subclass с increment-aware API |
| Default dict (auto-init) | collections.defaultdict | dict с factory для missing keys |
| Ordered set | n/a (use dict.fromkeys) | dict insertion order = ordered set |
Self-assessment перед экзаменом
Чек-лист (10 пунктов). Проверьте каждое утверждение для себя — если не уверены, перечитайте указанный урок:
- Я могу нарисовать
PyListObjectот руки — header, ob_item pointer, separately allocated массив указателей, capacity ≥ ob_size. (M02-01) - Я могу прочитать
lookdict()вObjects/dictobject.cи объяснить probe sequence:i = (5*i + 1 + perturb) & mask; perturb >>= PERTURB_SHIFT. (M02-03) - Я могу нарисовать compact dict layout (PEP 468):
dk_indices(sparse, 1/2/4-byte indices) +dk_entries(dense, insertion-ordered (hash, key, value) triples). (M02-04) - Я понимаю почему
tuplehashable, аlistнет — на уровне stable hash invariant: mutable объект, изменив content, ломает inverse-mapping в hash table. (M02-02, M02-06) - Я могу объяснить amortized O(1) append через aggregate analysis: total work = O(n) для n appends при geometric growth (1+1.125+…+n/(c-1)·c ≤ 9n при c=1.125). (M02-01)
- Я могу объяснить почему
'x' in [1M_items]плохо vsset: list — O(n) per check (linear scan), set — O(1) avg per check (hash + probe). Preprocess в set за O(n) one-time, потом O(1) per query. (M02-05) - Я знаю когда insertion order для dict стало language guarantee: Python 3.7. Python 3.6 — implementation detail (CPython, PyPy). (M02-04)
- Я могу объяснить почему immutable cache-friendlier: stable layout (no realloc, no rewrite), packed primitives возможны (NumPy ndarray), zero-copy между процессами (Arrow buffer). (M02-06)
- Я могу imple linear-probing dict из памяти: hash → slot, while занят чужим key → next slot, либо empty (not found) либо matching (hit). (M02-03 code challenge)
- Я понимаю как PEP 468 экономит ~30-65% памяти: разделение sparse
dk_indices(только индексы) + densedk_entries(только данные); раньше каждый slot — 24 байта(h, k, v)независимо занят или пуст. (M02-04)
Что в M03
Module 03 (functions / args/kwargs / comprehensions / functional tools) — менее memory-deep, больше idiomatic Python patterns:
- Function как PyFunctionObject, closures и cell variables
*args/**kwargsmechanics — tuple и dict packing- Comprehensions vs generator expressions (memory trade-off)
map/filter/reduceи functools (lru_cache, partial)- Decorators и descriptor protocol
После M03 у вас будет полная картина Python data + control model. M04+ — applied data engineering.