MEASUREMENT
bench/complexity/cost.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
102 lines"""Время операций при росте n в десять раз: O(1), O(n) и O(n log n) в наносекундах.
ЗАЧЕМ. basics.py считает сравнения; здесь то же видно по часам. Если
операция O(1), при росте n в десять раз её время почти не меняется; если
O(n) — растёт примерно в десять раз; O(n log n) на элемент — чуть заметнее,
чем O(1). Отношение «время при 10n / время при n» и есть то, что O-нотация
предсказывает.
ЧТО МЕРЯЕТСЯ (нс на одну операцию, n = 1 000, 10 000, 100 000):
list.append — n добавлений в пустой список, время / n;
list.insert(0, x) — 1 000 вставок в начало списка длины n;
x in list — искомый элемент последний;
x in set — тот же элемент во множестве;
sorted(), на элемент — сортировка перемешанного списка из n целых, время / n.
Подготовка (создание списков) в замер не входит. Формы меряются
вперемежку, ROUNDS кругов; печатаются медианы и отношения соседних размеров.
Запускать: python3.13 / 3.14. Числа — этой машины; отношения — наблюдение
этой конфигурации, на другой машине и версии их надо мерить заново.
"""
import random
import statistics
import sys
import time
print("PY", sys.version.split()[0])
print()
ROUNDS = 7
SIZES = (1_000, 10_000, 100_000)
rng = random.Random(7)
def op_append(n):
lst = []
t0 = time.perf_counter()
for i in range(n):
lst.append(i)
return (time.perf_counter() - t0) / n
def op_insert0(n):
lst = list(range(n))
k = 1_000
t0 = time.perf_counter()
for i in range(k):
lst.insert(0, i)
return (time.perf_counter() - t0) / k
def op_in_list(n):
lst = list(range(n))
target = n - 1
reps = max(20, 2_000_000 // n)
t0 = time.perf_counter()
for _ in range(reps):
target in lst
return (time.perf_counter() - t0) / reps
def op_in_set(n):
st = set(range(n))
target = n - 1
reps = 200_000
t0 = time.perf_counter()
for _ in range(reps):
target in st
return (time.perf_counter() - t0) / reps
def op_sorted(n):
data = list(range(n))
rng.shuffle(data)
t0 = time.perf_counter()
sorted(data)
return (time.perf_counter() - t0) / n
FORMS = [
("list.append", op_append),
("list.insert(0, x)", op_insert0),
("x in list", op_in_list),
("x in set", op_in_set),
("sorted(), на элемент", op_sorted),
]
samples = {(name, n): [] for name, _ in FORMS for n in SIZES}
for _ in range(ROUNDS):
for n in SIZES:
for name, fn in FORMS:
samples[(name, n)].append(fn(n) * 1e9)
print("нс на операцию, медианы", ROUNDS, "кругов")
print(f" {'операция':<22}" + "".join(f"{n:>12}" for n in SIZES) + f"{'×10':>8}{'×100':>8}")
for name, _ in FORMS:
med = [statistics.median(samples[(name, n)]) for n in SIZES]
r1 = med[1] / med[0]
r2 = med[2] / med[0]
print(f" {name:<22}" + "".join(f"{m:>12.1f}" for m in med) + f"{r1:>8.1f}{r2:>8.1f}")