Коллекции: списки, словари, множества, кортежи и их устройство

Базовый синтаксис коллекций разобран в курсе «Программирование с нуля» — если for x in xs и d["ключ"] пока не рефлекс, начните с Коллекции данных и вернитесь сюда. Здесь другая задача: понять, что физически происходит в памяти, когда вы пишете xs.append(v) или d[k] = v, и почему из-за этого одна и та же по смыслу программа может работать 0.2 секунды или 40 минут.

Профессиональный выбор коллекции — это не «что красивее выглядит». Это ответ на три вопроса:

1. Какой паттерн доступа? Индекс, ключ, «есть ли элемент», «минимальный элемент», «оба конца»?
2. Что меняется, а что нет? Изменяемость решает, можно ли объект хешировать, шарить между потоками и безопасно передавать наружу.
3. Сколько элементов и какого размера? На тысяче элементов разницы нет. На десяти миллионах — разница между ноутбуком и кластером.

В https://courses.digitable.life/post/python/02-data-model/ мы установили ключевой факт: переменная в Python — это имя, привязанное к объекту, а не ячейка со значением. Всё поведение коллекций — прямое следствие этого. Коллекция хранит не значения, а ссылки.

Карта абстракций: collections.abc

Прежде чем лезть в реализацию, полезно увидеть словарь понятий. В Python «быть последовательностью» — это не класс, а набор поддерживаемых протоколов, формализованный в collections.abc.

Практический вывод из этой схемы: в сигнатурах функций объявляйте минимальный нужный протокол, а не конкретный класс.

from collections.abc import Iterable, Sequence, Mapping

def total(prices: Iterable[float]) -> float:
    """Нужен только обход — принимаем всё итерируемое: список, генератор, ключи dict."""
    return sum(prices)

def median(values: Sequence[float]) -> float:
    """Нужны len и индексация — Sequence, но не Iterable (генератор сломался бы)."""
    ordered = sorted(values)
    mid = len(ordered) // 2
    return ordered[mid] if len(ordered) % 2 else (ordered[mid - 1] + ordered[mid]) / 2

Тонкость, о которую спотыкаются все: str — это тоже Sequence и Iterable. Функция «разверни вложенные списки» на строке уйдёт в бесконечную рекурсию, потому что итерация строки даёт строки длины 1, которые снова итерируемы. Проверяйте isinstance(x, str) отдельно и первым.

list: массив указателей с запасом

list — это динамический массив ссылок, а не связный список (несмотря на имя). Структура PyListObject хранит заголовок, длину, ёмкость и указатель на отдельно выделенный блок памяти с указателями на элементы.

Рост и амортизация

Когда места в блоке не осталось, CPython выделяет новый блок с запасом и копирует туда указатели. Формула в Objects/listobject.c даёт коэффициент роста примерно 1.125:

/* CPython, list_resize() — фрагмент */
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Ёмкость идёт по ряду 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 112, 134, 160, 190, ... Проверить это можно самому — и это лучшая привычка при изучении внутренностей: не верить статьям, а измерять.

import sys

# Смотрим, в какие моменты меняется ёмкость списка.
prev, xs = None, []
for i in range(130):
    size = sys.getsizeof(xs)
    if size != prev:
        # (56 — размер заголовка на 64-битном CPython) // 8 байт на указатель
        print(f"len={i:>4}  ёмкость≈{(size - 56) // 8}")
        prev = size
    xs.append(i)
# len=   0  ёмкость≈0
# len=   1  ёмкость≈4
# len=   5  ёмкость≈8
# len=   9  ёмкость≈16
# len=  17  ёмкость≈24
# ... (числа зависят от версии CPython и разрядности)

Коэффициент 1.125 — компромисс: экономия памяти против количества копирований. Поскольку рост геометрический, append стоит O(1) амортизированно: суммарно на N вставок приходится O(N) работы по копированию.

Если размер известен заранее, копирований можно избежать вовсе — но не через «преаллокацию» вручную, а через конструкции, которые сообщают интерпретатору длину:

# Плохо: N перевыделений (хотя амортизированно и дёшево)
result = []
for x in source:
    result.append(f(x))

# Лучше: list-comprehension. Байткод использует специальную инструкцию LIST_APPEND,
# без поиска атрибута .append на каждой итерации — обычно на 30–50% быстрее.
result = [f(x) for x in source]

# Ещё лучше, если source имеет __len__: list() умеет спросить длину и выделить сразу.
result = list(map(f, source))

Стоимость операций

Звёздочка у append важна: O(1) — это средняя стоимость. Отдельный append, попавший на границу ёмкости, скопирует весь массив. Для систем с жёсткими требованиями к хвостовым задержкам это заметно.

Срезы, копии и алиасинг

Срез создаёт новый список со ссылками на те же объекты — это shallow copy.

matrix = [[0, 0], [0, 0]]
shallow = matrix[:]          # или list(matrix), или copy.copy(matrix)
shallow[0].append(9)
print(matrix)                # [[0, 0, 9], [0, 0]] — внутренние списки общие!

import copy
deep = copy.deepcopy(matrix) # рекурсивная копия, корректно обрабатывает циклы через memo

Присваивание срезу — недооценённая операция: она меняет список на месте, в том числе меняя его длину.

xs = [1, 2, 3, 4, 5]
xs[1:4] = ["a"]        # заменили три элемента одним
print(xs)              # [1, 'a', 5]
xs[:0] = [0]           # вставка в начало без insert
print(xs)              # [0, 1, 'a', 5]
xs[::2] = ["x", "y"]   # расширенный срез требует ТОЧНОГО совпадения длин
print(xs)              # ['x', 1, 'y', 5]

Это важно, когда список — общее состояние: xs[:] = new_values обновит его для всех, кто держит ссылку, а xs = new_values — только локальное имя.

Классическая ловушка: [[]] * n

grid = [[0] * 3] * 3      # ВЫГЛЯДИТ как матрица 3×3
grid[0][0] = 1
print(grid)               # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] — одна строка, три ссылки!

grid = [[0] * 3 for _ in range(3)]  # правильно: три РАЗНЫХ списка
grid[0][0] = 1
print(grid)               # [[1, 0, 0], [0, 0, 0], [0, 0, 0]]

Оператор * копирует ссылки, а не объекты. Для [0] * 3 это безопасно (int неизменяем), для [[]] * 3 — катастрофа. Ровно та же природа у изменяемого аргумента по умолчанию — разберём в https://courses.digitable.life/post/python/04-functions-and-scopes/.

tuple: не «неизменяемый список», а запись

Технически tuple хранит указатели внутри самого объекта, без отдельного блока и без запаса ёмкости. Отсюда меньший размер (пустой кортеж ≈ 40 байт против ≈ 56 у пустого списка на 64-битном CPython) и чуть более быстрое создание — CPython держит freelist для коротких кортежей.

Но главное отличие семантическое, и оно определяет идиоматику:

• список — однородная последовательность переменной длины: «заказы», «строки файла». Тип: list[Order].
• кортеж — гетерогенная запись фиксированной длины, где позиция несёт смысл: (широта, долгота), (имя, возраст). Тип: tuple[float, float].

Если вы пишете tuple[int, ...] (переменная длина), почти всегда вам нужен либо list, либо Sequence. Подробнее о записи типов — в https://courses.digitable.life/post/python/07-typing/.

from typing import NamedTuple

# Позиционный кортеж читается плохо: что такое p[2]?
point = (55.75, 37.62, "Москва")

# NamedTuple — тот же кортеж (быстрый, неизменяемый, хешируемый), но с именами и типами.
class City(NamedTuple):
    lat: float
    lon: float
    name: str

c = City(55.75, 37.62, "Москва")
print(c.name, c[2], isinstance(c, tuple))   # Москва Москва True
print(c._replace(name="Moscow"))            # City(lat=55.75, lon=37.62, name='Moscow')

Неизменяемость поверхностна

Кортеж гарантирует только то, что набор ссылок не изменится. Объекты по этим ссылкам могут меняться сколько угодно:

t = ([], "x")
t[0].append(1)
print(t)                 # ([1], 'x') — кортеж «изменился»

print(hash(("a", "b")))  # ок
print(hash(([], "x")))   # TypeError: unhashable type: 'list'

Хешируемость кортежа вычисляется из хешей элементов — поэтому кортеж со списком внутри не может быть ключом словаря. Это правильно: иначе ключ «уезжал» бы из своей корзины при мутации.

Грабля года: t[0] += [1]

t = ([], "x")
t[0] += [1]
# TypeError: 'tuple' object does not support item assignment
print(t)   # ([1], 'x')  — И ОШИБКА, И ИЗМЕНЕНИЕ ОДНОВРЕМЕННО

Почему так: t[0] += [1] компилируется в «взять t[0], вызвать __iadd__ (список меняет себя на месте и возвращает себя), положить результат обратно в t[0]». Первый шаг успевает выполниться, второй падает. Мораль: не используйте += на элементах кортежа. Если очень нужно — t[0].extend([1]).

Мелочи, которые ломают код

x = (1)      # это int 1, а не кортеж — скобки здесь группирующие
x = (1,)     # вот это кортеж
x = 1,       # и это тоже кортеж — запятая, а не скобки, создаёт кортеж

def f(a): ...
f((1, 2))    # один аргумент-кортеж
f(*(1, 2))   # два аргумента

# Распаковка со звёздочкой (PEP 3132) — идиоматичный способ резать последовательности
first, *middle, last = [1, 2, 3, 4, 5]
print(first, middle, last)   # 1 [2, 3, 4] 5

dict: компактная хеш-таблица

Словарь — самая важная и самая оптимизированная структура в языке. На нём построены пространства имён модулей, __dict__ объектов, **kwargs, кеши, разбор JSON. Оптимизации dict — это оптимизации всего Python.

С версии 3.6 (как деталь реализации) и с 3.7 (как гарантия языка) словарь сохраняет порядок вставки. Это не «побочный эффект», а следствие перехода на компактное представление, предложенное Реймондом Хеттингером (письмо в python-dev, 2012): вместо одного разреженного массива «слотов записи» используются два массива — маленький разреженный индекс и плотный массив записей.

Экономия существенная: раньше на 2/3-заполненную таблицу нужно было держать 3 указателя × capacity (hash, key, value), теперь — 1 байт × capacity (при малых размерах) плюс 3 указателя × count. Типичный выигрыш по памяти — 20–25%, плюс итерация стала линейным проходом по плотному массиву вместо перебора дырок.

Как выполняется поиск

Три уровня отсева важны для понимания стоимости:

1. Сравнение указателей (is). Для интернированных строк — а это все идентификаторы и большинство строковых литералов — совпадение находится здесь, без единого сравнения символов.
2. Сравнение хешей (машинное слово). Отсеивает почти все коллизии по индексу.
3. Полное ==. Вызывается редко, но именно поэтому дорогой __eq__ в ключах — почти всегда невидимая проблема, пока таблица не разрастётся.

Пробирование в CPython — не линейное и не квадратичное: i = (5*i + perturb + 1) & mask с perturb >>= 5. Пока perturb не обнулился, в адрес втягиваются старшие биты хеша; после — последовательность гарантированно обходит все слоты. Это даёт хорошее рассеивание без плохих кластеров, характерных для наивного линейного пробирования.

Ресайз и жизненный цикл слота

Таблица растёт, когда заполнено больше 2/3. Новый размер — ближайшая степень двойки не меньше used * 3. Обратите внимание: при ресайзе размер считается от числа живых записей, поэтому словарь, из которого много удаляли, при следующем ресайзе действительно сожмётся.

Состояние DUMMY («надгробие») объясняет неочевидный факт: словарь, в который много вставляли и из которого много удаляли, может деградировать по скорости поиска, пока не случится ресайз. В долгоживущих кешах, где ключи постоянно приходят и уходят, полезно периодически пересоздавать словарь (d = dict(d)) — либо взять специализированную структуру вроде functools.lru_cache или cachetools.

Key-sharing: почему у объектов дешёвый __dict__

PEP 412 добавил разделяемые ключи: все экземпляры одного класса используют общий массив ключей, храня только массив значений. Именно поэтому создание миллиона объектов с одинаковым набором атрибутов не стоит миллиона хеш-таблиц. В CPython 3.11+ значения экземпляра и вовсе лежат «инлайн» рядом с объектом. Полностью убрать __dict__ можно через __slots__ — см. https://courses.digitable.life/post/python/05-oop/.

Контракт хеша и что его нарушает

Правила, за которые отвечаете вы:

• если a == b, то обязательно hash(a) == hash(b);
• хеш объекта не должен меняться за его жизнь;
• обратное неверно: равные хеши не означают равные объекты.

# Классика: bool — подкласс int, а 1 == 1.0 == True
d = {1: "int", True: "bool", 1.0: "float"}
print(d)            # {1: 'float'} — один ключ; ПЕРВЫЙ ключ остаётся, ЗНАЧЕНИЕ перезаписывается
print(d[True])      # float

# Хеш строк рандомизирован между запусками процесса (PEP 456, защита от hash-DoS)
# $ python3 -c "print(hash('a'))"   → каждый раз разное
# $ PYTHONHASHSEED=0 python3 -c "print(hash('a'))"  → воспроизводимо
# Отсюда правило: НИКОГДА не полагайтесь на порядок set и не сохраняйте hash() на диск.

# NaN нарушает рефлексивность равенства
nan = float("nan")
print(nan == nan)          # False
print(nan in [nan])        # True — контейнеры сначала сравнивают по is
print(len({float("nan"), float("nan")}))   # 2 — разные объекты, оба попали в множество

Про hash(-1) == -2 в CPython: значение −1 зарезервировано под «ошибка вычисления хеша» на уровне C API, поэтому его подменяют. Мелочь, но она периодически всплывает в самописных __hash__.

Представления, а не копии

keys(), values(), items() возвращают живые представления (PEP 3106). Они не копируют данные и отражают изменения словаря.

d = {"a": 1, "b": 2}
keys = d.keys()
d["c"] = 3
print(list(keys))              # ['a', 'b', 'c'] — представление живое

# keys() и items() ведут себя как множества
other = {"b": 20, "z": 26}
print(d.keys() & other.keys())  # {'b'}  — пересечение ключей
print(d.keys() - other.keys())  # {'a', 'c'}
print(d.items() & other.items())# set() — по (ключ, значение) совпадений нет
# values() множеством НЕ является: значения не обязаны быть хешируемыми и уникальными

for k in d:                     # изменение размера во время итерации — RuntimeError
    if k == "a":
        del d[k]
# RuntimeError: dictionary changed size during iteration
# Правильно: for k in list(d): ...   (снимок ключей)

Идиомы и подводные камни dict

from collections import defaultdict, Counter, ChainMap

# 1. setdefault vs defaultdict
groups = {}
for user in users:
    groups.setdefault(user.city, []).append(user)   # список создаётся на КАЖДОЙ итерации

groups = defaultdict(list)
for user in users:
    groups[user.city].append(user)                   # быстрее и читаемее

# Грабля defaultdict: ЧТЕНИЕ создаёт ключ
counts = defaultdict(int)
if counts["не было"] == 0:
    pass
print(dict(counts))     # {'не было': 0} — ключ появился!
# Для проверки используйте .get(k, 0) или k in counts

# 2. fromkeys с изменяемым значением — общий объект на все ключи
d = dict.fromkeys(["a", "b"], [])
d["a"].append(1)
print(d)                # {'a': [1], 'b': [1]} — тот же список

# 3. fromkeys БЕЗ значения — лучший способ дедупликации с сохранением порядка
uniq = list(dict.fromkeys([3, 1, 3, 2, 1]))
print(uniq)             # [3, 1, 2]  (set() порядок бы потерял)

# 4. Counter — не просто счётчик
c = Counter("абракадабра")
print(c.most_common(2))         # [('а', 5), ('б', 2)]
print(c - Counter("абра"))      # вычитание отбрасывает неположительные

# 5. Слияние (PEP 584, Python 3.9+)
defaults = {"retries": 3, "timeout": 5}
config = defaults | {"timeout": 30}       # новый словарь
defaults |= {"debug": True}               # на месте

# 6. ChainMap — приоритетный поиск БЕЗ копирования словарей
settings = ChainMap(cli_args, env_vars, file_config, defaults)
print(settings["timeout"])   # первый словарь, где ключ найден

Про OrderedDict: обычный dict сохраняет порядок, но OrderedDict всё ещё нужен там, где порядок — часть семантики: у него __eq__ учитывает порядок, есть move_to_end() и popitem(last=False). Классический LRU-кеш на OrderedDict — это ровно эти два метода.

set и frozenset: хеш-таблица без значений

Множество — та же хеш-таблица, но хранит только ключи, и оптимизирована под другой профиль нагрузки. Отличия от dict в Objects/setobject.c существенные:

• Разреженная таблица, а не компактная. Порядок вставки не сохраняется и не гарантируется.
• Ресайз при заполнении ≈3/5 (а не 2/3), рост в 4 раза для маленьких множеств и в 2 раза для больших (порог — 50 000 элементов). Множества готовы жертвовать памятью ради скорости проверки принадлежности.
• Перед «прыжковым» пробированием пробуются 9 соседних слотов подряд (LINEAR_PROBES) — расчёт на кеш-линию процессора: соседние слоты уже в кеше.

seen = set()
seen.add("x")
print("x" in seen)          # O(1) вместо O(n) у списка

# Литерал {} — это ПУСТОЙ СЛОВАРЬ. Пустое множество только так:
empty = set()
print(type({}), type(set()))   # <class 'dict'> <class 'set'>

# Операторы требуют СЛОВО set с обеих сторон, методы — любой iterable
a = {1, 2, 3}
# a & [2, 3]              → TypeError: unsupported operand type(s)
print(a.intersection([2, 3]))       # {2, 3} — работает
print(a.issuperset(x for x in [1]))  # True — и с генератором тоже

# frozenset хешируем — годится в ключи и в элементы других множеств
roles = {frozenset({"admin", "audit"}): "полный доступ"}

Сложность операций над множествами (n = len(s), m = len(t)):

Практический приём: замена in list на in set — самая частая и самая дешёвая оптимизация в Python-коде.

# O(n·m) — на 10 000 × 10 000 это ~100 млн сравнений, десятки секунд
banned_list = load_banned()          # list[str]
clean = [u for u in users if u.email not in banned_list]

# O(n + m) — доли секунды
banned = set(load_banned())
clean = [u for u in users if u.email not in banned]

Как выбрать структуру

Специализированные коллекции стандартной библиотеки

collections.deque — очередь с двух концов

Реализована как двусвязный список блоков по 64 указателя. append/popleft — O(1) на любом конце. Плата: индексация в середину — O(n).

from collections import deque

# Скользящее окно длиной 3: maxlen сам выталкивает старые элементы
window = deque(maxlen=3)
for value in [1, 2, 3, 4, 5]:
    window.append(value)
print(list(window))       # [3, 4, 5]

# Очередь задач: list.pop(0) — O(n), deque.popleft() — O(1)
q = deque(["a", "b"])
q.appendleft("start")
print(q.popleft())        # start
q.rotate(1)               # циклический сдвиг, O(k)

Для BFS по графу с миллионом вершин разница между list.pop(0) и deque.popleft() — это разница между O(V²) и O(V). См. https://courses.digitable.life/post/algorithms/08-graph-traversal/ и https://courses.digitable.life/post/data-structures/04-stacks-queues-deques/.

heapq — приоритетная очередь на обычном списке

import heapq

tasks = []
heapq.heappush(tasks, (2, "починить билд"))     # (приоритет, задача)
heapq.heappush(tasks, (1, "прод лежит"))
heapq.heappush(tasks, (3, "обновить доки"))
print(heapq.heappop(tasks))                     # (1, 'прод лежит')  — O(log n)

data = [5, 1, 9, 3]
heapq.heapify(data)                             # O(n), на месте
print(heapq.nsmallest(2, data))                 # [1, 3] — эффективнее sorted()[:2] при k << n

Два нюанса. Первый: heapq — min-heap, для max-heap кладите отрицательные приоритеты. Второй: если приоритеты совпадают, Python начнёт сравнивать второй элемент кортежа — и упадёт, если это несравнимый объект. Идиома: (priority, counter, payload), где counter — монотонный itertools.count().

bisect — поиск и вставка в отсортированный список

import bisect

grades = [(60, "D"), (70, "C"), (80, "B"), (90, "A")]
thresholds = [g[0] for g in grades]

def grade(score: int) -> str:
    """Бинарный поиск границы: O(log n) вместо цепочки if."""
    i = bisect.bisect_right(thresholds, score) - 1
    return grades[i][1] if i >= 0 else "F"

print(grade(85))     # B

bisect.insort находит место за O(log n), но вставляет за O(n) из-за сдвига. На практике memmove настолько быстр, что до десятков тысяч элементов это выигрывает у «правильных» деревьев. Для больших объёмов — библиотека sortedcontainers.

Когда объекты Python слишком дороги

import array, sys

# Список из миллиона int: 8 МБ указателей + сами объекты по 28 байт
py_list = list(range(1_000_000))
# array.array('q') — 8 байт на значение, БЕЗ объектов-обёрток
arr = array.array("q", range(1_000_000))
print(sys.getsizeof(py_list), sys.getsizeof(arr))
# ≈ 8_000_056   ≈ 8_000_064  — но у списка ещё ~28 МБ на объекты int вне кеша малых чисел

# memoryview — срез БЕЗ копирования, критично для сетевых буферов и парсеров
buf = bytearray(b"HTTP/1.1 200 OK\r\n\r\nbody")
view = memoryview(buf)
header = view[:17]         # копии нет
print(bytes(header))       # b'HTTP/1.1 200 OK\r\n'

Для числовых массивов дальше начинается numpy — единый непрерывный блок типизированной памяти, векторные операции и отсутствие интерпретаторного цикла. Это тема https://courses.digitable.life/post/python/14-data-stack/; про кеш-линии и локальность — https://courses.digitable.life/post/performance/05-cache-and-locality/.

Сортировка и группировка

list.sort() и sorted() используют Timsort — адаптивный устойчивый алгоритм, который эксплуатирует уже упорядоченные «прогоны» в данных. С CPython 3.11 политика слияния прогонов заменена на powersort, что улучшило поведение на частично упорядоченных данных. Читать: Objects/listsort.txt, теория — https://courses.digitable.life/post/algorithms/02-sorting/.

from operator import attrgetter, itemgetter
from collections import defaultdict
from itertools import groupby

orders = [
    {"user": "ann", "sum": 300}, {"user": "bob", "sum": 100},
    {"user": "ann", "sum": 50},  {"user": "cid", "sum": 100},
]

# key вычисляется РОВНО ОДИН РАЗ на элемент (внутри — decorate-sort-undecorate).
# itemgetter/attrgetter — реализация на C, ощутимо быстрее лямбды.
by_sum = sorted(orders, key=itemgetter("sum"), reverse=True)

# Многоуровневая сортировка: за счёт УСТОЙЧИВОСТИ можно сортировать в несколько проходов,
# начиная с наименее значимого ключа — работает и для разных направлений.
rows = sorted(orders, key=itemgetter("user"))          # вторичный ключ
rows = sorted(rows, key=itemgetter("sum"), reverse=True)  # первичный ключ

# Группировка: defaultdict работает за O(n) и НЕ требует сортировки
grouped = defaultdict(list)
for o in orders:
    grouped[o["user"]].append(o)

# itertools.groupby группирует только ПОДРЯД идущие элементы — без сортировки даст мусор
for user, items in groupby(sorted(orders, key=itemgetter("user")), key=itemgetter("user")):
    print(user, sum(i["sum"] for i in items))
# ann 350
# bob 100
# cid 100

Три грабли сортировки: xs.sort() возвращает None (сортирует на месте) — y = xs.sort() даёт None; параметра cmp нет с Python 3, для функции-компаратора нужен functools.cmp_to_key; сортировка разнородных типов падает с TypeError, а не даёт «какой-нибудь» порядок — и это хорошо.

Каталог граблей: сводка

# 1. Изменение списка во время итерации — элементы молча пропускаются
xs = [1, 2, 2, 3]
for x in xs:
    if x == 2:
        xs.remove(x)
print(xs)          # [1, 2, 3] — одна двойка выжила!
# Правильно: xs[:] = [x for x in xs if x != 2]

# 2. Изменение словаря/множества во время итерации — RuntimeError (лучше, чем тишина)
# Правильно: for k in list(d): ...

# 3. b = a — это НЕ копия
a = [1, 2]; b = a; b.append(3)
print(a)           # [1, 2, 3]

# 4. `in` для словаря проверяет КЛЮЧИ, не значения
d = {"a": 1}
print(1 in d, "a" in d, 1 in d.values())   # False True True

# 5. Список как множество → O(n²) на ровном месте (см. раздел про set)

# 6. sum() для склейки списков — квадратичен
# sum([[1], [2], [3]], [])  → работает, но копирует всё на каждом шаге
from itertools import chain
print(list(chain.from_iterable([[1], [2], [3]])))   # [1, 2, 3] — O(n)

# 7. Склейка строк в цикле s += x — в общем случае O(n²)
parts = ["a", "b", "c"]
s = "".join(parts)          # единственно правильный способ

# 8. Ключ-объект с изменяемым состоянием: положили в dict, поменяли поле,
#    участвующее в __hash__ → ключ «потерялся» и найти его больше нельзя.
#    Правило: ключи словаря должны быть неизменяемыми (str, int, tuple, frozenset, enum).

# 9. Сравнение через == для больших коллекций — O(n) с вызовом __eq__ на элементах.
#    В горячем цикле это часто и есть узкое место, а не «медленный Python».

Практика: типичная задача на коллекции

Задача: есть поток событий и справочник пользователей; нужно посчитать выручку по городам и найти топ-3, не загружая всё в память дважды.

from collections import Counter, defaultdict
from typing import Iterable, Iterator, NamedTuple

class Event(NamedTuple):
    user_id: int
    amount: int

def revenue_by_city(
    events: Iterable[Event],
    user_city: dict[int, str],          # справочник: O(1) поиск
) -> Counter[str]:
    """Один проход по событиям, O(n) по времени, O(городов) по памяти."""
    revenue: Counter[str] = Counter()
    unknown = 0
    for ev in events:
        city = user_city.get(ev.user_id)   # .get вместо try/except: промах ожидаем
        if city is None:
            unknown += 1
            continue
        revenue[city] += ev.amount
    if unknown:
        print(f"пропущено событий без города: {unknown}")
    return revenue

users = {1: "Москва", 2: "Казань", 3: "Москва"}
events = [Event(1, 100), Event(2, 300), Event(3, 50), Event(9, 999)]
rev = revenue_by_city(events, users)
print(rev.most_common(3))     # [('Москва', 150), ('Казань', 300)] → отсортировано по сумме
# пропущено событий без города: 1

Что здесь важно с точки зрения коллекций: справочник — dict (O(1) вместо линейного поиска по списку); аккумулятор — Counter (готовый most_common на heapq вместо ручной сортировки); events принимается как Iterable, поэтому функция одинаково работает и со списком, и с генератором, читающим файл построчно — память не растёт. Генераторы и ленивые пайплайны — тема https://courses.digitable.life/post/python/06-pythonic-idioms/.

Честно: где Python проигрывает

Коллекции Python исключительно удобны и достаточно быстры для «клея», веба и аналитики. Но есть жёсткие границы:

• Нет типизированных контейнеров в рантайме. list[int] — подсказка для mypy, а не гарантия памяти. Физически это по-прежнему массив указателей на объекты int по 28 байт. В Go []int64 — непрерывный блок по 8 байт (см. https://courses.digitable.life/post/golang/02-fundamentals/), в Java есть int[], в Rust — Vec<i64>. Python компенсирует это внешними библиотеками (array, numpy), а не языком.
• Плохая локальность. Обход списка — прыжки по куче за каждым объектом. На больших объёмах узкое место — промахи кеша, а не интерпретатор.
• Накладные расходы на объект. Пустой dict — около 64 байт, пустой set — около 216, каждый int — 28. Миллион маленьких словарей съест сотни мегабайт: используйте dataclass(slots=True), NamedTuple или колоночное представление.
• Нет неизменяемых персистентных коллекций из коробки. frozenset и tuple — это заморозка, а не персистентные структуры с дешёвым «обновлением». Сравните с Elixir/Clojure, где persistent map — базовый тип; в Python это сторонние библиотеки (pyrsistent, immutables).
• Потокобезопасность иллюзорна. Отдельные операции над dict/list атомарны благодаря GIL, но d[k] = d[k] + 1 — не атомарна. Не стройте на этом синхронизацию; см. https://courses.digitable.life/post/python/11-concurrency/.

И честно про сильную сторону: dict в CPython — одна из самых оптимизированных хеш-таблиц в индустрии, вылизанная за тридцать лет. Пока ваши данные помещаются в память и вы не в горячем численном цикле, «переписать на структурах пониже» почти никогда не окупается — окупается заменить O(n²) на O(n).

Мини-итог

• list — динамический массив ссылок с геометрическим ростом: индекс и хвост дёшевы, голова и in — O(n).
• tuple — фиксированная запись, компактнее списка, хешируема если хешируемы элементы; неизменяемость поверхностная.
• dict — компактная хеш-таблица: разреженный индекс + плотный массив записей, отсюда порядок вставки и экономия памяти; поиск отсеивает кандидатов по is, потом по хешу, потом по ==.
• set — хеш-таблица без значений, более разреженная ради скорости; порядок не гарантирован никогда.
• Выбор структуры = паттерн доступа × изменяемость × масштаб. Ошибка масштаба (in list вместо in set) стоит на порядки больше, чем любая микрооптимизация.
• Уровнем ниже ждут deque, heapq, bisect, array, memoryview; ещё ниже — numpy.

Источники

• The Python Tutorial: Data Structures — официальное введение.
• Built-in Types — исчерпывающий справочник по list, tuple, dict, set.
• collections и collections.abc — специализированные контейнеры и протоколы.
• TimeComplexity — Python Wiki — таблица сложностей операций CPython.
• Исходники: listobject.c, dictobject.c, setobject.c, listsort.txt.
• PEP 412 — Key-Sharing Dictionary, PEP 456 — Secure and Interchangeable Hash Algorithm, PEP 584 — Add Union Operators To dict.
• Luciano Ramalho, «Fluent Python», 2nd ed. — главы 2–3 остаются лучшим разбором коллекций.
• Micha Gorelick, Ian Ozsvald, «High Performance Python», 2nd ed. — глава 4 про списки, словари и стоимость памяти.
• Anthony Shaw, «CPython Internals» — как читать исходники интерпретатора.
• Теория, не привязанная к языку: https://courses.digitable.life/post/data-structures/05-hash-tables/ и https://courses.digitable.life/post/data-structures/01-complexity-and-memory/.

Что дальше

Мы разобрали, где живут данные. Дальше — как живёт код, который их обрабатывает: пространства имён, замыкания, декораторы и знаменитая ловушка изменяемого аргумента по умолчанию, корни которой мы уже нащупали в этой статье.

Функции, области видимости, замыкания, декораторы