Юнит-тестирование распределения вероятностей с помощью условных выражений

Question

У меня есть функция choose(elems) -> elem, которая вызывает rand(), что делает ее недетерминированной.

Чтобы лучше это проверить, я подумал, что можно разделить эту функцию на две части,

generate_choices(elems, ...) -> distribution
choose(distribution) -> elem

где choose() - это тонкая оболочка вокруг rand(), а generate_choices() создает распределение, из которого можно нарисовать элемент. Затем я могу детерминистически проверить, что это распределение вероятностей соответствует ожидаемому.

Распределение равномерно , но с двумя условиями:

1. Если не хватает elems, добавьте случайный запасной элемент равномерно.
2. Если все еще недостаточно elems, добавьте случайный элемент по умолчанию равномерно.

Некоторые примеры:

generate_choices([a, b, c, d], [], []) -> [a, b, c, d]
generate_choices([a, b, c], [fallback1], []) -> [a, b, c, fallback1]
generate_choices([a, b, c], [fb1, fb2], []) -> [a, b, c, (fb1 | fb2)]
generate_choices([a, b], [fb1, fb2], [default1]) -> [a, b, (fb1 | fb2), default1]
generate_choices([a, b], [fb1, fb2], [d1, d2]) -> [a, b, (fb1 | fb2), (d1 | d2) ]
generate_choices([a], [fb1, fb2], [d1, d2]) -> [a, (fb1|fb2), (d1|d2) ]

Мой вопрос: как мне моделировать distribution?

• Если я выберу простой список и вызову rand() из generate_choices(), чтобы заполнить отступление и по умолчанию , тогда я могу проверить только некоторые детерминированные части generate_choices() .
• Если я выберу три списка, (elems, fallback, default), тогда generate_choices() будет полностью детерминированным, но тогда choice() станет менее тривиальным и в любом случае должен быть проверен более тщательно.

Answer 1

Существует как минимум два способа проверки функций, использующих случайные числа.Возможно, вы захотите провести оба вида теста.

(1) Один из них - установить начальное состояние генератора случайных чисел, сгенерировать несколько примеров и проверить путем проверки, что эти примеры верны.Затем поместите эти примеры в тестовый сценарий в качестве ожидаемого результата и задайте то же начальное состояние в начале сценария.

(2) Другой тип теста - создание большого количества примеров и проверка его наВ среднем примеры удовлетворяют ожидаемым свойствам.Это недетерминированный тест, поскольку возможно, что для некоторых последовательностей, сгенерированных генератором случайных чисел, тест не пройден.Вы должны будете принять небольшую вероятность неудачи;хорошая новость заключается в том, что вы можете сделать вероятность достаточно малой, протестировав большое количество примеров и сделав допуск для теста достаточно большим.

(2a) Например, в простейшем случае, который вы даете, вводявляется последовательностью, а результат является перестановкой этой последовательности.Если вы генерируете большое количество примеров, вы должны обнаружить, что все перестановки имеют одинаковую частоту в пределах некоторого допуска.Очевидно, что этот тест ограничен длиной входных данных теста, поскольку их n!перестановки входа длины n.

Вы можете получить допуск, учитывая распределение пропорций каждой отдельной перестановки.Каждая перестановка имеет вероятность 1 / n !, и ожидаемое число каждой из них (m раз 1 / n!), Где m - это число сгенерированных перестановок.Дисперсия числа каждой перестановки составляет (m раз 1 / n! Раз (1 - 1 / n!)), И стандартное отклонение является квадратным корнем из этого.Вы можете приблизить интервал допуска как (ожидаемое число плюс или минус кратное стандартному отклонению).Вы можете получить более точный интервал, рассмотрев распределение более тщательно.

(2b) Другой способ проверить перестановки - посмотреть, сколько раз первый элемент выходных данных равен первому элементу входных данных., первый элемент вывода равен второму элементу ввода, первый элемент ввода равен третьему элементу ввода, ..., второму элементу ввода, ..., третьему элементу, ... последнему элементу ввода.Это может быть осуществимо для более длинных последовательностей, чем тест 2a.Опять же, игра состоит в том, чтобы выяснить распределение ожидаемых чисел в каждом бине и вывести из этого допуск.