Замер: окно
и перебор подотрезков

Категория

Замер

Уровень

Начальный

Опирается на

Главы 10.3–10.5: оценки O(n) и O(n²); глава 9.7: устройство замера

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

Подтвердить оценку сложности числами и объяснить её на review

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

Сравниваются два перебора — для минимального отрезка, устроенный как перебор главы 10.3, и перебор подстрок из главы 10.5 — с окнами из глав 10.4 и 10.5. Оба перебора устроены одинаково: для каждого начала l отрезок удлиняется вправо, пока не найден ответ для этого начала, и внутренний цикл прерывается оператором break. Для минимального отрезка — пока сумма не достигла порога, для подстроки — пока не встретился повтор.

Из-за break время перебора зависит от данных. Если ответ для каждого начала находится через L шагов, перебор делает около n·L шагов. В худшем случае ответа нет, внутренний цикл доходит до конца списка, и шагов n·(n + 1)/2, это O(n²). Окно от данных почти не зависит: каждая граница проходит вход один раз, шагов не больше 2·n. Поэтому в каждом опыте меняется свой параметр.

В опытах 2 и 3 видно то, чего не было в замере модуля 9. У одного и того же перебора на списке одной длины время различается в сотни раз — в зависимости от того, какие числа и символы в нём записаны.

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

Правила те же, что в главе 9.7: медиана нескольких запусков, подготовка данных вне замера, одни и те же данные для обоих способов. Переборы записаны в самом bench.py, из solution.py импортируются только две функции занятия.

1. Данные для минимального отрезка. 20 000 случайных целых чисел от 1 до 9, зерно random.Random(10). В опыте 1 порог равен сумме списка плюс 1 — отрезка с такой суммой нет. В опыте 2 порог 10, 100, 1000 и 10 000, длина ответа выводится в скобках.
2. Данные для подстроки. Строка из 20 000 символов, в которой m разных символов повторяются по кругу: при m = 3 это 'ĀāĂĀāĂ…'. Для каждого начала подстрока без повторов имеет длину ровно m, поэтому перебор делает около n·m шагов.
3. Медиана пяти запусков. Время одного вызова меряется time.perf_counter(), из пяти берётся медиана: единичный скачок, когда процессор занят другой программой, на неё не влияет.
4. Отношение в последнем столбце. Во сколько раз перебор медленнее окна на тех же данных.

def shortest_window_brute(nums, s):
    if s < 1:
        raise ValueError("s должно быть не меньше 1")
    best = 0
    for l in range(len(nums)):
        total = 0
        for r in range(l, len(nums)):
            total += nums[r]
            if total >= s:
                if best == 0 or r - l + 1 < best:
                    best = r - l + 1
                break
    return best


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

>>> def show(*args):
...     return args
...
>>> show([1, 2], 5)
([1, 2], 5)
>>> show("abc")
('abc',)
>>> max(*[3, 9, 4])
9

Перебор из главы 10.3 искал самый длинный отрезок и проверял все отрезки. Перебор здесь прерывает внутренний цикл, как только сумма достигла порога: более длинные отрезки с тем же началом ответом не будут. Это самый быстрый вариант перебора, поэтому окно сравнивается с лучшим из переборов.

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

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

Python 3.12.12, Darwin arm64

1. Минимальный отрезок, отрезка нет, n растёт
n               |   перебор  |    окно    | перебор / окно
500             |      2.331 |      0.009 |    262.6
1000            |     10.742 |      0.022 |    484.6
2000            |     44.739 |      0.039 |   1136.2
4000            |    174.304 |      0.083 |   2102.2
8000            |    678.676 |      0.167 |   4066.0

2. Минимальный отрезок, n = 20 000, порог s растёт
s (ответ)       |   перебор  |    окно    | перебор / окно
10 (2)          |      2.456 |      1.071 |      2.3
100 (13)        |      8.049 |      1.059 |      7.6
1000 (178)      |     80.863 |      1.290 |     62.7
10000 (1942)    |    772.905 |      1.431 |    540.1

3. Подстрока без повторов, n = 20 000, в строке m разных символов по кругу
m               |   перебор  |    окно    | перебор / окно | позиции
1               |      4.747 |      3.954 |            1.2 |    2.984
10              |     28.886 |      3.969 |            7.3 |    2.810
100             |    254.975 |      3.947 |           64.6 |    2.913
1000            |   2628.576 |      4.172 |          630.0 |    3.213

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

В последнем столбце опыта 3 — время варианта с позициями символов из главы 10.5, §8. Он записан в bench.py, писать его не нужно.

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

Порог больше суммы всего списка, поэтому ни для одного начала сумма порога не достигает, и break не срабатывает. Перебор проходит все n·(n + 1)/2 отрезков — это его худший случай. При удвоении n время перебора растёт примерно в 4 раза, время окна — в 2.

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

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

При n = 8000 перебор прошёл 8000 · 8001 / 2 = 32 004 000 отрезков за 0,68 с, около 21 нс на отрезок. При n = 1 000 000 отрезков около 5·10¹¹. При той же скорости это около 10 600 с, почти три часа. Окно при n = 8000 тратило около 21 нс на элемент, на миллионе это около 21 мс. Обе цифры — оценки по замеру: такой запуск не проводился. Интервьюер в главе 10.2 назвал размер списка до миллиона — поэтому перебор для этой задачи не подходит.

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

Длина списка одна — 20 000 чисел от 1 до 9, — меняется порог. Чем он больше, тем длиннее отрезок, который нужен, чтобы сумма его достигла, и тем больше шагов делает внутренний цикл перебора до break. Длина ответа в скобках растёт почти вдесятеро при каждом увеличении порога: 2, 13, 178, 1942. Примерно так же растёт и время перебора.

Линия окна почти горизонтальная: от 1,1 до 1,4 мс. Каждый элемент входит в окно один раз и выходит не больше одного раза, сколько бы элементов ни было в окне. Линия перебора при больших порогах идёт с наклоном 1: время пропорционально длине ответа. При пороге 10 перебор медленнее окна всего в 2,3 раза, при пороге 10 000 — в 540 раз.

Из опыта следует, что оценка перебора на конкретных данных — O(n·L), где L — длина отрезка, на котором срабатывает break. Если данные такие, что ответ всегда короткий, перебор работает быстро, и тест на маленьком пороге этого не покажет. Поэтому сложность называют для худшего случая: O(n²), опыт 1.

§6Опыт 3: подстрока без повторов

Перебор подстрок прерывается на первом повторе. В строке, где m разных символов идут по кругу, от любого начала без повторов идут ровно m символов, и перебор делает около n·m шагов. При m = 1 он почти не отличается от окна, при m = 1000 медленнее в 630 раз.

Оценку перебора O(n·m) из главы 10.5 замер подтверждает: при росте m в 10 раз время растёт в 6,1, 8,8 и 10,3 раза. Множитель меньше 10 при малых m — это постоянная часть работы на каждое начало: создание множества seen и шаг внешнего цикла. Для текста на одном языке m невелико, около сотни символов, но строка может содержать любые символы Юникода, и тогда m сравнимо с n.

Два варианта окна различаются на постоянный множитель. Вариант с позициями быстрее примерно на четверть: на каждом символе он выполняет одну проверку и одно присваивание, без вложенного цикла и без уменьшения счётчиков. Оба — O(n), и обе линии на графике горизонтальные. На собеседовании такой разницей не выбирают решение: выбирают то, которое кандидат может объяснить и проверить.

§7Цена одного шага

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

Цены посчитаны делением времени на число единиц работы. Для перебора минимального отрезка — 678,7 мс на 32 004 000 отрезков в опыте 1. Для перебора подстрок — 2628,6 мс примерно на 20 000 · 1001 подстрок в опыте 3. Для окон — время опыта на 20 000 элементов. Шаг окна дороже шага перебора: на каждом элементе окно выполняет и расширение, и сжатие. Но шагов у окна не больше 2·n, а у перебора — до n²/2. Поэтому в худшем случае окно уже при n = 500 быстрее в 260 раз.

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

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

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

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