Тестирование на случайное значение - мысли об этом подходе? - PullRequest
8 голосов
/ 23 сентября 2008

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

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

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

  • По сути, я знал, что проблема была в бите random , поэтому я разорвал его делегату (который затем был бы передан конструктору объектов).
  • Затем я создал класс, который в значительной степени выполняет ту же логику, что и код live , но запоминает значение, выбранное в закрытой переменной.
  • Затем я бросил этого делегата в живой класс и проверил:
* * Тысяча двадцать-одиной т.е.
Debug.Assert(myObj.RndVal == RndIntTester.ValuePassed);

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

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

Awesome Random Number Generator

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

Dilbert Random

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

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

Ответы [ 19 ]

6 голосов
/ 23 сентября 2008

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

6 голосов
/ 23 сентября 2008

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

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

5 голосов
/ 23 сентября 2008

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

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

4 голосов
/ 23 сентября 2008

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

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

2 голосов
/ 24 сентября 2008

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

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

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

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

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

Пол

2 голосов
/ 23 сентября 2008

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

Для решения психологической проблемы:

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

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

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

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

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

1 голос
/ 23 сентября 2008

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

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

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

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

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

0 голосов
/ 23 сентября 2008

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

0 голосов
/ 24 сентября 2008

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

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

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

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

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

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

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

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

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

0 голосов
/ 23 сентября 2008

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

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

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

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

...