Маленький пример руками и перебор как исполняемая спецификация

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

Как думаешь, какой здесь ответ

Задача: найти наибольшую сумму подотрезка - куска из идущих подряд элементов списка. Для [2, -1, 3] ответ 4, это весь список. А для [-2, -3, -1]?

Ответь себе до чтения. Если подотрезок может быть пустым, его сумма 0 - и это лучше любой отрицательной суммы: ответ 0. Если подотрезок обязан содержать хотя бы один элемент - ответ −1. В общей формулировке этого вопроса не видно; на трёх отрицательных числах он вылезает сам.

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

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

Механизм: три шага до быстрого алгоритма

Скиена в списке вопросов разработчика ставит этот пункт рядом с «из чего состоит вход»: могу ли я придумать вход настолько маленький, чтобы решить его вручную, и что будет, если попробую? Из этого вырастают три шага:

1. Пример руками. Три-пять элементов, ответ на бумаге. Каждое «а если…» записывается вопросом к спецификации.
2. Перебор по определению. Программа, которая перебирает ВСЕ кандидаты на ответ и проверяет каждый буквально по условию. Она медленная - n³, 2ⁿ, неважно, - зато мест для ошибки в ней мало: нет ни одной идеи, только определение. Ошибиться можно в самом определении и в границах перебора - пример в конце урока.
3. Список краёв. Пустой вход, один элемент, все одинаковые, все отрицательные, касание, равные ключи, наибольший размер. Каждый край прогоняется через перебор, и его ответ записывается как решение спецификации.

Перебор - это спецификация, которую можно запустить. С ним сверяют каждое следующее, быстрое решение: на маленьких входах они обязаны совпадать. Как это делать на тысячах входов автоматически - тема урока о стресс-тестеРазбирается в разделе 26, глава «Инженерия алгоритмов и проверка результата»: Стресс-тест: быстрое решение против перебора на тысячах маленьких входов.

Правило

Сначала реши руками вход из трёх-пяти элементов, потом напиши перебор, который буквально следует определению ответа, потом прогони через него края. Быстрый алгоритм пишется последним и сверяется с перебором. Если быстрый и перебор расходятся на крае, сначала реши, какое толкование верное, - это вопрос к спецификации, а не к коду.

Разбор: пустой подотрезок

Перебор по определению: все пары границ i < j, сумма между ними, наибольшая. Рядом быстрый алгоритм Кадане за один проход. Его идея: держать лучшую сумму подотрезка, который кончается на текущем элементе, а если все такие суммы отрицательны - взять пустой подотрезок с суммой 0. Для следующего элемента есть два варианта - продолжить подотрезок или начать заново с пустого; продолжать выгодно, только если накопленная сумма положительна. Отсюда max(0, tekushchaya + x). Запомни слово «пустого» - под выводом оно окажется главным.

def perebor(a, pustoj_mozhno):
    # определение буквально: перебрать все подотрезки a[i:j]
    kandidaty = []
    if pustoj_mozhno:
        kandidaty.append(0)           # сумма пустого подотрезка
    for i in range(len(a)):
        for j in range(i + 1, len(a) + 1):
            s = 0
            for k in range(i, j):
                s = s + a[k]
            kandidaty.append(s)
    if len(kandidaty) == 0:
        return "нет ответа"
    return max(kandidaty)

def kadane(a):
    # быстрый: лучшая сумма, кончающаяся здесь; начинает с нуля
    luchshaya = 0
    tekushchaya = 0
    for x in a:
        tekushchaya = max(0, tekushchaya + x)
        luchshaya = max(luchshaya, tekushchaya)
    return luchshaya

for a in [[2, -1, 3], [-2, 5, -1, 2, -6, 4], [-2, -3, -1], [], [7]]:
    s_pustym = perebor(a, True)
    bez_pustogo = perebor(a, False)
    print(a, "с пустым:", s_pustym, "без пустого:", bez_pustogo,
          "Кадане:", kadane(a))

[2, -1, 3] с пустым: 4 без пустого: 4 Кадане: 4
[-2, 5, -1, 2, -6, 4] с пустым: 6 без пустого: 6 Кадане: 6
[-2, -3, -1] с пустым: 0 без пустого: -1 Кадане: 0
[] с пустым: 0 без пустого: нет ответа Кадане: 0
[7] с пустым: 7 без пустого: 7 Кадане: 7

На обычных входах все три сходятся, и по ним не понять, что Кадане в таком виде решает задачу «с пустым подотрезком». Это видно только на крае: на [-2, -3, -1] он отвечает 0, а по второму толкованию нужно −1. Ни одна из программ не ошибается - ошибкой было бы не заметить, что их две. Если по спецификации пустой подотрезок запрещён, Кадане чинится в две строки: tekushchaya = max(x, tekushchaya + x) вместо обрезки нулём и luchshaya со стартом a[0], а пустой вход объявляется недопустимым в предусловии.

Разбор: касаются ли встречи

Сколько нужно переговорок, если встречи 9:00-10:00, 10:00-11:00 и 11:40-12:00? Перебор по определению: в каждый момент дня посчитать, сколько встреч идёт, и взять наибольшее. Что меньше этого числа комнат не хватит, видно сразу; что его всегда хватает - есть способ рассадить встречи ровно по стольким комнатам - докажет следующий урокРазбирается в разделе 26, глава «Как читать задачу и как её переформулировать»: Переформулировка: перестановка, подмножество, граф или интервалы. Быстрый алгоритм - заметание: отсортировать начала и концы как события и пройти их по времени, держа счётчик идущих встреч.

def perebor(vstrechi, poluotkrytye):
    # в каждый момент t (шаг полминуты) считаем, сколько встреч идёт
    luchshee = 0
    t = 0
    while t <= 24 * 60:
        idet = 0
        for v in vstrechi:
            if poluotkrytye:
                vnutri = v[0] <= t and t < v[1]
            else:
                vnutri = v[0] <= t and t <= v[1]
            if vnutri:
                idet = idet + 1
        luchshee = max(luchshee, idet)
        t = t + 0.5
    return luchshee

def zametanie(vstrechi, konec_ran_she):
    # события [время, тип]; списки сортируются по первому элементу,
    # при равенстве - по второму, поэтому меньший тип идёт раньше
    if konec_ran_she:
        tip_nachala = 1
    else:
        tip_nachala = 0
    sobytiya = []
    for v in vstrechi:
        sobytiya.append([v[0], tip_nachala])
        sobytiya.append([v[1], 1 - tip_nachala])
    sobytiya.sort()
    idet = 0
    luchshee = 0
    for s in sobytiya:
        if s[1] == tip_nachala:
            idet = idet + 1
        else:
            idet = idet - 1
        luchshee = max(luchshee, idet)
    return luchshee

# 9:00-10:00, 10:00-11:00 и 11:40-12:00, минуты от полуночи
vstrechi = [[540, 600], [600, 660], [700, 720]]
print("перебор, [начало, конец):  ", perebor(vstrechi, True))
print("перебор, [начало, конец]:  ", perebor(vstrechi, False))
print("заметание, конец раньше:   ", zametanie(vstrechi, True))
print("заметание, начало раньше:  ", zametanie(vstrechi, False))

перебор, [начало, конец):   1
перебор, [начало, конец]:   2
заметание, конец раньше:    1
заметание, начало раньше:   2

Здесь толкование спрятано ещё глубже - в порядке сортировки событий с одинаковым временем. Если в 10:00 сначала обработать конец первой встречи, а потом начало второй, хватит одной комнаты; если наоборот - алгоритм на мгновение насчитает две. Ни в описании заметания, ни в коде нет слова «касание», а решение принято. Перебор по моментам делает толкование явным: полуоткрытый интервал [начало, конец) или замкнутый [начало, конец]. В жизни встречи обычно полуоткрытые - из одной переговорки в 10:00 выходят, а другие входят.

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

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

Расхождение на крае, найденное в бою. Отчёт говорит «нужно 5 комнат», бронирование видит 4: один считал касание пересечением, другой нет.

Спор без судьи. Два разработчика с двумя быстрыми решениями спорят, чей ответ верен. Без перебора по определению спор не решается - нечем проверить.

Пустой вход роняет сервис. max([]) в Python - исключение. Ручной пример на пустом входе стоит секунду.

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

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

Теперь сам

1. Для [3, -5, 4, -1, 2, -8, 1] найди руками наибольшую сумму подотрезка.
2. Встречи [9:00, 9:30), [9:30, 10:00), [9:15, 9:45). Сколько комнат нужно? Что ответит заметание, если начала обрабатывать раньше концов?
3. Назови три края для задачи «найти медиану списка».