MEASUREMENT

bench/complexity/strkeys.py

The script that produced the numbers in the article, and the record of the run. The file is read from the repository at build time — this is the code that was run, not a copy of it.

Cited in

/en/interview/python/complexity

How to run it

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

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

python3.13 bench/complexity/strkeys.py
python3.14 bench/complexity/strkeys.py

python3.11 bench/complexity/find.py
python3.12 bench/complexity/find.py
python3.13 bench/complexity/find.py
python3.14 bench/complexity/find.py

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

The run below is recorded in Russian. It is a lab record, kept in the language it was written in; the numbers, the tables and the code read the same either way.

Record of the run

Замеры для урока «Сложность операций»

Скрипт	Что делает
`basics.py`	счёт без времени: сколько сравнений делают `x in list`, `x in set` и `bisect`; сколько раз список перевыделяет память на `append`; сколько сравнений у `[x for x in a if x in b]` со списком и множеством; сколько сравнений у `sorted()` на случайных, отсортированных и обратных данных; поиск в словаре, где у всех ключей один хеш
`cost.py`	время на операцию при n = 1 000, 10 000 и 100 000: `append`, `insert(0, x)`, `x in list`, `x in set`, `sorted()` на элемент
`practice.py`	источник ответов двух практических задач урока
`strkeys.py`	цена `hash` и `==` у строк длиной 10, 1 000 и 100 000 символов
`find.py`	полный короткий пример урока: `bisect_left` даёт позицию вставки, «найден ли» — отдельная проверка

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

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

python3.13 bench/complexity/strkeys.py
python3.14 bench/complexity/strkeys.py

python3.11 bench/complexity/find.py
python3.12 bench/complexity/find.py
python3.13 bench/complexity/find.py
python3.14 bench/complexity/find.py

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

Записи в runs/: без суффикса — CPython 3.13.7, остальные — с суффиксом версии (3.11.15, 3.12.3, 3.14.7). Сравнения считают сами элементы — объекты, у которых __eq__ и __lt__ увеличивают счётчик; искомый элемент — новый объект, равный последнему, иначе Python узнал бы его по тождеству. Счёт сравнений — наблюдение CPython для этих объектов, а не контракт языка: при коллизиях хешей он другой (раздел 6). Числа cost.py и strkeys.py — этой машины (2 ядра; разделы 6–7 basics.py и strkeys.py сняты 14.10.2026 на linux/x86_64); отношения зависят от данных, версии и машины, у себя их надо мерить заново. CPython 3.15 (вышел 9 октября 2026) здесь не запускался.

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

Поиск (одинаково на 3.11–3.14): на 100 000 элементах x in list — 100 000 сравнений, x in set — 1 (у Key без коллизий), bisect — 17. bisect по неотсортированному списку возвращает неверный индекс без ошибки.

append: ёмкости 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, … — как в комментарии в Objects/listobject.c; на 1 000 / 10 000 / 100 000 добавлений — 28 / 47 / 66 перевыделений.

Скрытый квадрат: [x for x in a if x in b] без общих элементов — 10 000 сравнений при n = 100 и 1 000 000 при n = 1 000, если b список; 0, если множество.

sorted(): на случайных данных (зерно 42) — 8 655 / 120 184 / 1 531 824 сравнений при n = 1 000 / 10 000 / 100 000 на 3.13 и 3.14; на 3.11 и 3.12 — 8 632 / 119 836 / 1 529 011. lg(n!) — 8 529 / 118 458 / 1 516 704. На отсортированных и строго убывающих данных — n − 1 на всех версиях.

Словарь с одинаковыми хешами: поиск последнего ключа — n сравнений (10 / 100 / 1 000) против одного при обычных хешах.

Множество с одним хешем на всех (раздел 6, одинаково на 3.11–3.14): поиск последнего — 10 / 105 / 1 336 / 11 672 вызовов __eq__ при n = 10 / 100 / 1 000 / 10 000 (хеш 1); с хешем 0 при n = 100 — 114. Построение — 45 / 5 982 / 605 201 / 57 720 235. Найденный по тождеству элемент — 0 вызовов __eq__.

bisect и «нашли» (раздел 7): bisect_left возвращает позицию вставки; для 77 777 в списке чётных — позиция 38 889 и __eq__ → False; для 200 001 — позиция 100 000, равная длине, сравнивать не с чем. Полный короткий пример того же — find.py: для [2, 4, 6, 8] у 6 и 5 позиция одна — 2, contains даёт True и False.

Строковые ключи (strkeys.py, медианы, 3.13.7, нс): hash новой строки длиной 10 / 1 000 / 100 000 — 35,3 / 431,8 / 29 768,6; a == b у равных разных объектов — 21,3 / 36,0 / 2 567,6. Повторный hash той же строки — около 30–35 при любой длине: хеш запоминается в объекте.

Время (медианы, 3.13.7, нс на операцию при n = 1 000 / 10 000 / 100 000): append 35,1 / 26,3 / 28,4; insert(0, x) 308,2 / 2 242,9 / 19 988,0; x in list 5 332,6 / 52 136,7 / 643 060,2; x in set 25,4 / 27,2 / 26,2; sorted() на элемент 106,7 / 127,0 / 220,3.

Script

92 lines

"""Строковые ключи: цена hash и == зависит от длины строки.

ЗАЧЕМ. В уроке поиск по хешу считается «одним сравнением», а перебор —
«n сравнениями». Это счёт операций, а не времени: одна операция над
строкой — хеш или сравнение на равенство — сама стоит тем больше, чем
длиннее строка. Добавлено 14.10.2026 по внешнему аудиту (PY-CMP-02).

ЧТО МЕРЯЕТСЯ (нс на одну операцию, длина строки 10, 1 000 и 100 000):

  hash(новой строки) — хеш строки, у которой он ещё не вычислен: каждый
  раз новый объект (хеш строки вычисляется один раз и запоминается в
  объекте, поэтому повторный hash того же объекта почти бесплатен — он
  напечатан отдельной строкой);

  a == b — две равные строки, но разные объекты: равенство по тождеству
  не срабатывает, и сравнивается содержимое.

Подготовка (создание строк) в замер не входит. Формы меряются вперемежку,
ROUNDS кругов; печатаются медианы.

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

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

ROUNDS = 7
LENGTHS = (10, 1_000, 100_000)


def reps_for(length):
    return 20_000 if length <= 1_000 else 500


def fresh_copies(base, reps):
    # base[:-1] + base[-1:] — новый объект с тем же содержимым и без
    # вычисленного хеша.
    return [base[:-1] + base[-1:] for _ in range(reps)]


def op_hash_fresh(length):
    reps = reps_for(length)
    copies = fresh_copies("a" * length, reps)
    t0 = time.perf_counter()
    for c in copies:
        hash(c)
    return (time.perf_counter() - t0) / reps


def op_hash_cached(length):
    reps = reps_for(length)
    s = "a" * length
    hash(s)
    t0 = time.perf_counter()
    for _ in range(reps):
        hash(s)
    return (time.perf_counter() - t0) / reps


def op_eq(length):
    reps = reps_for(length)
    a = "a" * length
    b = a[:-1] + a[-1:]
    assert a is not b and a == b
    t0 = time.perf_counter()
    for _ in range(reps):
        a == b
    return (time.perf_counter() - t0) / reps


FORMS = [
    ("hash(новой строки)", op_hash_fresh),
    ("hash(той же строки)", op_hash_cached),
    ("a == b, разные объекты", op_eq),
]

samples = {(name, n): [] for name, _ in FORMS for n in LENGTHS}
for _ in range(ROUNDS):
    for n in LENGTHS:
        for name, fn in FORMS:
            samples[(name, n)].append(fn(n) * 1e9)

print(f"строковые ключи: нс на операцию, медианы {ROUNDS} кругов")
print(f"   {'операция':<26}" + "".join(f"{n:>12}" for n in LENGTHS))
for name, _ in FORMS:
    meds = [statistics.median(samples[(name, n)]) for n in LENGTHS]
    print(f"   {name:<26}" + "".join(f"{m:>12.1f}" for m in meds))