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

Question

Хорошо, я работал над случайным выбором изображений и системой очередей (чтобы вы не видели одни и те же изображения слишком часто).

Все шло гладко (насколько это делает мой дрянной код) до Я добрался до случайного момента.Я хотел это проверить, но как это проверить?Здесь нет Debug.Assert(i.IsRandom) (печально) :D

Итак, я задумался над этим, полив его чаем, и пришел к следующему: мне просто интересно, могу ли я узнать ваши мысли?

• В принципе я знал случайный бит был проблемой, поэтому я вытащил его в делегат (который затем будет передан конструктору объектов).
• Затем я создал класс, который в значительной степени выполняет ту же логику, что и жить код, но запоминает значение, выбранное в частной переменной.
• Затем я бросил этого делегата в живой класс и протестировал его:

то есть

Debug.Assert(myObj.RndVal == RndIntTester.ValuePassed);

Но я не мог не подумать: я зря терял время? Я прогнал это через множество итераций, чтобы увидеть, не упал ли он в любой момент и т. д.

Вы думаете, я зря потратил на это время?Или мне могло сойти с рук:

Ответ GateKiller напомнил мне вот это:

Обновление для уточнения

• Я должен добавить, что я, по сути, никогда не хочу видеть один и тот же результат более X раз из пула размера Y.
• Добавление тестового контейнера позволило мне увидеть, было ли какое-либо из ранее выбранных изображений выбрано «случайно».
• Думаю, технически здесь тестируется не ГСЧ (поскольку я никогда не писал этот код), а тот факт, что я ожидаю случайный результаты из ограниченного пула, и я хочу их отслеживать.

Answer 1

Тест по требованию:«чтобы вы не видели одни и те же изображения слишком часто»

Попросите 100 изображений.Вы видели изображение слишком часто?

Answer 2

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

Answer 3

Если у вас фиксированный набор предметов и вы не хотите, чтобы они повторялись слишком часто, перетасуйте коллекцию случайным образом.Тогда вы будете уверены, что никогда не увидите одно и то же изображение дважды подряд, не почувствуете, будто слушаете радио Топ-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;
}

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

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

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

Answer 4

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

Если вы проводите тестирование методом «белого ящика» и знаете свое случайное начальное число, то вы действительно можете вычислить ожидаемый результат, но вам может потребоваться отдельный тест для проверки случайности вашего ГСЧ.

Answer 5

Генерация случайных чисел слишком важно, чтобы его не было.-- Роберт Р.Ковейу

Чтобы решить психологическую задачу:

Достойный способ предотвратить очевидные повторения — это случайным образом выбирать несколько предметов из полного набора, отбрасывая дубликаты.Сыграйте в них, а затем выберите еще несколько.Количество «несколько» зависит от того, как быстро вы их играете и насколько велик полный набор, но, например, можно избегать повторения внутри большего из «20» и «5 минут».Проводите пользовательское тестирование — вам, как программисту, так надоест слайд-шоу, что вы не являетесь хорошим испытуемым.

Чтобы протестировать код рандомизации, я бы сказал:

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

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

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

Answer 6

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

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

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

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

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

Павел

Answer 7

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

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

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

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

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

Answer 8

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

Answer 9

Я считаю, что все случайное не может быть должным образом протестировано.

Конечно, вы можете попытаться протестировать его, но комбинаций так много, что вам лучше просто положиться на ГСЧ и выборочно проверить большое количество случаев.

Answer 10

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

В любом случае, вам никогда не следует так много думать о случайных числах.:)

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Чтобы получить серию неповторяющихся случайных чисел:

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

Answer 15

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

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

Answer 16

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

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

Если вы обнаружите, что генератор, который вы используете сейчас, недостаточно хорош, вы можете легко что-нибудь найти.Погуглите «Mersenne Twister» — это гораздо более случайно, чем вам когда-либо понадобится.

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

Answer 17

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

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

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

Answer 18

Я согласен с Адамом Розенфилдом.В ситуации, о которой вы говорите, единственное, что вы можете с пользой проверить, — это распределение по диапазону.

Ситуация, с которой я обычно сталкиваюсь, заключается в том, что я генерирую псевдослучайные числа с помощью 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";

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

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

Answer 19

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

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

Вышеупомянутое показывает «относительно» нормальное распределение.

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

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

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

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

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

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