Спроектируйте свойства для property-based тестирования функции сортировки с помощью QuickCheck (или Hypothesis): какие инварианты проверять и какие краевые случаи важны
Ниже — набор свойств (инвариантов) и важных краевых случаев для property-based тестирования функции сортировки (QuickCheck / Hypothesis). К каждому свойству — короткое пояснение и пример, что проверять. Общие инварианты - Отсортированность: - Формально: \(\forall i\in\{0,\dots,n-2\}:\ a[i]\le a[i+1]\), где \(a=\mathrm{sort}(x)\). - Проверка: для всех соседних пар в выходном массиве сравнение не нарушается. - Перестановка (сохранение мульти-множества): - Формально: \(\forall v:\ \mathrm{count}(v,x)=\mathrm{count}(v,\mathrm{sort}(x))\). - Пояснение: выход — перестановка входа (ни один элемент не исчез/не добавлен, учесть кратности). - Идемпотентность: - Формально: \(\mathrm{sort}(\mathrm{sort}(x))=\mathrm{sort}(x)\). - Пояснение: повторная сортировка не меняет результат. - Сохранение длины: - Формально: \(|\mathrm{sort}(x)|=|x|\). - Пояснение: длина не должна меняться. - Пара-предикат для компаратора: - Для функции сравнения cmp (возвращающей знак) — проверять, что выход удовлетворяет cmp: \(\forall i:\ \neg(\mathrm{cmp}(a[i+1],a[i])<0)\) (т.е. нет пары, где правый элемент "меньше" левого по cmp). Опциональные свойства (в зависимости от требований) - Стабильность (если требуется стабильный алгоритм): - Формально: если для элементов \(u\) и \(v\) ключи равны и \(u\) предшествует \(v\) в входе, то \(u\) предшествует \(v\) в выходе. - Проверка: сохранить индекс-метку и убедиться, что относительный порядок равных ключей не меняется. - Монотонность относительно монотонной функции: - Формально: для строго возрастающей \(f\): \(\mathrm{sort}(\mathrm{map}(f,x))=\mathrm{map}(f,\mathrm{sort}(x))\). - Пояснение: полезно для проверки корректности работы с key-функциями. Краевые случаи и специальные типы данных - Пустой список и одноэлементный список. - Все элементы одинаковые. - Уже отсортированный и строго обратный (реверс) список. - Дубликаты (много одинаковых значений). - Большие списки (проверить на возможные переполнения/рекурсию). - Комбинация положительных/отрицательных чисел, ноль. - Особые float-значения: \(\mathrm{NaN}\), \(+\infty\), \(-\infty\) — явно задать ожидание поведения (NaN в Python некорректно сравнивается). - Разные типы в коллекции (int/float/str): в Python3 смешанные несравнимые типы должны давать ошибку — тест должен ожидать и проверять исключение или заранее ограничивать генераторы типов. - Неупорядочимые элементы (например объекты без сравнения) — ожидать исключение. - Комбинаторные случаи: very small sizes (0..5), medium, и максимально допустимые длины; включать случайные и специально сконструированные паттерны (выпуклые/вогнутые последовательности, почти отсортированные, periodic). Тесты для поведения API - Чистота/мутация: - Если API не должен менять вход: проверять, что исходный список не изменился. - Если сортировка in-place: проверить, что возвращаемое значение/модификация соответствует спецификации. - Поведение при некорректном компараторе: - Неконсистентный cmp (не транзитивный/не антирефлексивный) — ожидается либо корректная ошибка, либо документированное поведение; проверять, что функция не уходит в бесконечный цикл. - Поведение с параметром key (если есть): - Проверять порядок по ключу и то, что сравнение использует именно ключ, а не исходное значение. Практические рекомендации для генераторов (Hypothesis/QuickCheck) - Генерировать списки разной длины, включая 0,1, маленькие (=1000) для стресс‑тестов. - Включать контролируемый процент повторов и специальных значений (NaN, ±inf). - Для stability: генерировать пары (value, original_index) или обернуть элементы в объекты с индексом. - Убедиться, что генератор типов согласован с ожидаемым поведением (если функция не должна принимать смешанные типы — ограничить стратегию). - Использовать shrink-стратегии, которые сужают до коротких списков и простых значений (это помогает диагностике). Примеры конкретных свойств (короткие формулы) - Отсортированность: \(\forall i\in[0,n-2]: a[i]\le a[i+1]\). - Перестановка: \(\forall v:\ \mathrm{count}(v,x)=\mathrm{count}(v,a)\). - Идемпотентность: \(\mathrm{sort}(\mathrm{sort}(x))=\mathrm{sort}(x)\). - Стабильность: если \(\mathrm{key}(u)=\mathrm{key}(v)\) и \(u\) перед \(v\) в \(x\), то \(u\) перед \(v\) в \(\mathrm{sort}(x)\). Коротко: проверяйте отсортированность + сохранение мульти-множества + идемпотентность (+стабильность, если требуется), тестируйте все краевые случаи (пусто, одноэлементно, дубликаты, NaN/inf, смешанные/несравнимые типы, in-place vs pure API) и подбирайте стратегии генерации/сжатия с учётом этих сценариев.
Общие инварианты
- Отсортированность:
- Формально: \(\forall i\in\{0,\dots,n-2\}:\ a[i]\le a[i+1]\), где \(a=\mathrm{sort}(x)\).
- Проверка: для всех соседних пар в выходном массиве сравнение не нарушается.
- Перестановка (сохранение мульти-множества):
- Формально: \(\forall v:\ \mathrm{count}(v,x)=\mathrm{count}(v,\mathrm{sort}(x))\).
- Пояснение: выход — перестановка входа (ни один элемент не исчез/не добавлен, учесть кратности).
- Идемпотентность:
- Формально: \(\mathrm{sort}(\mathrm{sort}(x))=\mathrm{sort}(x)\).
- Пояснение: повторная сортировка не меняет результат.
- Сохранение длины:
- Формально: \(|\mathrm{sort}(x)|=|x|\).
- Пояснение: длина не должна меняться.
- Пара-предикат для компаратора:
- Для функции сравнения cmp (возвращающей знак) — проверять, что выход удовлетворяет cmp: \(\forall i:\ \neg(\mathrm{cmp}(a[i+1],a[i])<0)\) (т.е. нет пары, где правый элемент "меньше" левого по cmp).
Опциональные свойства (в зависимости от требований)
- Стабильность (если требуется стабильный алгоритм):
- Формально: если для элементов \(u\) и \(v\) ключи равны и \(u\) предшествует \(v\) в входе, то \(u\) предшествует \(v\) в выходе.
- Проверка: сохранить индекс-метку и убедиться, что относительный порядок равных ключей не меняется.
- Монотонность относительно монотонной функции:
- Формально: для строго возрастающей \(f\): \(\mathrm{sort}(\mathrm{map}(f,x))=\mathrm{map}(f,\mathrm{sort}(x))\).
- Пояснение: полезно для проверки корректности работы с key-функциями.
Краевые случаи и специальные типы данных
- Пустой список и одноэлементный список.
- Все элементы одинаковые.
- Уже отсортированный и строго обратный (реверс) список.
- Дубликаты (много одинаковых значений).
- Большие списки (проверить на возможные переполнения/рекурсию).
- Комбинация положительных/отрицательных чисел, ноль.
- Особые float-значения: \(\mathrm{NaN}\), \(+\infty\), \(-\infty\) — явно задать ожидание поведения (NaN в Python некорректно сравнивается).
- Разные типы в коллекции (int/float/str): в Python3 смешанные несравнимые типы должны давать ошибку — тест должен ожидать и проверять исключение или заранее ограничивать генераторы типов.
- Неупорядочимые элементы (например объекты без сравнения) — ожидать исключение.
- Комбинаторные случаи: very small sizes (0..5), medium, и максимально допустимые длины; включать случайные и специально сконструированные паттерны (выпуклые/вогнутые последовательности, почти отсортированные, periodic).
Тесты для поведения API
- Чистота/мутация:
- Если API не должен менять вход: проверять, что исходный список не изменился.
- Если сортировка in-place: проверить, что возвращаемое значение/модификация соответствует спецификации.
- Поведение при некорректном компараторе:
- Неконсистентный cmp (не транзитивный/не антирефлексивный) — ожидается либо корректная ошибка, либо документированное поведение; проверять, что функция не уходит в бесконечный цикл.
- Поведение с параметром key (если есть):
- Проверять порядок по ключу и то, что сравнение использует именно ключ, а не исходное значение.
Практические рекомендации для генераторов (Hypothesis/QuickCheck)
- Генерировать списки разной длины, включая 0,1, маленькие (=1000) для стресс‑тестов.
- Включать контролируемый процент повторов и специальных значений (NaN, ±inf).
- Для stability: генерировать пары (value, original_index) или обернуть элементы в объекты с индексом.
- Убедиться, что генератор типов согласован с ожидаемым поведением (если функция не должна принимать смешанные типы — ограничить стратегию).
- Использовать shrink-стратегии, которые сужают до коротких списков и простых значений (это помогает диагностике).
Примеры конкретных свойств (короткие формулы)
- Отсортированность: \(\forall i\in[0,n-2]: a[i]\le a[i+1]\).
- Перестановка: \(\forall v:\ \mathrm{count}(v,x)=\mathrm{count}(v,a)\).
- Идемпотентность: \(\mathrm{sort}(\mathrm{sort}(x))=\mathrm{sort}(x)\).
- Стабильность: если \(\mathrm{key}(u)=\mathrm{key}(v)\) и \(u\) перед \(v\) в \(x\), то \(u\) перед \(v\) в \(\mathrm{sort}(x)\).
Коротко: проверяйте отсортированность + сохранение мульти-множества + идемпотентность (+стабильность, если требуется), тестируйте все краевые случаи (пусто, одноэлементно, дубликаты, NaN/inf, смешанные/несравнимые типы, in-place vs pure API) и подбирайте стратегии генерации/сжатия с учётом этих сценариев.