Как я должен проверить случайность?

Рассмотрим способ, чтобы случайным образом перетасовать элементы в массив. Как бы вы написать простой, но прочный модульный тест, чтобы убедиться, что это работает?

Я'вэ придумали две идеи, обе из которых имеют заметные недостатки:

  • Перемешать массив, то убедитесь, что ее порядок отличается от прежнего. Это звучит хорошо, но не выполняется, если перемешивание происходит в случайном порядке в том же порядке. (Маловероятно, но возможно.)
  • Перемешать массив с постоянным семя, и сравните его с заданной выходной. Это зависит от случайной функции всегда возвращает одинаковые значения дают такое же потомство. Тем не менее, это иногда в неверном предположении.

Рассмотрим вторую функцию, которая имитирует броски кубиков и возвращает случайное число. Как бы вы протестировать эту функцию? Как бы вы проверить, что функция...

  • никогда не возвращается вне границы дозволенного?
  • возвращает числа в действительное распределение? (Единая для один умирает, нормальный для большого числа костей.)

Я'м искать ответы, предлагая обзор тестирование не только эти примеры, но и случайные элементы кода в целом. Модульные тесты даже правильное решение здесь? Если нет, то какого рода тесты?

Просто, чтобы облегчить все'с ума Я'м не пишу свой собственный генератор случайных чисел.

Konrad Rudolph
Редактировал вопрос 4-го мая 2012 в 5:39
Программная Инженерия
unit-testing random testing
3-го мая 2012 в 6:13
23 просмотров
Комментарии к вопросу (9)
Решение

Я не'т думаю, что юнит-тесты-это правильный инструмент для тестирования случайности. Модульный тест должен вызывать метод и проверить возвращаемое значение (или состояние объекта) от ожидаемого значения. Проблема с тестированием случайность, что там'т-ожидаемое значение для большинства вещей, которые вы'd, как, чтобы проверить. Вы можете проверить с учетом семян, но это только тесты повторяемость. Это не'т дать вам какой-либо способ измерить как случайные распределение, или, если это's даже случайность.

К счастью, есть много статистических испытаний можно выполнить, например, несгибаемых тестов случайности. См. также:

  1. Как блок проверить псевдо генератор случайных чисел?
  • Стив Джессоп рекомендует найти проверенную реализацию того же алгоритма ГСЧ, что вы're, используя и сравниваем свой вывод с выбранным семена против собственной реализации.
  • Грег Hewgill рекомендует ЛОР набор статистических тестов. Джон Д. Кук]5 отсылает читателей к своей статье CodeProject простой генерации случайных чисел, который включает в себя выполнение теста Колмогорова-Смирнова, упомянутых в книге Дональда Кнута's громкость 2, Seminumerical алгоритмов.
  • Несколько человек рекомендуем проверить, что распределение генерируемых чисел является однородным, Хи-квадрат тест, и тестирование, что средние и стандартные отклонения находятся в пределах ожидаемого диапазона. (Обратите внимание, что испытания только распределение не хватает. [1,2,3,4,5,6,7,8] равномерное распределение, но это'ы, конечно, не случайно.)
  1. Модульного тестирования с функциями, которые возвращают случайные результаты
  • Брайан Genisio указывает на то, что издеваясь над вашим ГСЧ один вариант для создания тестов повторяемые, и предоставляет образец C# кода.
  • Снова, еще несколько человек указывают на использование фиксированных значений семян для повторимости и простые тесты для равномерного распределения, Хи-Квадрат и т. д.
  1. Модульного тестирования случайность в статье Вики, что говорит о множестве проблем уже затрагивали, когда пытаешься проверить то, что, по своей природе, не повторимый. Одно интересное, что я узнал от него следующее:

Я'вэ видел в WinZip используется в качестве инструмента для измерения хаотичности файл значений до (очевидно, чем меньше он может сжимать файл, тем менее случайной она).

Bill the Lizard
Редактировал ответ 30-го мая 2018 в 5:03
Комментарии (7)

1. Модульных тестов ваш алгоритм

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

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Увидеть, если ваша случайная функция имеет смысл

Для модульного тестирования, вы должны добавить тест, который выполняется несколько раз и утверждает, что результаты

  • в границах, которые вы установили (так, в кости от 1 до 6) и
  • показать целесообразное распределение (сделать несколько тестов и посмотреть, если распределение в пределах Х% того, что вы ожидали, например на рулон кости вы должны увидеть 2 между 10% и 20% (1/6 = 16.67%) времени, учитывая, что вы свернул его в 1000 раз).

3. Интеграционного тестирования по алгоритму и случайной функции

Как часто вы ожидаете, что Ваш массив не будет отсортирован в первоначальной сортировки? Вроде пару сотен раз и утверждают, что только Х% от времени сортировки не меняется.

Это уже интеграционный тест, вы тестируете алгоритм вместе с случайная функция. После того, как вы используете реальный случайной функции, вы можете'т получить больше от одного теста.

Из опыта (я писал генетического алгоритма) я бы сказал сочетание модульного тестирования вашего алгоритма, проверка распределения случайной функции и интеграционного тестирования является способом пойти.

sebastiangeiger
Редактировал ответ 9-го мая 2012 в 6:54
Комментарии (0)

Аспект PRNGs, что, кажется, забыли о том, что все его свойства имеют статистический характер: вы можете'т ожидать, что перетасовки массива приведет к другой перестановке из одного вы начали. В принципе, если вы используете обычный ГПСЧ, единственное, что вы'вновь гарантировано, что он не'т использовать простой шаблон (надеюсь) и что она имеет равномерное распределение среди множества цифр он возвращает.

Правильного теста для ГПСЧ связаны с запуском его не менее 100 раз и после проверки распределения на выходе (что является прямым ответом на вторую часть вопроса).

Ответ на первый вопрос почти тот же: выполнить тест примерно в 100 раз с {1, 2, ..., n} и сосчитать, сколько раз каждый элемент был на каждой позиции. Они должны быть примерно равны, если способ перетасовать хорошая.

Совершенно другое дело-это как тест криптография-класс PRNGs. Это вопрос, в котором ты, наверное,'т останавливаться, пока вы точно не знаете, что вы делаете. Люди, как известно уничтожить (читай: открытой катастрофической дыры в) хорошее криптосистем с помощью всего нескольких 'оптимизация' или тривиальные правки.

Редактировать: я внимательно перечитал вопрос, лучшие ответы и мои собственные. А очки я по-прежнему стою, я бы второй законопроект ящерица'ы ответ. Модульные тесты являются логическими по своей природе - они либо не имеют, либо у них получится, и поэтому непригодны для тестирования "Как хорошо, что" параметры ГПСЧ (или метод, с помощью ГПСЧ), так как любой ответ на этот вопрос будет количественным, а не полярные.

K.Steff
Редактировал ответ 3-го мая 2012 в 10:26
Комментарии (2)

Дайте ему поработать несколько раз и визуализация данных.

Здесь'ы пример Shuffle от ужасы кодирование, можно видеть, что алгоритм-это ОК или нет:

Это's легко понять, что каждый пункт возвращается как минимум один раз (границы ОК) и что распределение нормально.

Carra
Редактировал ответ 4-го мая 2012 в 3:51
Комментарии (2)

Есть две части к этому: рандомизация, тестирование и испытания то, что использовать рандомизацию.

Рандомизация тестирования является относительно простым. Вы убедитесь, что период генератора случайных чисел является, как вы ожидаете (по несколько образцов, используя несколько как бы случайных семян, в течение некоторого порогового значения) и распределение выхода на большой размер, как вы ожидаете (в пределах некоторого порога).

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

Комментарии (0)

Вы можете рассчитывать на безопасные генераторы случайных чисел

Я просто пришла ужасная мысль: вы'повторно не писать свой собственный генератор случайных чисел ты?

Предполагая, что вы'повторно не так, то вы должны тест код, вы несете ответственность за, а не других людей's код (например, SecureRandom отобрать реализации для вашей рамки).

Тестирование код

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

Очевидно, что вы проверить граничными условиями и убедитесь, что перетасовки происходит в точности, как ваш алгоритм диктует даны соответствующие входы.

Тестирование безопасный генератор случайных чисел

Если вы не уверены в том, что безопасный генератор случайных чисел на вашем языке не является истинно случайным или глючит (предоставляет диапазон значений и т. д.), то нужно провести подробный статистический анализ производства за несколько сотен миллионов итераций. Сюжет частоты появления каждого числа и она должна появляться с равной вероятностью. Если результаты перекос так или иначе, вы должны сообщить свои выводы в рамках дизайнеры. Они, безусловно, будут заинтересованы в решении проблемы с безопасной генераторы случайных чисел являются основой для многих алгоритмов шифрования.

Gary Rowe
Редактировал ответ 3-го мая 2012 в 6:43
Комментарии (0)

Общие советы я'вэ нашел полезным при работе с кодом, который позволит рандомизированных ввода: Регистрация крайние случаи ожидаемой случайности (Max и min значения, а максимум+1 и мин-1 значения если применимо). Проверить места (дальше, выше, и ниже), где число точек перегиба (т. е. -1, 0, 1 или больше 1, меньше 1 и неотрицательна в случаях, когда дробные значения могут испортить функцию). Проверьте несколько мест, полностью вне разрешенного ввода. Проверить несколько типичных случаев. Вы также можете добавить случайные данные, но на модульный тест, который имеет нежелательный побочный эффект, что то же значение, разве'т тестируемого каждый раз, когда запускается тест (семя подход может работать, хотя, проверить первые 1000 случайных чисел из семян или somesuch).

Для проверки выходной случайной функции, важно определить цель. В случае карты, есть цель для проверки однородности генератор случайных 0-1, чтобы определить, если все 52 карты появляются в результате, или какой-то иной цели (может быть, весь этот список и многое другое)?

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

Что'ы длинный способ сказать, что есть две тестовые задания: испытания, что ГСЧ производит правильное распределение, и убедившись, что ваши тасовать карты код, используя, что ГСЧ для того чтобы произвести результаты случайного. Если ты пишешь ГСЧ, использовать статистический анализ чтобы доказать свое распределение, если вы'вновь пишет на карты пройдоха, убедитесь, есть 52 номера-повторяющиеся карты в каждый выход (он's в лучшем случае, тест проверки, что вы're через ГСЧ).

Комментарии (0)

Чтобы проверить, что источник случайных чисел, генерирующего нечто, что, по крайней мере, имеет вид случайности, я бы тест создать довольно большую последовательность байт, записать их во временный файл, а потом выложить на адррес fourmilab'ы ЛОР инструмент. Дать ЛОР к -т (немногословный) переключатель, поэтому он будет создавать легко разобрать КШМ. Затем проверить различные цифры, чтобы увидеть, что они на "хорошо.&и"

Чтобы решить, какие цифры хорошие, использовать известный источник случайности для калибровки теста. Тест должен почти всегда проходят, когда дали хороший набор случайных чисел. Потому что даже по-настоящему случайную последовательность имеет вероятность генерации последовательности, которая представляется неслучайной, вы можете'т получить тест, который обязательно проходят. Вы просто выбираете пороги, что делает маловероятным, что случайная последовательность приведет к сбою теста. Разве'т рандоме удовольствие?

Примечание: Вы не можете написать тест, который показывает, что ПСЧ генерирует и"случайных" и последовательность. Вы можете только написать тест, что если она проходит, свидетельствует об определенной вероятности того, что последовательность генерируется ГПСЧ является "случайным&.и" Добро пожаловать в радость рандоме!

Комментарии (0)

Случай 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 раза подряд. Но вы не't имеют функцию, которая автоматически удаляет ваш источник, если юнит-тест не пройден, не так ли? Запустить его снова!

Он может не 3 раза подряд? Может быть, вы должны попробовать свою удачу в лотерее.

Случай 2: бросьте кубик

Кости-ролла вопрос один и тот же вопрос. Бросить кости 6000 раз. 

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;
Комментарии (0)

Ну, вы'll никогда не быть 100% уверенным, поэтому лучшее, что вы можете сделать, это, что это'ы вероятность того, что числа являются случайными. Выбрать вероятность, скажем, что образец цифры или предметы придумают х раз дали миллион образцов, в пределах погрешности. Запуск вещь в миллион раз, и посмотреть, если это's в рамках маржи. К счастью, компьютеры делают такого рода вещи легко сделать.

Комментарии (4)