Окно
и пересчёт за O(1)

Категория

Алгоритм

Уровень

Начальный

Опирается на

Главы 9.1 и 9.2; занятие 7: срезы и полуинтервалы

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

На этом сдвиге построены все задачи модуля

§1Задача: сумма каждого окна

Задача КТП о лучшем отрезке длины k разобрана в главе 9.4. Здесь — более простая задача, которая лежит внутри неё: посчитать сумму каждого окна. Лучшему отрезку остаётся только выбрать наибольшую из этих сумм. Контракт тот же, что в главе 9.2: числа могут быть отрицательными, неверное k даёт ValueError.

§2Решение срезами

Самое прямое решение — для каждого начала окна s взять срез nums[s:s + k] и сложить его функцией sum. Начала окон — от 0 до n − k включительно, поэтому цикл идёт по range(len(nums) - k + 1). Это решение пишется сразу и служит эталоном: с ним сравнивают быстрое.

def window_sums_slices(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    sums = []
    for s in range(len(nums) - k + 1):
        sums.append(sum(nums[s:s + k]))
    return sums

>>> def check(k):
...     if k < 1:
...         raise ValueError("k должно быть не меньше 1")
...     return k
...
>>> check(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in check
ValueError: k должно быть не меньше 1

>>> nums = [12, 15, 9, 20, 18]
>>> nums[1:4]
[15, 9, 20]
>>> sum(nums[1:4])
44

Прогон ниже показывает, что каждое окно считается с нуля. Голубые ячейки — текущее окно, указатель s стоит на его начале.

На шагах 4 и 6 видно повторение работы. Окно [12, 15, 9] и окно [15, 9, 20] имеют общую часть 15 + 9, но во втором окне она складывается заново. При k = 3 общая часть — два элемента, при k = 1000 — 999.

§3Сколько стоят срезы

Окон n − k + 1. В каждом k элементов копируются в срез и ещё раз читаются при сложении. Число элементов во всех срезах — (n − k + 1)·k, время O(n·k). Сильнее всего это заметно, когда k — примерно половина n: окон около n/2, в каждом около n/2 элементов, итого около n²/4.

Кроме времени, срез занимает память: на каждом шаге создаётся список из k элементов. Он удаляется сразу после sum, поэтому дополнительная память — O(k), но копирование всё равно стоит времени.

§4Идея сдвига и состояние окна

Соседние окна отличаются двумя элементами: при сдвиге на одну позицию слева уходит nums[r − k], справа приходит nums[r]. Здесь r — индекс элемента, который входит в окно. Остальные k − 1 элементов общие, их сумма уже известна. Поэтому новую сумму получают из старой:

новая сумма = старая сумма + nums[r] − nums[r − k]

[12, 15, 9] 20     →     12 [15, 9, 20]
сумма 36                 36 + 20 − 12 = 44

1. Первое окно. Сложить nums[0:k] целиком: total = sum(nums[:k]). Это единственное окно, которое считается с нуля.
2. Сдвиг. Для каждого r от k до n − 1: total += nums[r] − nums[r − k]. Теперь total — сумма окна nums[r − k + 1:r + 1].
3. Запись. После первого окна и после каждого сдвига дописать total в ответ.

§5Сдвиг окна вручную

Прежде чем смотреть код, сделайте сдвиги сами. На каждом сдвиге щёлкните ячейку, которая уходит из окна, затем ячейку, которая входит, и введите новую сумму. Неверный выбор не выполняется, вместо него появляется объяснение.

§6Сборка функции из строк

Правило из §4 записывается функцией из девяти строк. Расставьте их по порядку: сначала проверка k, затем первое окно и начало ответа, затем цикл со сдвигом и записью. Готовая функция — ниже, в прогоне §7.

>>> list(range(3, 7))
[3, 4, 5, 6]
>>> total = 36
>>> total += 20 - 12
>>> total
44

Напишите функцию сами в окне ниже, прямо на странице. «Запустить тесты» проверяет её на восьми тестах. Среди них k = 1, k = n, неверное k, пустой список и сравнение с суммами срезов на двухстах случайных списках. Часть тестов заготовка проходит сразу. Первый запуск загружает Python в браузер, около 10 МБ.

§7Код и пошаговый прогон

def window_sums(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    sums = [total]
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        sums.append(total)
    return sums

Прогон на том же списке, что в §2. Голубые ячейки — окно после сдвига, перечёркнутая — элемент, который из него ушёл. Указатель r стоит на элементе, который вошёл.

Цикл выполняется n − k раз, каждая итерация — одно вычитание, одно сложение и запись в ответ. Вместе с первым окном это k + 2·(n − k) обращений к элементам, время O(n) при любом k. Дополнительной памяти, кроме списка ответа, не нужно: срезов нет. Замер обоих способов — в главе 9.7.

§8Две ошибки сдвига

В каждой ошибке код отличается от верной версии одной строкой, и Python выполняет его без исключений: неверен только ответ. Каждая запущена на том же списке, что и верная версия выше, и её можно пройти по шагам. Ответ для сравнения: [36, 44, 47, 45, 50].

Верная версия — прогон в §7. Обе ошибки ловят тесты песочницы: первую — test_example, test_k_is_one, test_negative и сравнение со срезами, вторую — те же тесты и test_k_is_n.

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