Стресс-тест: быстрое решение против перебора на тысячах маленьких входов

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

Как думаешь, найдут ли тесты ошибку

Функция проверяет, есть ли в списке два элемента с суммой s: сортирует и идёт двумя указателями с концов. В ней ошибка - условие цикла i <= j вместо i < j. Автор прогнал её на 2000 случайных списках со случайными числами до миллиарда, сверяя с перебором. Сколько расхождений он увидит?

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

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

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

Механизм: генератор, эталон, сравнение

Рецепт из раздела 14 («перебрать все маленькие входы и сравнить с точным алгоритмом») работает для любого алгоритма, не только жадного. Деталей четыре:

1. Эталон - перебор по определению из урока о маленьком примере. Он медленный, поэтому входы маленькие.
2. Генератор - выдаёт входы, а не ответы: длина 0-5, значения из короткого диапазона. Короткий диапазон - главное: он делает частыми совпадения, равенства и границы.
3. Сравнение - на каждом входе ответы быстрого и эталона. Первое расхождение останавливает прогон и печатает вход.
4. Полный перебор маленьких входов - если входов немного, лучше перебрать их все: тогда отсутствие расхождений - доказательство корректности на всей этой области, а не удача.

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

Правило

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

Разбор: диапазон значений решает

Функция с ошибкой и перебор. Один и тот же стресс-тест, три диапазона значений. Спецификация функции: список натуральных чисел (от 1) и натуральное s. Генератор выдаёт входы ровно из этой области; если бы условие допускало ноль и отрицательные, их обязан был бы выдавать и генератор - иначе этот край остался бы непроверенным.

import random

def est_para_bystro(a, s):
    # два указателя по отсортированной копии:
    # есть ли i < j, у которых a[i] + a[j] == s
    b = sorted(a)
    i = 0
    j = len(b) - 1
    while i <= j:
        t = b[i] + b[j]
        if t == s:
            return True
        if t < s:
            i = i + 1
        else:
            j = j - 1
    return False

def est_para_perebor(a, s):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == s:
                return True
    return False

def stress(verh, popytok):
    # случайные маленькие входы: длина 1-5, значения 1..verh;
    # пустой список - один вход, его проверяет полный перебор ниже
    for k in range(1, popytok + 1):
        n = random.randint(1, 5)
        a = []
        for i in range(n):
            a.append(random.randint(1, verh))
        s = random.randint(2, 2 * verh)
        if est_para_bystro(a, s) != est_para_perebor(a, s):
            return [k, a, s]
    return [popytok, "расхождений нет"]

random.seed(1)      # закреплено: прогон повторяется попытка в попытку
print("значения до 10⁹:", stress(10 ** 9, 2000))
print("значения до 10: ", stress(10, 2000))
print("значения до 3:  ", stress(3, 2000))

значения до 10⁹: [2000, 'расхождений нет']
значения до 10:  [4, [6, 4, 2, 7], 12]
значения до 3:   [3, [3, 2, 2, 2], 6]

При числах до миллиарда 2000 попыток прошли чисто: событие «s равно удвоенному элементу» почти не случается. Числа до 10 дали расхождение на четвёртой попытке: в [6, 4, 2, 7] нет пары с суммой 12, но указатели сошлись на шестёрке и сложили её с собой. Числа до 3 - на третьей. Количество попыток не заменяет диапазона. Оценим: в списке в среднем три числа (длина от 1 до 5), и событие «s ровно вдвое больше одного из них» при s до 2 · 10⁹ случается с вероятностью около 3 / (2 · 10⁹). Даже миллион попыток находит его примерно в одном прогоне из семисот.

Разбор: полный перебор маленькой области

Случайный генератор нашёл ошибку, но не гарантирует, что найдёт. Если область маленькая, её можно перебрать целиком: все списки длиной до 3 из чисел 1-3 и все s от 2 до 6.

def est_para_bystro(a, s):
    b = sorted(a)
    i = 0
    j = len(b) - 1
    while i <= j:
        t = b[i] + b[j]
        if t == s:
            return True
        if t < s:
            i = i + 1
        else:
            j = j - 1
    return False

def est_para_perebor(a, s):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == s:
                return True
    return False

def vse_spiski(n, verh):
    # все списки длины n со значениями 1..verh
    if n == 0:
        return [[]]
    out = []
    for hvost in vse_spiski(n - 1, verh):
        for x in range(1, verh + 1):
            out.append(hvost + [x])
    return out

vhodov = 0
plohih = []
for n in range(0, 4):
    for a in vse_spiski(n, 3):
        for s in range(2, 7):
            vhodov = vhodov + 1
            if est_para_bystro(a, s) != est_para_perebor(a, s):
                plohih.append([a, s])
print("входов проверено:", vhodov, "| с расхождением:", len(plohih))
print("первые:", plohih[:4])

входов проверено: 200 | с расхождением: 45
первые: [[[1], 2], [[2], 4], [[3], 6], [[1, 2], 2]]

Двести входов, сорок пять расхождений - и самое маленькое из них: список [1] и s = 2. Один элемент, и функция «находит» пару. Такой контрпример объясняет ошибку сам: пары из одного элемента не бывает, значит, функция складывает элемент с собой, значит, условие i <= j неверно. Граница правила: полный перебор доказывает корректность только внутри перебранной области. Если ошибка срабатывает лишь на списках длиннее трёх или на числах больше трёх, этот прогон её не увидит - поэтому область выбирают так, чтобы в неё попадали все ветви кода и все значимые соотношения значений: равенства, удвоения, касания. Ветви - необходимое условие, но не достаточное: ошибку, которая живёт только на больших числах (переполнение на границе типа, потеря точности), маленькая область не содержит, и для неё пишут отдельный тест на этой границе.

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

Тесты из головы автора. Автор проверяет то, о чём подумал, а ошибка живёт там, о чём не подумал.

Большие случайные входы. Расхождение есть, но вход из тысячи чисел - и непонятно, что в нём виновато.

Широкий диапазон значений. Совпадений нет, края не встречаются, ошибки равенств не видны. 2000 чистых попыток создают ложное спокойствие.

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

Перед тем как заменить медленную, но проверенную функцию быстрой, их прогоняют стресс-тестом друг против друга - старая становится эталоном. Так проверяют оптимизацию SQL-запроса (старый запрос против нового на случайных маленьких таблицах), новую реализацию сортировки, кеш поверх медленного вычисления. Библиотеки вроде Hypothesis для Python генерируют входы и уменьшают найденный контрпример за тебя, но что сравнивать - свойство - пишешь ты сам, и выбор области - какие длины и диапазоны - остаётся твоим.

Теперь сам

1. Быстрая функция ищет медиану, медленная сортирует и берёт середину. Какой генератор ты напишешь?
2. Стресс-тест 10 000 раз не нашёл расхождений на списках длины 100 со значениями до 10⁶. Что изменить в первую очередь?
3. Сколько входов в полном переборе «все списки длины до 4 из чисел 1-3»?