Замер: сдвиг окна
и сумма среза

Категория

Эксперимент

Уровень

Начальный

Опирается на

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

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

Подтвердить O(n·k) и O(n) числами и объяснить их на review

§1Что сравниваем и чего ждём

Сравниваются две функции из главы 9.3. window_sums_slices для каждого из n − k + 1 окон берёт срез и складывает его: время O(n·k). window_sums складывает первое окно, а дальше сдвигает его одним вычитанием и одним сложением: время O(n) при любом k. В отличие от замера главы 8.10, здесь у задачи два параметра, n и k, поэтому опытов три — в каждом меняется свой параметр.

Опыт 1 показывает важную деталь: при фиксированном k оба способа растут линейно по n. Отличие в сложности видно, только когда растёт k. Поэтому для окна оценку пишут через оба параметра: O(n·k).

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

Правила те же, что в занятии 4 и главе 8.10: медиана нескольких запусков, подготовка данных вне замера, один и тот же список для обоих способов.

1. Одни данные. 400 000 случайных целых чисел от −1000 до 1000, зерно random.Random(9). Каждый опыт берёт начало этого списка нужной длины, обе функции получают один и тот же срез.
2. Медиана пяти запусков. Время одного вызова меряется time.perf_counter(), из пяти берётся медиана. Медиана не реагирует на единичный скачок, когда процессор ненадолго занят другой программой.
3. Подготовка вне замера. Срез data[:n] создаётся до вызова measure, в замер попадает только сама функция.
4. Отношение в последнем столбце. Во сколько раз срезы медленнее сдвига при тех же n и k.

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


def row(n, k, nums):
    slices = measure(window_sums_slices, nums, k)
    rolling = measure(window_sums, nums, k)
    print(f"{n:<9}| {k:<7}| {slices:10.3f} | {rolling:10.3f} | {slices / rolling:6.1f}")

>>> f"[{25000:<9}]"
'[25000    ]'
>>> f"[{13.7049:10.3f}]"
'[    13.705]'

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

Настоящий вывод python bench.py на ноутбуке автора: Apple M4, Python 3.12.12, macOS, 07.10.2026. Замер шёл 34 секунды, почти всё время заняли срезы при k = 10 000 и в опыте 3. Повторный запуск дал числа, которые отличаются от этих не больше чем на 14 %; отношения между способами те же.

Python 3.12.12, Darwin arm64

1. k = 100, n растёт
n        | k      |    срезы   |   сдвиг    | срезы / сдвиг
25000    | 100    |     13.705 |      1.109 |   12.4
50000    | 100    |     28.895 |      2.389 |   12.1
100000   | 100    |     57.639 |      4.529 |   12.7
200000   | 100    |    113.811 |      9.246 |   12.3
400000   | 100    |    228.023 |     18.601 |   12.3

2. n = 100 000, k растёт
n        | k      |    срезы   |   сдвиг    | срезы / сдвиг
100000   | 1      |      8.125 |      4.308 |    1.9
100000   | 10     |     14.065 |      4.430 |    3.2
100000   | 100    |     59.903 |      4.779 |   12.5
100000   | 1000   |    388.996 |      4.488 |   86.7
100000   | 10000  |   4173.750 |      4.074 | 1024.4

3. k = n / 2, n растёт
n        | k      |    срезы   |   сдвиг    | срезы / сдвиг
2000     | 1000   |      3.771 |      0.048 |   78.4
4000     | 2000   |     15.870 |      0.100 |  159.0
8000     | 4000   |     70.356 |      0.193 |  364.9
16000    | 8000   |    284.182 |      0.413 |  687.7
32000    | 16000  |   1137.466 |      0.771 | 1475.0

Время в миллисекундах, медиана пяти запусков.

§4Опыт 1: растёт длина списка

При k = 100 удвоение n удваивает время обоих способов. Отношение «срезы / сдвиг» держится около 12 на всех длинах: способы растут одинаково, но срезы в 12 раз медленнее.

Это совпадает с оценкой O(n·k): если k не меняется, срезы — линейная функция от n с множителем k. По одному опыту 1 разница между способами выглядела бы как постоянный множитель «в 12 раз быстрее». Что это разница в сложности, видно только в опытах 2 и 3.

§5Опыт 2: растёт длина окна

Опыт 2 показывает, чем сдвиг отличается от срезов: при n = 100 000 его время около 4–5 мс при любом k — от 1 до 10 000. Каждый сдвиг стоит одно вычитание и одно сложение независимо от того, сколько элементов в окне. У срезов время растёт вместе с k: от 100 до 1000 — в 6,5 раза, от 1000 до 10 000 — в 10,7 раза.

Линия сдвига на графике горизонтальная — время не зависит от k. Линия срезов при больших k идёт с наклоном 1: время пропорционально k. При малых k она пологая: там заметна постоянная часть работы на каждое окно, о ней — §7.

Точное число элементов во всех срезах при переходе от k = 1000 к k = 10 000 выросло в 9,1 раза: окон стало 90 001 вместо 99 001. Время выросло в 10,7 раза. Такие отклонения от оценки на замерах обычны, в главе 8.10 точные 4 и 2 тоже не получались. Отношение «срезы / сдвиг» дошло до 1024: одна и та же задача решается за 4 мс и за 4,2 секунды.

§6Опыт 3: окно — половина списка

Когда k растёт вместе с n, срезы становятся квадратичными: окон около n/2, в каждом n/2 элементов. При удвоении n время срезов растёт в 4 раза, время сдвига — в 2.

На логарифмических осях линия срезов идёт с наклоном 2, линия сдвига — с наклоном 1, как перебор и указатели в главе 8.10.

Сколько шли бы срезы на миллионе

При n = 32 000 и k = 16 000 срезы обработали 16 001 · 16 000 ≈ 2,56·10⁸ элементов за 1,14 с. Это около 4,4 нс на элемент. При n = 1 000 000 и k = 500 000 элементов во всех срезах 500 001 · 500 000 ≈ 2,5·10¹¹. При той же скорости это около 1100 с, примерно 18 минут. Сдвиг тратил около 46 нс на шаг при n = 400 000, на миллионе это около 46 мс. Обе цифры — оценки по замеру: такой запуск не проводился.

§7Цена одного элемента

Из чисел замера можно посчитать, сколько стоит одна единица работы каждого способа.

Элемент среза в 8–10 раз дешевле шага цикла: копирование и sum идут внутри интерпретатора и не выполняют байт-код на каждый элемент. Поэтому при небольших k разница между способами меньше, чем подсказывает оценка O(n·k) против O(n). Но даже при k = 1 срезы медленнее в 1,9 раза. На каждое окно они создают новый список и вызывают sum, и эта постоянная часть работы дороже двух арифметических операций сдвига.

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

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

1. Перейдите в папку lesson_09 и выполните python bench.py. На машине автора замер идёт около 35 секунд.
2. Сохраните вывод: python bench.py > bench_results.txt.
3. Для опытов 1 и 3 посчитайте рост времени при удвоении n, как в таблицах §4 и §6, и запишите в complexity_note.md.
4. Для опыта 2 запишите, во сколько раз выросло время срезов от k = 1 до k = 10 000 и как изменилось время сдвига.
5. Если отношения далеки от 2 и 4, закройте тяжёлые программы и запустите замер ещё раз.

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