Тестирование на случайное значение - мысли об этом подходе?

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

          ******    ******           ****
***********************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Вышеупомянутые шоу 'относительно' нормальное распределение.

если это выглядело более скошенным, такие как это:

          ******    ******           ****
    ************  ************  ************
    ************  ************  ***************
    ************  ************  ****************
    ************  ************  *****************
    ************  ************  *****************
   ***************************  ******************
   **************************** ******************
******************************* ******************
**************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Затем Вы видите, что существует меньше случайности. Как другие упомянули, существует проблема повторения для утверждения с также.

Если бы необходимо было записать, что двоичный файл говорит, что 10 000 случайных чисел от использования генератора, говорят случайное число от 1 до 1 024 и пытаются сжать тот файл с помощью некоторого сжатия (zip, gzip, то и т.д.) затем Вы могли сравнить эти два размера файла. Если существует большое сжатие, то это не особенно случайно. Если нет большой части изменения в размере, то это 'довольно случайно'.

Почему это работает

Алгоритмы сжатия ищут шаблоны (повторение и иначе), и уменьшает это в некотором роде. Одним способом посмотреть эти алгоритмы сжатия является мера объема информации в файле. Очень сжатый файл имеет мало информации (например, случайность), и мало-сжатый файл имеет много информации (случайность)

Я соглашаюсь с Adam Rosenfield. Для ситуации Вы говорите о, единственной вещью, на которую можно полезно протестировать, является распределение через диапазон.

Ситуация, с которой я обычно встречаюсь, состоит в том, что я генерирую псевдослучайные числа с PRNG своего любимого языка и затем управляю ими в желаемый диапазон. Чтобы проверить, влияли ли мои манипуляции на распределение, я генерирую набор чисел, управляю ими и затем проверяю распределение результатов.

Для получения хорошего теста необходимо генерировать, по крайней мере, пару порядков величины больше чисел, чем диапазон содержит. Чем больше значений Вы используете, тем лучше тест. Очевидно, если у Вас будет действительно большой спектр, то это не будет работать, так как необходимо будет генерировать слишком много чисел. Но в Вашей ситуации это должно хорошо работать.

Вот пример в Perl, который иллюстрирует то, что я имею в виду:

for (my $i=0; $i<=100000; $i++) {
   my $r = rand;        # Get the random number
   $r = int($r * 1000); # Move it into the desired range
   $dist{$r} ++;        # Count the occurrences of each number
}

print "Min occurrences: ", (sort { $a <=> $b } values %dist)[1], "\n";
print "Max occurrences: ", (sort { $b <=> $a } values %dist)[1], "\n";

Если распространение между минутой и макс. случаями является маленьким, то Ваше распределение хорошо. Если это широко, то Ваше распределение может быть плохим. Можно также использовать этот подход к проверке, был ли диапазон покрыт и были ли любые значения пропущены.

Снова, чем больше чисел Вы генерируете, тем более допустимый результаты. Я склонен начинать с малого и работать до того, что моя машина обработает за разумное количество времени, например, пять минут.

Хотя Вы не можете протестировать на случайность, можно протестировать это на корреляцию или распределение, последовательности чисел.

Трудно протестировать цель: Каждый раз мы нуждаемся в изображении, выбираем 1 из 4 изображений наугад.

Легкий протестировать цель: Для каждых 100 изображений мы выбираем, каждое из 4 изображений должно появиться по крайней мере 20 раз.

Случайные числа сгенерированы от распределения. В этом случае каждое значение должно иметь тот же propability появления. При вычислении бесконечной суммы randoms Вы получаете точное распределение.

На практике вызывайте функцию много раз и проверяйте результаты. Если Вы ожидаете иметь изображения N, вычислять 100*N randoms, затем рассчитывать, сколько из каждого ожидаемого числа было найдено. Большинство должно появиться 70-130 раз. Повторно выполните тест с другим случайным семенем, чтобы видеть, отличаются ли результаты.

При нахождении генератора, Вы используете, теперь не достаточно хорошо, можно легко найти что-то. Google для "вихря Мерсенна" - который намного более случаен, чем Вы когда-либо, нужно.

Для предотвращения повторного появления изображений Вам нужно что-то менее случайное. Простой подход должен был бы проверить на запрещенные значения, если его из тех, повторно вычислить.

Получить ряд неповторения случайных чисел:

1. Создайте список случайных чисел.
2. Добавьте порядковый номер к каждому случайному числу
3. Отсортируйте упорядоченный список по исходному случайному числу
4. Используйте свой порядковый номер в качестве нового случайного числа.

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

Я или взял бы пулы N размера Y, проверяющего на любые результаты, которые появляются больше чем X количества раз или берут один пул размера N*Y, проверяя каждую группу размера Y для любого результата, который появляется больше чем X раз (1 к Y, 2 к Y + 1, 3 к Y + 2, и т.д.). То, что N, зависело бы от того, как надежный Вы хотите, чтобы тест был.

Любой хороший генератор псевдослучайного числа позволит Вам отобрать генератор. Если Вы отберете генератор с тем же числом, то поток сгенерированных случайных чисел будет тем же. Итак, почему бы не отобрать Ваш генератор случайных чисел и затем создают Ваши модульные тесты на основе того конкретного потока чисел?

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

сохраните случайные значения и перед использованием следующего сгенерированного случайного числа проверьте по хранимой сумме.

Мое мнение - то, что что-либо случайное не может быть правильно протестировано.

Уверенный можно попытаться протестировать его, но существует столько комбинаций для попытки этого, Вы более обеспечены просто доверие RNG и пятну, проверяющему большое небольшое количество случаев.

Случайный Случайно. Даже если то же изображение обнаруживается 4 раза подряд, это можно было бы все еще считать случайным.

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

При использовании Perl можно использовать Статистику:: модуль ChiSquare, чтобы сделать тяжелую работу для Вас.

Однако, если Вы захотите удостовериться, что Ваши изображения равномерно распределяются, то затем Вы, вероятно, не захотите, чтобы они были действительно случайны. Вместо этого я предложил бы, чтобы Вы взяли свой весь список изображений, перестановка, которые перечисляют и затем удаляют объект из него каждый раз, когда Вам нужно "случайное" изображение. Когда список пуст, Вы восстанавливаете его, перестановка и повторение.

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

Всего наилучшего,

Paul

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

Все эти алгоритмы имеют что-то общее: ряд повторяется после многих повторений. Помните, это не действительно случайные числа, только серия чисел, которые кажутся случайными. Для выбора одного генератора по другому необходимо спросить себя: Для чего Вы хотите это?

Как Вы тестируете случайность? Действительно Вы можете. Существует много тестов для этого. Первое и самое простое, конечно, выполняются Ваш генератор псевдослучайного числа огромное количество раз, и скомпилируйте количество раз, каждый результат появляется. В конце каждый результат должен был появиться неоднократно очень близко к (количество повторений) / (количество возможных результатов). Чем больше стандартное отклонение этого, тем хуже Ваш генератор.

Второе: сколько случайных чисел Вы используете в то время? 2, 3? Возьмите их в парах (или триплеты) и повторите предыдущий эксперимент: после очень длинного количества повторений каждый ожидаемый результат должен был появиться, по крайней мере, однажды, и снова количество раз, каждый результат появился, не должно быть слишком далеко от ожидаемого. Существуют некоторые генераторы, которые работают просто великолепно для взятия один или 2 за один раз, но перестали работать эффектно, когда Вы берете 3 или больше (RANDU кто-либо?).

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

Невозможно протестировать, если значение действительно случайно или нет. Лучшее, которое можно сделать, выполняют тест некоторое большое количество раз и теста, что Вы получили соответствующее распределение, но если результаты действительно случайны, даже это имеет (очень маленький) шанс сбоя.

Если Вы делаете тестирование методом "белого ящика", и Вы знаете свое случайное семя, то можно на самом деле вычислить ожидаемый результат, но Вам, возможно, понадобится отдельный тест для тестирования случайности RNG.

Если у Вас есть фиксированный набор объектов, и Вы не хотите, чтобы они повторялись слишком часто, переставляли набор случайным образом. Затем Вы будете уверены, что никогда не видите то же изображение дважды подряд, чувствуете слушанию Лучших 20 радио и т.д. Вы сделаете всю передачу через набор перед повторением.

Item[] foo = …
for (int idx = foo.size(); idx > 1; --idx) {
  /* Pick random number from half-open interval [0, idx) */
  int rnd = random(idx); 
  Item tmp = foo[idx - 1];
  foo[idx - 1] = foo[rnd];
  foo[rnd] = tmp;
}

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

Немного отличающийся подход, который походит на него, мог бы относиться к Вашему пересмотренному проблемному оператору, должен иметь Вашу "реализацию" селектора изображения, сохраняют ее новейшую историю выбора в очереди самое большее Y длина. Прежде, чем возвратить изображение, это тестирует, чтобы видеть если в очереди X времена уже, и если так, это случайным образом выбирает, другой, до него находит тот, который передает.

Если Вы действительно спрашиваете о тестировании качества генератора случайных чисел, я должен буду открыть книгу по статистике.

Поколение случайных чисел слишком важно, чтобы быть оставленным случиться. - Robert R. Coveyou

Решить психологическую проблему:

Достойный способ предотвратить очевидные повторения состоит в том, чтобы выбрать несколько объектов наугад из полного набора, удалив дубликаты. Играйте их, затем выберите другого немногие. Сколько, "некоторые" зависят от того, как быстро Вы играете их и насколько большой полный набор, но например предотвращение повторения в больших из "20", и "5 минут" могло бы быть в порядке. Сделайте пользователя, тестирующего - как программист, Вы будете так сыты слайд-шоу по горло, Вы не хороший испытуемый.

Для тестирования кода рандомизации я сказал бы:

Шаг 1: укажите, как код ДОЛЖЕН отобразить необработанные случайные числа на выбор в Вашем домене, и удостоверяться, что Ваш код правильно использует вывод генератора случайных чисел. Протестируйте это путем Насмешки генератора (или отбор это с известным тестовым значением, если это - PRNG).

Шаг 2: удостоверьтесь, что генератор достаточно случаен в Ваших целях. При использовании библиотечной функции Вы делаете это путем чтения документации. Если Вы записали свое собственное, почему?

Шаг 3 (только усовершенствованные статистики): запустите некоторые статистические тесты для случайности на выводе генератора. Удостоверьтесь, что Вы знаете то, что вероятность имеет ложный отказ на тесте.

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

Ну, проблема состоит в том, что случайные числа по определению могут быть повторены (потому что они... ожидают его: случайный). Возможно, то, что Вы хотите сделать, является сохранением последнее случайное число, и сравните расчетный с этим, и, если равный просто вычисляют другого..., но теперь Ваши числа менее случайны (я знаю, что нет такой вещи как "более или менее" случайность, но позвольте мне использовать термин только на этот раз), потому что они, как гарантируют, не повторятся.

Так или иначе Вы никогда не должны уделять случайным числам такое внимание.:)