ЗАМЕР

bench/collections/build.py

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

Цитируется в статье

/ru/interview/python/builtin-collections

Как запустить

python3.11 bench/collections/basics.py
python3.12 bench/collections/basics.py
python3.13 bench/collections/basics.py
python3.14 bench/collections/basics.py

python3.13 bench/collections/cost.py
python3.14 bench/collections/cost.py

python3.11 bench/collections/hashable.py
python3.12 bench/collections/hashable.py
python3.13 bench/collections/hashable.py
python3.14 bench/collections/hashable.py

python3.13 bench/collections/build.py
python3.14 bench/collections/build.py

python3.11 bench/collections/practice.py
python3.12 bench/collections/practice.py
python3.13 bench/collections/practice.py
python3.14 bench/collections/practice.py

Запись прогона

Замеры для урока «Встроенные коллекции»

Скрипт	Что делает
`basics.py`	наблюдения без времени: дубли, хешируемость, порядок словаря и множества (множество строк при трёх разных `PYTHONHASHSEED`), размер контейнера на 1000 целых, сводка «что умеет каждый»
`cost.py`	цена `x in коллекция` на 10, 1 000 и 100 000 элементов и удаления из начала: `list.pop(0)` против `deque.popleft()`
`practice.py`	источник ответов двух практических задач урока
`hashable.py`	полный короткий пример урока: значение словаря может быть списком, ключ и элемент множества — нет
`build.py`	цена сценария «построить `set` из списка и проверить» против проверок по самому списку, 1 и 100 проверок

python3.11 bench/collections/basics.py
python3.12 bench/collections/basics.py
python3.13 bench/collections/basics.py
python3.14 bench/collections/basics.py

python3.13 bench/collections/cost.py
python3.14 bench/collections/cost.py

python3.11 bench/collections/hashable.py
python3.12 bench/collections/hashable.py
python3.13 bench/collections/hashable.py
python3.14 bench/collections/hashable.py

python3.13 bench/collections/build.py
python3.14 bench/collections/build.py

python3.11 bench/collections/practice.py
python3.12 bench/collections/practice.py
python3.13 bench/collections/practice.py
python3.14 bench/collections/practice.py

Записи в runs/: без суффикса — CPython 3.13.7, остальные — с суффиксом версии (3.11.15, 3.12.3, 3.14.7). Числа cost.py и build.py — этой машины (2 ядра; build.py, hashable.py и разделы 6 basics.py сняты 14.10.2026 на linux/x86_64). Отношения между формами — наблюдение этой конфигурации: они зависят от размера и вида данных, версии и машины, и на своей машине их надо мерить заново. CPython 3.15 (вышел 9 октября 2026) здесь не запускался.

Что получилось

Дубли. set оставляет разные элементы, dict.fromkeys — тоже, но в порядке первого появления; в литерале словаря с повторённым ключом побеждает последнее значение.

Хешируемость. Требование — к элементам множества и к ключам словаря, а не к значениям: {"items": []} создаётся, а {[]: "x"} и {[1, 2]} падают (hashable.py, на 3.11–3.14). Список и множество не могут быть ни элементом множества, ни ключом словаря; кортеж может, но только если хешируемо всё, что в нём: {(1, [2])} падает. frozenset — может. На 3.14 текст ошибки называет роль объекта: cannot use 'list' as a set element (…).

Порядок. Словарь хранит порядок вставки; удалённый и вставленный снова ключ уходит в конец. Множество из пяти строк при PYTHONHASHSEED = 1, 2, 3 напечаталось в трёх разных порядках — на всех четырёх версиях одинаково. Множество маленьких целых часто печатается по возрастанию, потому что hash(n) == n, но не всегда: {8, 1} печатается как {8, 1}.

Память на 1000 целых (сам контейнер, 3.13.7): list 8056 байт, tuple 8040, set 32984, dict 36952 — множество в 4,1 раза больше списка. На 3.14.7 кортеж — 8048.

x in коллекция, элемент последний (медианы, 3.13.7; в каждое число входит цикл — пустой стоит 18,7 нс на шаг): на 10 элементах список 119,5 нс против 35,2 у множества — но если элемент первый, список находит его за 33,7 нс. На 1 000 — 9 690 нс против 44,9 (в 216 раз), на 100 000 — около миллисекунды против 79,4 нс. У множества и ключей словаря время почти не зависит от размера.

Удаление из начала (50 000 удалений из 100 000, 3.13.7): list.pop(0) — 12 662 нс на удаление, deque.popleft() — 42,4, list.pop() с конца — 43,7.

Память и вид ключей (раздел 6, одинаково на 3.11–3.14): dict на 1000 ключей int — 36952 байта, на 1000 ключей str — 26032; set — 32984 в обоих случаях. Записи словаря со строковыми ключами в CPython хранятся без поля под хеш (PyDictUnicodeEntry в Include/internal/pycore_dict.h).

Построить множество ради проверки (build.py, медианы, 3.13.7, нс на сценарий): на 10 элементах одна проверка по списку — 98,8, set(lst) плюс одна проверка — 211,1; сто проверок — 8 499,6 против 1 962,7. На 1 000: одна проверка — 4 638,7 против 7 926,6, сто — 596 511,4 против 10 674,0. Ради одной проверки множество не окупилось, ради ста — окупилось.

Скрипт

64 строк

"""Цена построения множества ради проверки `x in`.

ЗАЧЕМ. cost.py меряет `x in` по готовым коллекциям: создание коллекции в
замер не входит. Но совет «проверяй по множеству» на практике часто
означает «построй множество из списка и проверь» — и тогда в цену входит
построение: хеш каждого элемента и вставка в таблицу. Здесь видно, при
каком числе проверок это окупается. Добавлено 14.10.2026 по внешнему
аудиту (PY-COL-02).

ЧТО МЕРЯЕТСЯ (нс на весь сценарий, размеры 10 и 1 000, искомый элемент
последний — худший случай для списка):

  k проверок по списку          — k раз `x in lst`;
  set(lst) + k проверок         — построить множество и k раз `x in st`;

для k = 1 и k = 100.

КАК. Формы меряются вперемежку, ROUNDS кругов; печатаются медианы.

Запускать: python3.13 / 3.14. Числа — этой машины; соотношения на другой
машине и версии надо мерить заново.
"""
import statistics
import sys
import time

print("PY", sys.version.split()[0])
print()

ROUNDS = 9
REPS = 2_000


def by_list(lst, target, k):
    t0 = time.perf_counter()
    for _ in range(REPS):
        for _ in range(k):
            target in lst
    return (time.perf_counter() - t0) / REPS


def build_then_set(lst, target, k):
    t0 = time.perf_counter()
    for _ in range(REPS):
        st = set(lst)
        for _ in range(k):
            target in st
    return (time.perf_counter() - t0) / REPS


print(f"построить set ради проверок: нс на сценарий, медианы {ROUNDS} кругов")
print(f"   {'размер':>7}{'проверок':>10}{'по списку':>12}{'set(lst) + проверки':>22}")
for size in (10, 1_000):
    lst = list(range(size))
    target = size - 1
    for k in (1, 100):
        forms = [("list", by_list), ("set", build_then_set)]
        samples = {name: [] for name, _ in forms}
        for _ in range(ROUNDS):
            for name, fn in forms:
                samples[name].append(fn(lst, target, k) * 1e9)
        med = {name: statistics.median(xs) for name, xs in samples.items()}
        print(f"   {size:>7}{k:>10}{med['list']:>12.1f}{med['set']:>22.1f}")