Четыре коллекции на каждый день

В прошлом уроке мы освоили строки и кодировки. Со строками вы можете прочитать любой файл. Но прочитанные данные нужно где-то держать — и держать так, чтобы быстро искать, фильтровать, дедуплицировать. Этим в Python занимаются четыре встроенные коллекции:

• list — упорядоченный изменяемый список. Аналог массива в Java/Go.
• tuple — упорядоченный неизменяемый кортеж. Похож на список, но без возможности менять.
• dict — словарь, отображение «ключ → значение». В других языках называется hash map.
• set — множество, неупорядоченное собрание уникальных элементов.

Этот квартет покроет 90% ваших структур данных. Изучаем их по порядку.

list — упорядоченный изменяемый список

list — самая универсальная и самая часто используемая коллекция. Хранит элементы в порядке вставки, элементы могут быть любого типа (включая разные типы в одном списке, но так лучше не делать без причины).

records: list[dict] = []

records.append({"id": 1, "name": "Анна"})
records.append({"id": 2, "name": "Борис"})

print(records[0])       # {'id': 1, 'name': 'Анна'}
print(len(records))     # 2

Type hint list[dict] — современный синтаксис из 3.9+. До этого писали List[Dict] с импортом из typing. Сейчас — не нужно.

Базовые операции

nums = [1, 2, 3]

# добавление
nums.append(4)              # в конец: [1, 2, 3, 4]
nums.insert(0, 0)           # по индексу: [0, 1, 2, 3, 4]
nums.extend([5, 6])         # докинуть несколько: [0, 1, 2, 3, 4, 5, 6]

# удаление
nums.remove(3)              # удалить первое вхождение значения
last = nums.pop()           # достать с конца, вернуть
first = nums.pop(0)         # достать с индекса 0

# индексация
print(nums[0])              # первый
print(nums[-1])             # последний
print(nums[1:3])            # срез [start:end) — элементы 1 и 2
print(nums[::2])            # каждый второй
print(nums[::-1])           # развёрнутый список

# проверка
print(3 in nums)            # True/False — линейный поиск (медленно для больших)
print(len(nums))            # длина

Срезы — главная фишка

xs = [10, 20, 30, 40, 50, 60, 70]

print(xs[2:5])      # [30, 40, 50]    — со 2 по 4 (5 не включается)
print(xs[:3])       # [10, 20, 30]    — первые три
print(xs[4:])       # [50, 60, 70]    — с 4 до конца
print(xs[-3:])      # [50, 60, 70]    — последние три
print(xs[::2])      # [10, 30, 50, 70] — шаг 2
print(xs[::-1])     # [70, 60, 50, ...] — развернуть

# срез возвращает копию, оригинал не меняется
copy = xs[:]

xs[:] — короткий способ сделать полную копию. Удобно, когда нужно передать функции данные, чтобы она их не изменила (помните про mutable defaults и побочные эффекты из урока 01).

Когда list медленный

list хранит элементы как массив указателей. Доступ по индексу — O(1), мгновенно. А вот поиск элемента x in xs — это

big_list = list(range(1_000_000))
print(999_999 in big_list)   # работает, но медленно

Когда нужны частые проверки «есть ли элемент» — берите set или dict. У них in — O(1).

tuple — упорядоченный неизменяемый

tuple похож на list, но без модификаций. Создаётся через круглые скобки:

point: tuple[int, int] = (3, 5)
print(point[0])     # 3

# point[0] = 10   <-- TypeError: 'tuple' object does not support item assignment

Зачем нужен, если есть list? Три причины:

1. Сигнал смысла. tuple часто используется для гетерогенных данных — фиксированной формы. Один кортеж — один объект, состоящий из нескольких частей разного типа:

# хорошо: tuple = «запись» из 3 разных полей
person: tuple[str, int, str] = ("Анна", 30, "RU")

# плохо для list, хорошо для tuple
db_row = (1, "Анна", "RU", 30, "2024-01-15")

В DE кортежи прилетают из БД именно так — каждая строка результата SELECT — это tuple значений.

2. Можно класть в ключи dict и в set. dict и set требуют, чтобы ключ/элемент был

seen = set()
seen.add(("Анна", 30))   # OK — tuple hashable
# seen.add(["Анна", 30])  <-- TypeError: unhashable type: 'list'

Это позволяет дедуплицировать составные записи через set (см. ниже).

3. Микро-оптимизация по памяти. tuple занимает чуть меньше, чем list. На миллионах объектов разница ощутима, но junior пока про это не думает.

Распаковка кортежей

Очень частый паттерн —

point = (3, 5)
x, y = point        # x = 3, y = 5

# то же для функции, возвращающей несколько значений
def divmod_v2(a: int, b: int) -> tuple[int, int]:
    return a // b, a % b   # вернёт tuple

quotient, remainder = divmod_v2(10, 3)
print(quotient, remainder)  # 3 1

# распаковка в цикле — гавная вещь
records = [("Анна", 30), ("Борис", 25)]
for name, age in records:
    print(f"{name}: {age}")

«Лишние» элементы можно собрать в звёздочку:

first, *rest = [1, 2, 3, 4, 5]
print(first)   # 1
print(rest)    # [2, 3, 4, 5]

dict — хеш-таблица, ваш главный инструмент

dict — это

user: dict[str, str | int] = {
    "id": 1,
    "name": "Анна",
    "country": "RU",
}

print(user["name"])         # "Анна"
print(user.get("email"))    # None — если ключа нет
print(user.get("email", "unknown"))  # "unknown" — дефолт

# добавление / обновление
user["email"] = "[email protected]"

# проверка ключа — быстро
if "email" in user:
    print(user["email"])

get vs прямой доступ

Принципиально важно:

user["unknown"]    # KeyError: 'unknown'  — Python падает
user.get("unknown")  # None — Python молчит
user.get("unknown", "fallback")  # "fallback"

Используйте [] когда уверены, что ключ есть (и хотите красиво упасть, если нет). Используйте .get() когда ключа может не быть. Распространённый антипаттерн:

# плохо: лишний lookup
if "email" in user:
    return user["email"]
else:
    return None

# хорошо
return user.get("email")

setdefault и update

# группировка: «у пользователя X собрать список заказов»
orders_by_user: dict[int, list] = {}

for order in all_orders:
    orders_by_user.setdefault(order["user_id"], []).append(order)

setdefault(key, default) — «вернуть значение по ключу, а если ключа нет — вставить default и вернуть его». Удобно для аккумуляции в словарь-список или словарь-set.

# слияние двух словарей
base = {"a": 1, "b": 2}
extra = {"b": 20, "c": 3}

base.update(extra)
print(base)     # {"a": 1, "b": 20, "c": 3}  — b перезаписан

# то же выражением, без мутации
merged = {**base, **extra}

Итерация по словарю

d = {"a": 1, "b": 2, "c": 3}

for key in d:            # ключи (то же, что d.keys())
    print(key)

for key, value in d.items():
    print(f"{key} = {value}")

for value in d.values():
    print(value)

С Python 3.7 порядок итерации = порядок вставки. Это гарантия языка, можно полагаться.

set — множество для дедупликации и быстрого поиска

set — неупорядоченное собрание уникальных значений. Хранит только сами значения (без «значение к ключу»), всё остальное похоже на dict.

seen: set[int] = set()
seen.add(1)
seen.add(2)
seen.add(1)        # дубль игнорируется

print(seen)        # {1, 2}
print(len(seen))   # 2
print(1 in seen)   # True

Создание из существующего списка — дедупликация в одну строку:

ids = [1, 2, 3, 1, 2, 4]
unique = set(ids)
print(unique)      # {1, 2, 3, 4}  — порядок не гарантирован!

# вернуть к list (если порядок важен — сначала set, потом sorted)
unique_list = sorted(set(ids))
print(unique_list)  # [1, 2, 3, 4]

Set-операции работают как в математике:

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)       # {1, 2, 3, 4, 5, 6}  — объединение (union)
print(a & b)       # {3, 4}              — пересечение (intersection)
print(a - b)       # {1, 2}              — разность
print(a ^ b)       # {1, 2, 5, 6}        — симметрическая разность

Это бесценно для DE. «Какие user_id есть в источнике, но нет в нашей БД?» — это source - existing. Одна строка.

frozenset — immutable set

Иногда нужен set, который можно положить ключом в dict (помните: ключ dict должен быть hashable). set — mutable, нельзя. frozenset — immutable, можно:

# словарь по «множеству признаков»
permissions = {
    frozenset({"read"}): "reader",
    frozenset({"read", "write"}): "editor",
    frozenset({"read", "write", "delete"}): "admin",
}

user_perms = frozenset({"read", "write"})
print(permissions[user_perms])   # "editor"

Редкий, но иногда красивый инструмент.

Сложность операций — что быстро, что нет

Это не abstract math, это ваша реальная скорость работы скриптов:

Главное правило DE: если делаете больше одной проверки in на коллекции — переведите её в set или dict. На 100 элементах разница невидна, на миллионе — это секунды vs минуты.

DE-кейсы

Кейс 1: дедупликация записей

# у нас 10 миллионов событий, нужно убрать дубли по (user_id, event_type)
events = [
    {"user_id": 1, "event_type": "click", "ts": "..."},
    {"user_id": 1, "event_type": "click", "ts": "..."},  # дубль
    {"user_id": 2, "event_type": "view", "ts": "..."},
]

seen: set[tuple[int, str]] = set()
unique = []

for e in events:
    key = (e["user_id"], e["event_type"])
    if key not in seen:
        seen.add(key)
        unique.append(e)

Здесь ключ — tuple, потому что в set нужен hashable.

Кейс 2: lookup-таблица

# у нас список заказов и список продуктов с ценами
# для каждого заказа нужно посчитать total

products = [
    {"id": 101, "name": "Кофе", "price": 250.0},
    {"id": 102, "name": "Чай", "price": 180.0},
]

orders = [
    {"product_id": 101, "qty": 2},
    {"product_id": 102, "qty": 1},
]

# наивно — медленно, O(N*M)
for order in orders:
    for p in products:
        if p["id"] == order["product_id"]:
            order["total"] = p["price"] * order["qty"]

# правильно — построить lookup-словарь, потом O(N)
price_by_id = {p["id"]: p["price"] for p in products}

for order in orders:
    order["total"] = price_by_id[order["product_id"]] * order["qty"]

На 10 000 заказов и 10 000 продуктов наивный подход — 100 миллионов сравнений. Lookup-словарь — 10 000 lookup’ов. Это в 10 000 раз быстрее. Базовая техника DE.

Упражнение

В REPL (uv run python) выполните:

# 1. Дедуплицируйте список и сохраните порядок появления:
xs = ["a", "b", "a", "c", "b", "d", "a"]
# Ожидаемое: ["a", "b", "c", "d"]

# 2. Постройте обратный индекс: из {1: "a", 2: "b"} получите {"a": 1, "b": 2}
forward = {1: "a", 2: "b", 3: "c"}

# 3. Найдите ключи, которые есть в obj1, но нет в obj2:
obj1 = {"a": 1, "b": 2, "c": 3}
obj2 = {"b": 20, "c": 30, "d": 40}
# Ожидаемое: {"a"}

# 4. У вас список словарей. Сгруппируйте по полю "country":
people = [
    {"name": "Анна", "country": "RU"},
    {"name": "Pierre", "country": "FR"},
    {"name": "Борис", "country": "RU"},
]
# Ожидаемое: {"RU": ["Анна", "Борис"], "FR": ["Pierre"]}

Критерии:

• Все четыре задачи решены без явного двойного цикла, кроме (1) — там понимание, как сохранить порядок.
• Используется правильная коллекция (set для дедупликации, dict для группировки).
• Вы можете объяснить, почему ваш код работает за O(n), а не O(n²).

В следующем уроке —