Замер четырёх способов
найти пару

Категория

Эксперимент

Уровень

Начальный

Опирается на

Занятие 4: замеры времени; главы 8.2 и 8.4

Зачем это знать

Подтверждать оценку O(…) числами и выбирать способ под ограничения

§1Четыре способа

Два способа уже разобраны в главе 8.4. Ещё два пригодятся, когда список не отсортирован: словарь уже просмотренных цен и сортировка копии с последующими указателями. Все четыре отвечают на один вопрос — есть ли пара с суммой target, — но требуют разного от входа и тратят разную память.

>>> import math
>>> round(math.log2(1000)), round(math.log2(1_000_000))
(10, 20)

def pair_sum_set(prices, target):
    seen = {}                               # цена → индекс первого вхождения
    for j, p in enumerate(prices):
        if target - p in seen:              # нужная пара уже встречалась
            return (seen[target - p], j)
        seen.setdefault(p, j)
    return None


def pair_sum_sorted_copy(prices, target):
    ordered = sorted(prices)                # новый список, O(n log n)
    answer = pair_sum(ordered, target)
    if answer is None:
        return None
    i, j = answer
    return (ordered[i], ordered[j])

>>> for j, p in enumerate([300, 450]):
...     print(j, p)
...
0 300
1 450
>>> seen = {}
>>> seen.setdefault(300, 0)
0
>>> seen.setdefault(300, 5)
0
>>> seen
{300: 0}
>>> 1600 - 1300 in seen
True

>>> a = [3, 1, 2]
>>> b = sorted(a)
>>> a, b
([3, 1, 2], [1, 2, 3])
>>> a.sort()
>>> a
[1, 2, 3]
>>> print(a.sort())
None

Словарь устроен так: для каждой цены p проверяется, встречалась ли раньше парная ей цена target − p. Если встречалась, пара найдена. Если нет, цена p записывается в словарь вместе со своим индексом, чтобы её могли найти следующие цены. Проверка in у словаря в среднем стоит O(1), подробно это разобрано в занятии 17. Сам словарь занимает память под каждую просмотренную цену.

Прогон ниже — на неотсортированном каталоге из главы 8.5, где указатели пару потеряли. Список читается один раз слева направо, указатель j под ячейками — текущая цена, содержимое словаря видно в таблице переменных.

Пара нашлась на пятой цене: для 900 парная цена 700 уже лежит в словаре с индексом 3. Порядок цен для словаря не важен, поэтому ответ (3, 4) совпадает с ответом перебора.

§2Как устроен замер

Замер повторяет правила занятия 4: измеряется худший случай, каждое число — медиана нескольких запусков, копирование и подготовка данных вне замера.

1. Худший случай — пары нет. Цены — чётные числа 0, 2, 4, …, цель — 1. Сумма двух чётных чисел чётная, поэтому пары нет, и каждый способ просматривает вход до конца.
2. Одинаковые данные. Перебор и указатели получают отсортированный список, словарь и сортировка — тот же список, перемешанный с фиксированным зерном random.Random(8).
3. Медиана пяти запусков. Время одного запуска меряется time.perf_counter(), из пяти берётся медиана: она не реагирует на единичный скачок, когда процессор ненадолго занят другой программой.
4. Перебор до 16 000. На списке из 100 000 элементов перебор идёт больше минуты, поэтому его не запускали. Для миллиона время дано оценкой.

def measure(func, prices, target, repeat=5):
    times = []
    for _ in range(repeat):
        start = time.perf_counter()
        func(prices, target)
        times.append(time.perf_counter() - start)
    return statistics.median(times) * 1000    # миллисекунды

§3Результаты

Настоящий вывод python bench.py на ноутбуке автора: Apple M4, Python 3.12.12, macOS, 28.09.2026. На другой машине числа будут другими, отношения между ними — близкими.

Python 3.12.12, Darwin arm64
n        | перебор   | указатели | словарь   | сортировка + указатели
------------------------------------------------------------------------
1000     |     12.97 |     0.033 |     0.059 |     0.082
2000     |     51.73 |     0.063 |     0.110 |     0.135
4000     |    170.09 |     0.131 |     0.225 |     0.341
8000     |    751.50 |     0.282 |     0.472 |     0.782
16000    |   2785.62 |     0.548 |     0.886 |     1.765
100000   | не мерили |     3.042 |     6.925 |    12.720
1000000  | не мерили |    33.625 |   177.025 |   206.950
Время в миллисекундах. Перебор на n > 16 000 не запускается: он идёт минуты.

На графике обе оси логарифмические: каждая метка в 10 раз больше предыдущей. На такой шкале зависимость вида n^k выглядит прямой линией, и её наклон равен k. Линия перебора идёт круче остальных вдвое: у неё k = 2, у остальных около 1. Наведите на точку, чтобы увидеть число.

§4Что показывают числа

Рост при удвоении n

Удобнее сравнивать, во сколько раз растёт время, когда список становится вдвое длиннее. Для O(n) ожидаем рост примерно в 2 раза, для O(n²) — примерно в 4.

Отношения колеблются вокруг 4 и 2 — оценки O(n²) и O(n) подтверждаются. Точно 4 и 2 не получается: на время влияют кэш процессора и работа интерпретатора, которые от n зависят не строго.

Сколько шёл бы перебор на миллионе

На 16 000 элементах перебор проверил 127 992 000 пар за 2,79 с, то есть около 21,8 нс на пару. На миллионе элементов пар 499 999 500 000, и при той же скорости перебор шёл бы около 10 900 с — примерно три часа. Указатели справились за 34 мс.

Словарь и сортировка

Словарь тоже растёт линейно, но на каждом шаге вычисляет хеш и обращается к памяти. Поэтому на миллионе элементов он в 5 раз медленнее указателей и занимает память под миллион записей. Сортировка копии — самый медленный из быстрых способов: к линейному проходу добавляется O(n log n) на сортировку и память под копию. Зато оба работают на неотсортированном входе, где указатели неприменимы.

§5Как выбрать способ

Способ выбирают по ответам на вопросы из главы 8.3, а замер показывает цену каждого выбора.

Перебор в последней строке выбран намеренно. Если условие гарантирует маленький вход, простой код, в котором легко убедиться, бывает лучше быстрого. На собеседовании это оговаривают: «при таких ограничениях хватит перебора, но если n вырастет — вот решение за O(n)».

§6Замер у себя

Скрипт bench.py лежит в стартовом наборе lesson_08. Он импортирует ваши pair_sum_brute и pair_sum из solution.py, поэтому запускать его нужно после того, как обе функции написаны и тесты проходят.

1. Перейдите в папку lesson_08 и выполните python bench.py. На машине автора замер идёт около 20 секунд, почти всё время занимает перебор на 16 000 элементах.
2. Сохраните вывод в файл bench_results.txt: python bench.py > bench_results.txt.
3. Посчитайте рост времени при удвоении n для перебора и указателей, как в таблице §4, и запишите в complexity_note.md.
4. Если отношения далеки от 4 и 2, проверьте, не открыты ли тяжёлые программы, и запустите замер ещё раз.

§7Проверьте себя