Когда готового нет: ускоряем перебор, убирая повторную работу

Если ты умеешь находить в переборе повторную работу и знаешь, чем её убирать, листай до «Теперь сам».

Как думаешь, что здесь лишнее

Нужно посчитать пары цен, отличающихся не больше чем на 300 рублей. Перебор берёт каждую пару:

for i in range(n):
    for j in range(i + 1, n):
        if abs(a[i] - a[j]) <= 300: ...

Какую работу он делает зря? Ответь себе до чтения.

Для каждого i он заново просматривает все цены, хотя подходят только близкие - и большинство проверок заведомо проваливается. Если цены упорядочить, близкие к a[j] окажутся рядом с ним, подряд, и искать их среди всех станет не нужно.

На что это похоже

Поиск нужной книги дома. Если книги стоят как попало, за каждой приходится обходить все полки - это перебор. Расставь их по алфавиту один раз - и каждый следующий поиск короткий. Расстановка стоит времени, но окупается со второго-третьего поиска. Ускорение перебора почти всегда выглядит так: один раз заплатить за порядок или память, чтобы не повторять работу на каждом шаге.

Механизм: три источника повторной работы

Порядок работы такой. Перебор уже написан - он эталон из урока о маленьком примере. В нём ищется внутренний цикл и вопрос: что из сделанного на прошлом шаге этому циклу можно было бы не делать заново? Ответ называет источник повтора, а таблица - лекарство. Новое решение сверяется с перебором на маленьких входах.

Правило

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

Разбор: пары близких цен - сортировка и два указателя

После сортировки партнёры b[j] слева от него - это непрерывный отрезок b[i..j−1]: всё, что левее i, отличается больше чем на d. При переходе к следующему j граница i может только сдвинуться вправо, никогда назад. Значит, оба указателя вместе проходят список один раз.

import random

def perebor(a, d):
    # каждая пара заново: |a[i] - a[j]| <= d
    par = 0
    proverok = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            proverok = proverok + 1
            if abs(a[i] - a[j]) <= d:
                par = par + 1
    return [par, proverok]

def dva_ukazatelya(a, d):
    # после сортировки партнёры a[j] - подряд идущий отрезок слева от j
    b = sorted(a)
    par = 0
    proverok = 0
    i = 0
    for j in range(len(b)):
        while b[j] - b[i] > d:
            proverok = proverok + 1
            i = i + 1
        proverok = proverok + 1
        par = par + (j - i)
    return [par, proverok]

random.seed(4)
for n in [50, 100, 200]:
    a = []
    for k in range(n):
        a.append(random.randint(0, 10000))
    print("n =", n, "| пар, проверок:", perebor(a, 300),
          "против", dva_ukazatelya(a, 300))

n = 50 | пар, проверок: [77, 1225] против [77, 99]
n = 100 | пар, проверок: [310, 4950] против [310, 195]
n = 200 | пар, проверок: [1109, 19900] против [1109, 391]

Ответы совпадают, проверок у перебора n(n − 1)/2, у двух указателей - меньше 2n. Честности ради: в счётчик не вошла сама сортировка, а это ещё около n log₂ n сравнений - для n = 200 порядка 1500. Итог всё равно n log n против n², и разрыв растёт с каждым удвоением. Повтор был в поиске партнёра «среди всех», и порядок убрал его целиком.

Разбор: максимум в скользящем окне

Для каждого окна из k подряд идущих чисел нужен максимум - например, пик нагрузки за каждые k минут. Наивно каждое окно просматривается с нуля, хотя соседние окна делят k − 1 элемент. Здесь не поможет сортировка - повтор другого рода: перекрывающиеся куски. Лекарство - монотонная очередь: в ней номера кандидатов в максимум, и значения по ним убывают. Новый элемент выталкивает с хвоста всех, кто не больше его: они уже никогда не станут максимумом, пока он в окне. Равных тоже - новый элемент того же значения проживёт в окне дольше, так что максимум не потеряется. Голова очереди - максимум текущего окна; когда она выходит из окна, сдвигаем голову.

import random

def naivno(a, k):
    # максимум каждого окна считаем с нуля
    otvet = []
    proverok = 0
    for s in range(len(a) - k + 1):
        m = a[s]
        for i in range(s, s + k):
            proverok = proverok + 1
            m = max(m, a[i])
        otvet.append(m)
    return [otvet, proverok]

def monotonnaya(a, k):
    # в очереди - номера кандидатов в максимум, значения убывают;
    # голова очереди - максимум текущего окна
    och = []
    golova = 0
    otvet = []
    proverok = 0
    for i in range(len(a)):
        while len(och) > golova and a[och[len(och) - 1]] <= a[i]:
            proverok = proverok + 1
            och.pop()
        och.append(i)
        if och[golova] <= i - k:
            golova = golova + 1
        if i >= k - 1:
            otvet.append(a[och[golova]])
        proverok = proverok + 1
    return [otvet, proverok]

random.seed(9)
a = []
for i in range(300):
    a.append(random.randint(0, 99999))
for k in [10, 50, 100]:
    r1 = naivno(a, k)
    r2 = monotonnaya(a, k)
    print("k =", k, "| совпали:", r1[0] == r2[0], "| проверок наивно:",
          r1[1], "очередью:", r2[1])

k = 10 | совпали: True | проверок наивно: 2910 очередью: 575
k = 50 | совпали: True | проверок наивно: 12550 очередью: 593
k = 100 | совпали: True | проверок наивно: 20100 очередью: 593

Наивный способ платит (n − k + 1) · k и дорожает вместе с окном, пока окно не больше половины списка (дальше окон остаётся мало, и при k = n окно одно). Очередь почти не замечает k: каждый номер входит в неё один раз и выходит не больше одного раза. Счётчик в программе учитывает выталкивания и по одному действию на элемент - меньше 2n при любом окне; проверка головы добавляет ещё не больше n. Счётчики двух программ считают разное - сравнения внутри окна против действий с очередью, - так что сравнивать стоит рост, а не сами числа: наивный растёт с k, очередь стоит на месте.

Одна вольность учебной версии: начало списка och не освобождается. С хвоста номера уходят через pop(), а с головы - нет: голова только сдвигается, и выбывшие номера перед ней остаются в памяти - на 300 числах это неважно, на бесконечном потоке метрик это утечка. В работе берут двустороннюю очередь collections.deque и вынимают голову popleft(): тогда в очереди не больше k номеров.

Граница правила видна в сравнении двух разборов: лекарство зависит от источника повтора. Сортировка, так хорошо сработавшая для пар, здесь бесполезна - она уничтожила бы порядок, в котором и живут окна.

Что ломается без этого

Микрооптимизация вместо структурной. Переписать внутренний цикл наивного окна «побыстрее» - выигрыш в разы. Убрать повтор - выигрыш порядка k раз при окне заметно меньше данных, и он растёт с окном.

Не то лекарство. Отсортировать данные, где важен исходный порядок (окна, последовательности событий), - и ответ становится неверным.

Ускоренное решение без сверки. Два указателя с ошибкой на равных значениях проходят тесты, где равных не было. Перебор рядом ловит это за секунду.

Зачем это в работе

Типичный медленный отчёт - вложенный цикл по двум выгрузкам: «для каждого заказа найти платёж». Это первый источник повтора, и словарь платежей по номеру заказа превращает час в секунды. Мониторинг с «пиком за последние пять минут» по каждой метрике - второй источник, и монотонная очередь делает его дешёвым при любом окне. Перебор при этом не выбрасывается: он остаётся тестом.

Теперь сам

1. Перебор считает, сколько раз каждое слово из списка zapros встречается в списке tekst - для каждого слова запроса просматривает весь текст. Источник повтора и лекарство?
2. Для 10⁵ запросов «сумма элементов с l по r» к неизменному списку из 10⁵ чисел наивный способ складывает отрезок каждый раз. Сколько это сложений в худшем случае и как убрать повтор?
3. Монотонная очередь для окна k = 3 на списке [1, 3, 2, 5, 4]. Какие максимумы окон она выдаст?