Проверка на случайную ценность - мысли об этом подходе?

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

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

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

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

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

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

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

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

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

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

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

The generation of random numbers is too important to be left to chance. -- Robert R. Coveyou

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот пример на 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";

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Павел