Рассмотрим метод случайного перемешивания элементов в массиве. Как бы вы написали простой, но надежный модульный тест, чтобы убедиться, что он работает?
У меня есть две идеи, каждая из которых имеет заметные недостатки:
- Перемешайте массив, затем убедитесь, что его порядок отличается от предыдущего. Это звучит хорошо, но терпит неудачу, если случайное перемешивание происходит в том же порядке. (Невероятно, но возможно.)
- Перемешайте массив с постоянным начальным числом и сравните его с заранее заданным выводом. Это зависит от случайной функции, всегда возвращающей одинаковые значения при одинаковом начальном числе. Однако иногда это неверное предположение .
Рассмотрим вторую функцию, которая имитирует броски костей и возвращает случайное число. Как бы вы протестировали эту функцию? Как бы вы проверили эту функцию ...
- никогда не возвращает число за пределами указанных границ?
- возвращает числа в правильном распределении? (Униформа для одного кубика, нормальная для большого количества кубиков.)
Я ищу ответы, дающие представление о тестировании не только этих примеров, но и случайных элементов кода в целом. Являются ли модульные тесты даже правильным решением здесь? Если нет, то какие это тесты?
Просто чтобы облегчить всем разум, я не пишу свой собственный генератор случайных чисел.
testing
unit-testing
random
dlras2
источник
источник
Ответы:
Я не думаю, что юнит-тесты - это правильный инструмент для проверки случайности. Модульный тест должен вызывать метод и проверять возвращаемое значение (или состояние объекта) относительно ожидаемого значения. Проблема с проверкой случайности заключается в том, что для большинства вещей, которые вы хотите проверить, нет ожидаемого значения. Вы можете проверить с данным семенем, но это только проверяет повторяемость . Это не дает вам никакого способа измерить, насколько случайным является распределение, или если оно вообще случайное.
К счастью, есть много статистических тестов, которые вы можете запустить, например Diehard Battery of Tests of Randomness . Смотрите также:
Как выполнить модульное тестирование генератора псевдослучайных чисел?
Модульное тестирование с функциями, которые возвращают случайные результаты
Модульное тестирование Случайность - это вики-статья, в которой рассказывается о многих проблемах, уже затронутых при попытке проверить то, что по своей природе не повторяется. Один интересный момент, который я извлек из этого, был следующим:
источник
1. Модульный тест вашего алгоритма
По первому вопросу я бы построил фальшивый класс, в котором вы кормите последовательность случайных чисел, для которых вы знаете результат своего алгоритма. Таким образом вы убедитесь, что алгоритм, который вы строите поверх своей случайной функции, работает. Так что-то вроде:
2. Проверьте, имеет ли смысл ваша случайная функция
К модульному тесту вы должны добавить тест, который запускается несколько раз и утверждает, что результаты
2
прибавку от 10% до 20% (1/6 = 16,67%) от время с учетом того что ты его 1000 раз прокатил).3. Интеграционный тест для алгоритма и случайной функции
Как часто вы ожидаете, что ваш массив сортируется в исходной сортировке? Сортируйте пару сотен раз и утверждайте, что только в x% случаев сортировка не меняется.
На самом деле это уже интеграционный тест, вы тестируете алгоритм вместе со случайной функцией. Как только вы используете реальную случайную функцию, вы больше не сможете избежать одиночных тестовых прогонов.
Из опыта (я написал генетический алгоритм) я бы сказал, что объединение модульного теста вашего алгоритма, теста распределения вашей случайной функции и интеграционного теста - это путь.
источник
Один аспект PRNG, о котором кажется забытым, заключается в том, что все его свойства являются статистическими по своей природе: нельзя ожидать, что перетасовка массива приведет к перестановке, отличной от той, с которой вы начали. По сути, если вы используете обычный PRNG, единственное, что вам гарантировано, это то, что он не использует простой шаблон (надеюсь) и что он имеет равномерное распределение по набору чисел, который он возвращает.
Правильный тест для PRNG будет включать в себя его запуск не менее 100 раз, а затем проверку распределения выходных данных (что является прямым ответом на вторую часть вопроса).
Ответ на первый вопрос почти одинаков: выполните тест около 100 раз с {1, 2, ..., n} и посчитайте, сколько раз каждый элемент находился в каждой позиции. Все они должны быть примерно равны, если метод случайного выбора хорош.
Совсем другое дело, как тестировать PRNG-решения криптографического уровня. Это вопрос, в котором вам, вероятно, не стоит останавливаться, если вы действительно не знаете, что делаете. Известно, что люди уничтожают (читай: открывают катастрофические дыры) хорошие криптосистемы с помощью всего лишь нескольких «оптимизаций» или тривиальных правок.
РЕДАКТИРОВАТЬ: Я полностью перечитал вопрос, главный ответ и мой собственный. Пока мои замечания остаются в силе, я поддержу ответ Билла Ящерицы. Модульные тесты являются булевыми по своей природе - они либо терпят неудачу, либо успешно, и поэтому не подходят для проверки того, «насколько хороши» свойства PRNG (или метода, использующего PRNG), поскольку любой ответ на этот вопрос будет количественным , а не полярный.
источник
Здесь есть две части: тестирование рандомизации и тестирование вещей, которые используют рандомизацию.
Проверка рандомизации относительно проста. Вы проверяете, что период генератора случайных чисел соответствует ожидаемому (для нескольких выборок, использующих несколько случайных начальных чисел, в пределах некоторого порога), и что распределение выходных данных по большому размеру выборки соответствует ожидаемому. это должно быть (в пределах некоторого порога).
Тестирование вещей, использующих рандомизацию, лучше всего проводить с помощью детерминированного генератора псевдослучайных чисел. Поскольку выходные данные рандомизации известны на основе начального числа (его входных данных), то вы можете выполнить модульное тестирование как обычно на основе входных данных против ожидаемых выходных данных. Если ваш ГСЧ не является детерминированным, то смоделируйте его с помощью детерминированного (или просто не случайного). Протестируйте рандомизацию отдельно от кода, который ее потребляет.
источник
Пусть он запускается несколько раз и визуализирует ваши данные .
Вот пример случайного воспроизведения из Coding Horror , вы можете увидеть, что алгоритм в порядке или нет:
Легко видеть, что каждый возможный элемент возвращается по крайней мере один раз (границы в порядке) и что распределение в порядке.
источник
Общие указатели, которые я нашел полезными при работе с кодом, который принимает случайный ввод: проверьте граничные случаи ожидаемой случайности (значения max и min, а также значения max + 1 и min-1, если применимо). Проверьте места (в, выше и ниже), где числа имеют точки перегиба (т.е. -1, 0, 1 или больше 1, меньше 1 и неотрицательные для случаев, когда дробное значение может испортить функцию). Проверьте несколько мест за пределами разрешенного ввода. Проверьте несколько типичных случаев. Вы также можете добавить случайный ввод, но для модульного теста, который имеет нежелательный побочный эффект, что одно и то же значение не тестируется при каждом запуске теста (хотя подход с использованием начального числа может работать, протестируйте первые 1000 случайных чисел из начального числа). S или что-то подобное).
Для проверки вывода случайной функции важно определить цель. В случае карт цель состоит в том, чтобы проверить однородность генератора случайных чисел 0-1, определить, все ли 52 карты появляются в результате, или какую-то другую цель (может быть, весь этот список и более)?
В конкретном примере вы должны предположить, что ваш генератор случайных чисел непрозрачен (точно так же, как не имеет смысла проводить модульное тестирование системного вызова или malloc - если вы не пишете ОС). Может быть полезно измерить генератор случайных чисел, но ваша цель не состоит в том, чтобы написать генератор случайных чисел, просто чтобы увидеть, что вы получаете 52 карты каждый раз, и что они меняют порядок.
Это долгий способ сказать, что на самом деле здесь есть две тестовые задачи: проверка того, что ГСЧ производит правильное распределение, и проверка того, что тасовой код вашей карты использует этот ГСЧ для получения рандомизированных результатов. Если вы пишете ГСЧ, используйте статистический анализ, чтобы доказать свое распределение, если вы пишете тасователь карт, убедитесь, что в каждом выходе имеется 52 неповторяющихся карты (это лучший пример для проверки по проверке, которую вы используете ГСЧ).
источник
Вы можете положиться на безопасные генераторы случайных чисел
У меня просто ужасная мысль: ты ведь не пишешь свой собственный генератор случайных чисел?
Предполагая, что это не так, вам следует протестировать код, за который вы отвечаете , а не код других людей (например,
SecureRandom
реализацию вашей платформы).Тестирование вашего кода
Чтобы проверить, правильно ли реагирует ваш код, нормально использовать метод с низкой видимостью для получения случайных чисел, чтобы его можно было легко переопределить с помощью класса модульного теста. Этот переопределенный метод эффективно отключает генератор случайных чисел и дает вам полный контроль над тем, что и когда производится. Следовательно, вы можете полностью использовать свой код, который является целью модульного тестирования.
Очевидно, что вы проверите граничные условия и убедитесь, что перетасовка происходит именно так, как ваш алгоритм диктует с учетом соответствующих входных данных.
Тестирование безопасного генератора случайных чисел
Если вы не уверены, что безопасный генератор случайных чисел для вашего языка не является действительно случайным или содержит ошибки (предоставляет значения вне диапазона и т. Д.), То вам необходимо выполнить подробный статистический анализ выходных данных за несколько сотен миллионов итераций. Постройте частоту появления каждого числа, и оно должно отображаться с равной вероятностью. Если результаты так или иначе искажены, вы должны сообщить о своих выводах разработчикам каркаса. Они определенно будут заинтересованы в устранении проблемы, поскольку безопасные генераторы случайных чисел являются основополагающими для многих алгоритмов шифрования.
источник
Ну, вы никогда не будете уверены на 100%, поэтому лучшее, что вы можете сделать, - это вероятность того, что числа случайны. Выберите вероятность - скажем, что выборка чисел или предметов будет появляться x раз при миллионах выборок с допустимой погрешностью. Запустите вещь миллион раз, и посмотрите, находится ли она в пределах поля. К счастью, компьютеры делают такие вещи легкими в выполнении.
источник
Чтобы проверить, что источник случайных чисел генерирует что-то, что, по крайней мере, имеет вид случайности, я хотел бы, чтобы тест генерировал довольно большую последовательность байтов, записывал их во временный файл и затем передавал в инструмент Fourmilab ent . Укажите ключ -t (краткий), чтобы он генерировал легко анализируемый CSV. Затем проверьте различные цифры, чтобы увидеть, что они "хороши".
Чтобы решить, какие числа являются хорошими, используйте известный источник случайности для калибровки вашего теста. Тест должен почти всегда проходить при наличии хорошего набора случайных чисел. Поскольку даже действительно случайная последовательность имеет вероятность создания последовательности, которая выглядит неслучайной, вы не можете получить тест, который обязательно пройдет. Вы просто выбираете пороги, которые делают маловероятным, что случайная последовательность вызовет сбой теста. Разве случайность не забавна?
Примечание: Вы не можете написать тест, который показывает, что PRNG генерирует «случайную» последовательность. Вы можете только написать тест, который, если он пройдет, указывает на некоторую вероятность того, что последовательность, сгенерированная PRNG, является «случайной». Добро пожаловать в радость случайности!
источник
Случай 1: Тестирование шаффла:
Рассмотрим массив [0, 1, 2, 3, 4, 5], перемешайте его, что может пойти не так? Обычные вещи: а) вообще не тасует, б) тасует 1-5, но не 0, тасует 0-4, но не 5, тасует и всегда генерирует один и тот же шаблон, ...
Один тест, чтобы поймать их всех:
Перемешайте 100 раз, добавьте значения в каждый слот. Сумма каждого слота должна быть аналогична друг другу. Avg / Stddev можно рассчитать. (5 + 0) /2=2,5, 100 * 2,5 = 25. Ожидаемое значение составляет, например, около 25.
Если значения выходят за пределы диапазона, существует небольшая вероятность того, что вы получили ложный отрицательный результат. Вы можете рассчитать, насколько велик этот шанс. Повторите тест. Ну, конечно, есть небольшая вероятность, что тест не пройден 2 раза подряд. Но у вас нет подпрограммы, которая автоматически удаляет ваш источник, если модульный тест не пройден, не так ли? Запустите это снова!
Это может провалиться 3 раза подряд? Может быть, вам стоит испытать удачу в лотерее.
Случай 2: бросить кости
Вопрос с игрой в кости - это тот же вопрос. Бросьте кости 6000 раз.
источник