От просьбы к спецификации: вход, выход и что значит «лучше»

Если ты привык уточнять вход, вид ответа и критерий до первой строки кода, листай до «Теперь сам».

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

Безопасник просит: «Найди пользователей, которые заходят слишком часто - больше четырёх раз за час». Вот журнал за утро, минуты от полуночи:

ann: 5, 20, 40, 59
bob: 10, 55, 57, 58, 61, 64

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

Если «за час» - это календарный час с 0:00 до 0:59, у Боба там четыре входа (10, 55, 57, 58) и ещё два в следующем часе: никто не нарушил. Если «за час» - любые шестьдесят минут подряд, то с 10-й по 69-ю минуту у Боба шесть входов: нарушитель. Оба толкования честные, а ответы разные. Программа, написанная по одному из них, будет «правильной» и при этом не той, что нужна.

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

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

Механизм: пять вопросов к любой просьбе

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

1. Из чего состоит вход? Какие объекты (числа, строки, пары, события со временем), есть ли повторы, упорядочен ли он, что гарантируется (предусловие).
2. Какой вид ответа? Здесь четыре разные задачи прячутся за одной фразой: - есть ли такой объект - ответ «да» или «нет»; - сколько их - одно число; - все такие объекты - список, и он может быть огромным; - лучший объект по какому-то критерию - и тогда нужен сам критерий.
3. Что значит «лучше»? Минимизировать что - сумму, максимум, число шагов? При равенстве какой брать? Нужен ли точный оптимум, или устроит почти лучший - и насколько «почти»? Это записывают числом в постусловие: «сумма не больше чем на 5% выше оптимума». Оптимум при этом обычно неизвестен, и обещание проверяют либо через доказанную нижнюю границу оптимума (так устроены приближённые алгоритмы раздела 22), либо перебором на маленьких входах.
4. Каков размер? Десять элементов, тысяча или миллиард - от этого зависит, какой алгоритм вообще допустим (следующий урок).
5. Какие края? Пустой вход, один элемент, все одинаковые, касающиеся интервалы, равные времена.

Каждый ответ ты записываешь в спецификацию: вход и предусловие, выход, постусловие. Вопрос без ответа - это место, где две программы разойдутся.

Правило

Прежде чем выбирать алгоритм, запиши вход, вид ответа (есть ли / сколько / все / лучший), критерий «лучше» и размер. Если на какой-то вопрос нет ответа - задай его заказчику; если заказчика нет - выбери толкование явно и напиши его в спецификации.

Разбор: два толкования «слишком часто»

Запишем оба толкования из начала урока как программы - это и есть спецификации, только исполняемые.

# журнал входов: [пользователь, минута от полуночи]
zhurnal = [["ann", 5], ["bob", 10], ["ann", 20], ["bob", 55],
           ["bob", 57], ["bob", 58], ["ann", 40], ["bob", 61],
           ["bob", 64], ["ann", 59]]
K = 4      # «слишком часто» - больше K входов
W = 60     # за W минут

def po_chasam(zhurnal):
    # толкование 1: календарные часы 0:00-0:59, 1:00-1:59, ...
    schet = {}
    for z in zhurnal:
        klyuch = z[0] + " в час " + str(z[1] // 60)
        schet[klyuch] = schet.get(klyuch, 0) + 1
    plohie = []
    for klyuch, n in sorted(schet.items()):
        if n > K:
            plohie.append(klyuch)
    return plohie

def skolzyashchee(zhurnal):
    # толкование 2: любое окно [t, t + W), где t - время какого-то входа
    vremena = {}
    for z in zhurnal:
        if z[0] not in vremena:
            vremena[z[0]] = []
        vremena[z[0]].append(z[1])
    plohie = []
    for imya, t in sorted(vremena.items()):
        t.sort()
        levyj = 0
        for pravyj in range(len(t)):
            while t[pravyj] - t[levyj] >= W:
                levyj = levyj + 1
            if pravyj - levyj + 1 > K:
                plohie.append(imya + " с минуты " + str(t[levyj]))
                break
    return plohie

# первое толкование отвечает парами «пользователь, час»,
# второе - пользователем и началом окна: даже вид ответа разный
print("по календарным часам:", po_chasam(zhurnal))
print("скользящим окном:    ", skolzyashchee(zhurnal))

по календарным часам: []
скользящим окном:     ['bob с минуты 10']

Обе программы правильные - каждая для своей задачи. Заметь, что второе толкование потребовало ещё двух решений, которых просьба не содержала: окно полуоткрытое (t[pravyj] - t[levyj] >= W выталкивает вход, случившийся ровно через 60 минут), а окна начинаются только в моменты входов. Второе не меняет списка нарушителей (хотя начало окна программа называет по первому входу в нём, а не по самой ранней минуте): если в каком-то окне больше K входов, то в окне, начатом с первого из них, их не меньше. Но это надо было заметить и записать, а не получить случайно.

Что с этим делать на практике? Спросить. Вопрос «календарный час или любые 60 минут?» занимает одну строку в переписке, а неверный ответ на него - переписанный модуль и пропущенная атака.

Разбор: одна фраза - четыре задачи разной цены

«Найди пары чисел с суммой 11». В списке двести случайных чисел от 1 до 10; пара - это две позиции i < j, и равные числа на разных позициях дают разные пары. Посмотрим, что стоит каждый вид ответа.

import random

random.seed(7)
a = []
for i in range(200):
    a.append(random.randint(1, 10))
S = 11

# 1. есть ли пара с суммой S: хватит множества виденных
vidennye = set()
shagov = 0
est = False
for x in a:
    shagov = shagov + 1
    if S - x in vidennye:
        est = True
        break
    vidennye.add(x)
print("есть ли:   ", est, "- просмотрено", shagov, "чисел")

# 2. сколько пар: счётчики значений, ответ - одно число;
#    x образует пару с каждым уже встреченным S - x, по одной на каждого
schet = {}
par = 0
for x in a:
    par = par + schet.get(S - x, 0)
    schet[x] = schet.get(x, 0) + 1
print("сколько:   ", par, "- просмотрено", len(a), "чисел")

# 3. все пары: ответ сам по себе такой длины
vse = []
for j in range(len(a)):
    for i in range(j):
        if a[i] + a[j] == S:
            vse.append([i, j])
print("все пары:  ", len(vse), "пар в ответе")

# 4. ближайшая сумма, если точной нет: сортировка и два указателя
b = sorted(a)
i = 0
j = len(b) - 1
luchshaya = b[0] + b[1]
# ответ «лучший объект» - сама пара, а не только её сумма
para = [b[0], b[1]]
while i < j:
    s = b[i] + b[j]
    if abs(s - 22) < abs(luchshaya - 22):
        luchshaya = s
        para = [b[i], b[j]]
    if s < 22:
        i = i + 1
    else:
        j = j - 1
print("ближе к 22:", luchshaya, "=", para[0], "+", para[1])

есть ли:    True - просмотрено 6 чисел
сколько:    1969 - просмотрено 200 чисел
все пары:   1969 пар в ответе
ближе к 22: 20 = 10 + 10

«Есть ли» закончился на шестом числе: 2 и 9 нашлись быстро. «Сколько» прошёл весь список один раз и выдал одно число. «Все пары» - другая порода: в ответе 1969 пар, и никакой алгоритм не выпишет их быстрее, чем за 1969 действий. Размер ответа - нижняя граница времени, и если в списке из миллиона чисел пар много, этот ответ не поместится в память, сколько ни оптимизируй поиск. Четвёртый вид появляется, когда точного ответа может не быть: суммы 22 у чисел до 10 нет, и честная спецификация говорит, что тогда вернуть.

Граница правила «уточни вид ответа»: иногда заказчик сам не знает, что ему нужно, пока не увидит число. Тогда начинают с самого дешёвого вида - «есть ли» или «сколько» - и только потом решают, нужен ли список.

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

Оптимизируешь не ту задачу. Неделя на быстрый подсчёт пар, а нужен был список - или наоборот.

Ответ не помещается. «Все пары похожих документов» на миллионе документов - это до 500 миллиардов пар. Узнать это до написания кода стоит одной строки арифметики.

Тихое расхождение на краях. Касающиеся интервалы, равные времена, пустой вход: тесты проходят, а в бою отчёт расходится с соседним отделом, который считал по-другому.

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

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

Теперь сам

1. Просьба: «найди самый популярный товар за неделю». Назови три вопроса, без ответа на которые программу писать нельзя.
2. В списке из 10⁶ чисел все числа равны 5, S = 10. Сколько пар с суммой 10? Можно ли вывести их все?
3. Для журнала из урока: K = 3, W = 60. Кто нарушитель по календарным часам, кто - по скользящему окну?