Почему этот урок важен

Big-O — это абстракция. Junior, выучивший «list.append O(1), dict.get O(1)» — формально знает теорию. Но в реальном коде встречаются паттерны, где формально кажется одно big-O, а реально получается другое. Эти паттерны — главная причина того, что «у меня же всё по теории, а скрипт работает 4 часа вместо 4 минут».

Разберём 6 самых частых ловушек.

Ловушка 1: x in list внутри цикла

Самая распространённая ошибка. Junior пишет:

def find_common(list_a, list_b):
    result = []
    for x in list_a:
        if x in list_b:  # O(len(list_b))
            result.append(x)
    return result

Кажется: «один цикл по a, проверка in — стандартная операция, должно быть O(n)». Но x in list_b — это O(m) в худшем случае, где m = len(list_b). Внутри цикла по a (n итераций) — получаем O(n * m).

На равных размерах n = m — это O(n²). На 100K элементах — 10 миллиардов операций. На 1M — триллион.

Правильно — превратить list_b в set, проверка in становится O(1):

def find_common_fast(list_a, list_b):
    set_b = set(list_b)   # O(m) один раз
    result = []
    for x in list_a:
        if x in set_b:    # O(1) каждая
            result.append(x)
    return result          # итог: O(n + m)

Замер:

import timeit

list_a = list(range(0, 10_000, 2))
list_b = list(range(0, 10_000, 3))

t_slow = min(timeit.repeat(
    lambda: [x for x in list_a if x in list_b],
    number=10, repeat=3
)) / 10

t_fast = min(timeit.repeat(
    lambda: [x for x in list_a if x in set(list_b)],
    number=10, repeat=3
)) / 10

print(f"list-based: {t_slow*1000:.1f} ms")
print(f"set-based:  {t_fast*1000:.1f} ms")
print(f"speedup:    {t_slow/t_fast:.0f}x")

Типичный вывод:

list-based: 850.0 ms
set-based:    1.2 ms
speedup:    700x

700-кратное ускорение от одного изменения. Это типичный профит.

Ловушка 2: конкатенация строк в цикле

Ещё одна классическая ошибка:

def build_str_slow(parts):
    result = ""
    for p in parts:
        result += p   # каждое += создаёт НОВУЮ строку
    return result

Строки в Python immutable. Это значит, что result += p не модифицирует строку — оно создаёт новый объект длиной len(result) + len(p), копируя обе строки в него.

Сложность одного += — O(len(result)). После N конкатенаций суммарная работа:

1 + 2 + 3 + ... + N = N * (N+1) / 2 = O(N²)

Правильно — использовать str.join:

def build_str_fast(parts):
    return "".join(parts)  # O(total length)

join сначала пробегает по всем частям, считает суммарную длину, выделяет один буфер этого размера, и копирует туда все части — O(N), где N — суммарная длина.

import timeit

parts = [f"chunk_{i}_" for i in range(10_000)]

t_slow = min(timeit.repeat(
    lambda: __import__("functools").reduce(lambda a, b: a + b, parts, ""),
    number=10, repeat=3
)) / 10

t_fast = min(timeit.repeat(
    lambda: "".join(parts),
    number=10, repeat=3
)) / 10

print(f"+= concat: {t_slow*1000:.2f} ms")
print(f"str.join:  {t_fast*1000:.2f} ms")
print(f"speedup:   {t_slow/t_fast:.0f}x")

Типичный вывод:

+= concat: 180.00 ms
str.join:    0.30 ms
speedup:   600x

Ловушка 3: копирование при slice-ах

lst[i:j] создаёт копию длины (j-i). Это O(j-i) по времени и памяти. Junior часто пишет:

def reverse_iter_bad(lst):
    while lst:
        x = lst[0]
        lst = lst[1:]   # копирует весь хвост — O(n) каждый раз
        print(x)

Кажется простым. Реально: на каждом шаге копируется хвост длиной n, n-1, n-2, …, 1. Сумма — O(n²).

Правильно — итерация через индексы или iter:

def reverse_iter_good(lst):
    for x in lst:
        print(x)        # O(n) total

Аналогичная ловушка с list copies в рекурсии:

def sum_recursive(lst):
    if not lst:
        return 0
    return lst[0] + sum_recursive(lst[1:])  # копия каждый раз

Каждый вызов копирует хвост. Time O(n²), space O(n²) (все эти копии висят на стеке). Правильно — передавать индекс:

def sum_recursive(lst, i=0):
    if i == len(lst):
        return 0
    return lst[i] + sum_recursive(lst, i+1)  # копии нет

Ловушка 4: вложенные generator/list comprehensions

# Кажется элегантным, но...
result = [(x, y) for x in big_list for y in big_list if x != y]

Это двойной цикл — O(n²). На 10K элементов — 100M операций, на 100K — 10B. Если случайно засунули такое в hot path — провал.

Тоже бывает скрытое:

unique_pairs = {(x, y) for x in lst for y in lst}  # тоже O(n^2)

Правило: любой код с двумя циклами по входу — O(n²), независимо от синтаксиса (явный for, comprehension, map, generator).

Ловушка 5: len() внутри цикла — не баг, но…

Это не ловушка, но многие junior’ы боятся:

for i in range(len(lst)):    # len() O(1)
    ...

len(list) — это O(1). У list-а длина хранится в заголовке объекта, не считается итерацией. То же для len(dict), len(set). Бояться не надо.

Но: len(generator) — TypeError, у генератора нет длины. len(s) для str/bytes — O(1) (длина в заголовке). len(range(n)) — O(1) (range это объект, а не materialized list).

А вот это уже ловушка:

for i in range(sum(1 for _ in iterator)):
    ...

Здесь sum(1 for _ in iterator) проходит по всему итератору O(n) и потом второй раз тот же итератор не сработает (уже исчерпан). Не пишите так.

Ловушка 6: list.remove / list.pop(0)

def remove_evens_bad(lst):
    for x in lst[:]:        # копия для итерации
        if x % 2 == 0:
            lst.remove(x)    # ищет и сдвигает — O(n) каждый раз
    return lst

lst.remove(x) — это линейный поиск + сдвиг хвоста. На N удалений — O(n²).

Правильно: создать новый список, либо использовать del с известным индексом, либо filter:

def remove_evens_good(lst):
    return [x for x in lst if x % 2 != 0]   # O(n), новый список

Аналогично, lst.pop(0) каждый раз сдвигает все элементы — O(n). Используйте collections.deque, если нужны частые pop из начала:

from collections import deque

queue = deque(big_list)
while queue:
    x = queue.popleft()    # O(1)

Попробуй сам: спрятанная O(n²)

Найдите проблему в коде ниже без запуска. Потом запустите и измерьте на n=10000 и n=20000:

def process(events):
    """events — список dict-ов с полем 'user_id'"""
    seen_users = []
    unique_events = []
    for e in events:
        if e['user_id'] not in seen_users:   # ?
            seen_users.append(e['user_id'])
            unique_events.append(e)
    return unique_events

import timeit, random

def make_events(n):
    return [{'user_id': random.randint(0, n // 2)} for _ in range(n)]

for n in [1000, 10_000, 20_000]:
    events = make_events(n)
    t = min(timeit.repeat(lambda: process(events), number=1, repeat=3))
    print(f"n={n}: {t*1000:.0f} ms")

n=1000:     10 ms
n=10000:   850 ms
n=20000:  3400 ms

Шпаргалка: типичные ловушки

Правила, которые экономят джуну часы отладки

1. Внутри цикла проверка in some_collection — some_collection должен быть set/dict, не list.
2. Конкатенация строк — str.join, не +=.
3. Slice внутри рекурсии или цикла — нет, передавайте индексы.
4. Удаление из начала list — нет, deque или фильтр.
5. Любой вложенный цикл по входу — оцените big-O, не тащите в production без оснований.

И главное правило — мерь подозрительные места. Если кажется, что код медленный — поставьте timeit на горячий блок и сверьтесь с ожидаемым big-O. Несовпадение — повод копать.

В следующем модуле — выход на уровень железа. Иерархия памяти, кэш-линии, и почему даже формально-одинаковые big-O могут различаться в 10 раз на практике.