Property‑based testing — подход, в котором вместо набора конкретных примеров (unit‑тестов) вы описываете свойства (инварианты) функции, а фреймворк (QuickCheck, Hypothesis) автоматически генерирует много случайных входов и пытается найти контрпример. При ошибке фреймворк обычно выполняет «shrinking» — упрощает вход до минимального воспроизводимого случая.
Типичные свойства для функции сортировки:
- Отсортированность: для результата $s=\mathrm{sort}(xs)$ выполняется
$$\forall i\in [0,|s|-2]:s_i\le s_{i+1}.$$ - Сохранение содержимого (перестановка / равенство мультимножеств):
$$\mathrm{multiset}(s)=\mathrm{multiset}(xs)\text{или}\forall v:\mathrm{count}(v,s)=\mathrm{count}(v,xs).$$ - Идемпотентность:
$$\mathrm{sort}(\mathrm{sort}(xs))=\mathrm{sort}(xs).$$ - Сохранение длины:
$$|s|=|xs|.$$
Пример (псевдо‑Python с Hypothesis):
from hypothesis import given, strategies as st
from collections import Counter
@given(st.lists(st.integers()))
def test_sort_properties(xs):
s = my_sort(xs)
# 1) отсортированность
assert all(s[i] <= s[i+1] for i in range(len(s)-1))
# 2) мультимножества совпадают
assert Counter(s) == Counter(xs)
# 3) идемпотентность
assert my_sort(s) == s
Как генерация случайных данных помогает находить баги, не покрытые unit‑тестами:
- Покрывает неожиданные комбинации входов: пустые списки, одноэлементные, длинные, с большим количеством дубликатов, с отрицательными/положительными/крайними значениями.
- Находит краевые случаи и редкие сценарии, которые разработчик не подумал включить в фиксированные тесты (напр., повторяющиеся элементы, порядок уже отсортированного или строго убывающего списка).
- Выявляет ошибки логики (пропуск элементов, потеря дубликатов) через проверку мультимножеств; выявляет нарушения упорядоченности через свойство отсортированности.
- Обнаруживает проблемы с некорректным компаратором или нестабильной реализацией: случайные входы чаще проявляют несогласованность сравнений.
- Автоматическое сжатие (shrinking) приводит к минимальному воспроизводимому контрпримеру, что облегчает отладку.
В итоге property‑based testing масштабирует покрытие тестами: вместо ручного перечисления примеров вы формулируете общие свойства, а генератор ишёт широкое пространство входов и находит неожиданные ошибки.