Як мені перевірити випадковість?

Розглянемо метод випадкового перемішування елементів у масиві. Як ви напишете простий, але надійний тест на одиницю, щоб переконатися, що це працює?

Я висунув дві ідеї, в обох з яких є помітні вади:

  • Перемішайте масив, потім переконайтеся, що його порядок відрізняється від попереднього. Це звучить добре, але не вдається, якщо випадкове перемішування відбувається у такому ж порядку. (Неможливо, але можливо.)
  • Перемішайте масив з постійним насінням та перевірте його на заданий вихід. Це залежить від випадкової функції, яка завжди повертає ті ж значення, що мають одне й те саме насіння. Однак це іноді неправильне припущення .

Розглянемо другу функцію, яка імітує кубичні рулони і повертає випадкове число. Як ви перевіряєте цю функцію? Як би ви перевірили цю функцію ...

  • ніколи не повертає номер за межами заданих меж?
  • повертає номери в дійсному розподілі? (Уніформа для одного вмирання, нормальна для великої кількості кісток.) ​​

Я шукаю відповіді, що пропонують розуміння тестування не лише цих прикладів, але й випадкових елементів коду в цілому. Чи є тут стандартні випробування навіть правильним рішенням? Якщо ні, то які тести?


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

108
"Це залежить від випадкової функції, яка завжди повертає ті ж самі значення, що мають одне і те ж насіння. Однак це іноді є неприпустимим припущенням." Я йшов за посиланням, і я не бачу недійсного припущення. Це досить чітко говорить: "Якщо одне і те ж насіння використовується неодноразово, створюється однакова серія чисел".
додано Автор hao, джерело
@ Локі Астарі: ваш коментар звучить як досить хороша відповідь. Чому ви відповіли на питання в коментарях, а не давали правильну відповідь?
додано Автор mateostabio, джерело
@BryanOakley: він не відповідає на питання, яке задано Як написати одиничні тести . Це коментар щодо дизайну коду, для його перевірки необхідний сполучений спосіб.
додано Автор Martin York, джерело
Тісне зчеплення показує його голову. Переходьте в об'єкт, який генерує випадкові числа. Потім під час тестування ви можете передавати об'єкт, який генерує певний набір чисел, для яких ви знаєте, що колода виглядає після перемішування. Ви можете перевірити випадковість свого генератора випадкових чисел окремо.
додано Автор Martin York, джерело
Я б настійно рекомендував використовувати існуючу бібліотечну процедуру для перемішування (java Collections.shuffle() або подібні). Існує попереджаюча історія, яку можна прочитати на developer.com/tech/article.php/616221/… про написання недосконалого алгоритму перестановки. Для написання функції d6() можна перевірити його достатньо, щоб бути впевненим, що він не генерує число, що перебуває за межами діапазону, а потім проводять квадратний тест на розподілі (chi квадрат є досить чутливим до псевдо випадкових послідовностей). Подивіться також на коефіцієнт послідовного кореляції.
додано Автор user40980, джерело
Тестування на випадковість неможливо . Будь-який можливий правильний результат вашого перемішування може бути досягнутий, і в одному перемішуванні всі результати мають рівну вірогідність, незалежно від того, наскільки імовірно вони можуть з'явитися. Найкраще, що ви можете зробити, це підказка про те, як результат ймовірний . Наприклад, можливе перемішування, що призводить до того ж порядку (і так само ймовірно, як і будь-яке інше замовлення). Однак, якщо ви повторите тест 100 разів, і порядок буде таким же після перестановки кожного разу, то перемішування навряд чи буде випадковим.
додано Автор Lars Yencken, джерело
@Kyralessa Я пропустив важливу половину цієї цитати: "В результаті код вашого додатка не повинен вважати, що одне і те ж насіння призведе до тієї ж псевдослучайної послідовності в різних версіях .NET Framework".
додано Автор SuB, джерело
@Kyralessa "Реалізація генератора випадкових чисел у випадковому класі не гарантується залишатися незмінною в основних версіях .NET Framework". Так що не величезна турбота, але все-таки щось розглянути.
додано Автор SuB, джерело
Що сказав @MartinYork. Оскільки ви не пишете власного генератора випадкових чисел, то те, що ви повинні тестувати, це те, що ваш код правильно викликає будь-який RNG, який він використовує. Правильність цього RNG виходить за межі ваших одиничних тестів.
додано Автор David Moles, джерело

10 Відповіді

Я не думаю, що тест на одиницю є правильним інструментом для перевірки випадковості. Одиничний тест повинен викликати метод і перевірити повернене значення (або стан об'єкта) проти очікуваного значення. Проблема з випадковою перевіркою полягає в тому, що для більшості речей, які потрібно протестувати, немає очікуваного значення. Ви можете протестувати з певним насінням, але лише перевіряє повторюваність . Це не дає вам ніякого способу вимірювати випадковий розподіл, або якщо воно взагалі випадкове.

На щастя, існує безліч статистичних тестів, які можна запустити, наприклад, Diehard Battery Test of Randomness . Дивіться також:

  1. How to unit test a pseudo random number generator?

    • Steve Jessop recommends that you find a tested implementation of the same RNG algorithm that you're using and compare its output with selected seeds against your own implementation.
    • Greg Hewgill recommends the ENT suite of statistical tests.
    • John D. Cook refers readers to his CodeProject article Simple Random Number Generation, which includes an implementation of the Kolmogorov-Smirnov test mentioned in Donald Knuth's volume 2, Seminumerical Algorithms.
    • Several people recommend testing that the distribution of the numbers generated is uniform, the Chi-squared test, and testing that the mean and standard deviation are within the expected range. (Note that testing the distribution alone is not enough. [1,2,3,4,5,6,7,8] is a uniform distribution, but it's certainly not random.)
  2. Unit Testing with functions that return random results

    • Brian Genisio points out that mocking your RNG is one option for making your tests repeatable, and provides C# sample code.
    • Again, several more people point to using fixed seed values for repeatability and simple tests for uniform distribution, Chi-squared, etc.
  3. Unit Testing Randomness is a wiki article that talks about many of the challenges already touched on when trying to test that which is, by its nature, not repeatable. One interesting bit that I gleaned from it was the following:

    I've seen winzip used as a tool to measure the randomness of a file of values before (obviously, the smaller it can compress the file the less random it is).

90
додано
@DanRasmussen Звичайно, у мене буде час зробити це протягом вихідних днів.
додано Автор Josh, джерело
Існує Dieharder ( webhome.phy.duke.edu/~rgb/General/ dieharder.php ), який є GPL. Це прямо вперед для використання. Незалежно від того, як ви перевіряєте не випадковість, ви повинні вирішити, чи перевіряєте ви те, що ви думаєте, що тестуєте.
додано Автор Greenhorn, джерело
"Проблема з ... випадковістю полягає в тому, що немає очікуваного значення ..." - наскільки іронічно, з огляду на те, що "очікуване значення" є чітко визначеним терміном у статистиці. І хоча це не те, що ви мали на увазі, він натякає на правильне рішення: використовуючи відомі властивості статистичних розподілів у поєднанні з випадковими вибірками та статистичні тести , щоб визначити, чи працює алгоритм з дуже високою ймовірністю. Так, це не класичний тест на одиницю, але я хотів це згадати, оскільки в найпростішому випадку він просто дивиться на розподіл ... очікуваного значення .
додано Автор Mark Ransom, джерело
Ще один хороший набір тестів для статистичної випадковості - "ent", що знаходиться на fourmilab.ch/andom .
додано Автор user40980, джерело
Існує оновлена ​​версія знаменитої батареї випробувань випадковості в Dieharder, яка включає в себе Статистичний тестовий комплекс (STS), розроблений Національним інститутом стандартів і технологій (NIST). Він доступний для роботи в Ubuntu та, ймовірно, в інших дистрибутивах: phy. duke.edu/~rgb/General/dieharder.php
додано Автор Attila Szasz, джерело
Зверніть увагу, що ent включений для Ubuntu, а також тести chi-squared серед інших: Програма тестування послідовності псевдовипадкових чисел
додано Автор Attila Szasz, джерело
Чи можете ви підвести підсумки деяких посилань, які ви опублікували, для повноти відповіді?
додано Автор SuB, джерело

1. Одиниця перевірити свій алгоритм

Для першого запитання я б побудував фальшивий клас, який ви передаєте послідовності випадкових чисел, для яких ви знаєте результат вашого алгоритму. Таким чином, ви переконаєтесь, що алгоритм, який ви будуєте зверху своєї випадкової функції, працює. Тож щось на кшталт:

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

2. Подивіться, чи має ваша випадкова функція сенс

Для тесту на одиницю слід додати тест, який працює кілька разів і стверджує, що результати

  • знаходяться в межах, які ви встановили (отже, кістковий вал становить від 1 до 6) і
  • показати здоровий розподіл (виконайте декілька тестових спроб і перевірте, чи розподіл не перевищує x% від того, що ви очікували, наприклад, для коду, який ви мали б побачити 2 , виходите від 10% до 20 % (1/6 = 16,67%) часу, якщо ви його прокатували 1000 разів.

3. Інтеграційний тест для алгоритму та випадкової функції

Як часто ви очікували, що ваш масив буде відсортовано у вихідній сортування? Сортувати пару сотень разів і стверджувати, що лише х% часу сортування не змінюється.

Фактично це вже є тестом інтеграції, ви тестуєте алгоритм разом з випадковою функцією. Як тільки ви використовуєте справжню випадкову функцію, ви не зможете піти з одним випробуванням більше.

З досвіду (я написав генетичний алгоритм) Я хотів би сказати, що поєднання одиничного тесту вашого алгоритму, тест розподілу вашої випадкової функції та тест інтеграції є способом піти.

21
додано

Один із аспектів, який, здається, забутий про PRNG - це те, що всі його властивості мають статистичний характер: ви не можете очікувати, що переміщення масиву призведе до іншої перестановки з тієї, з якої ви почали працювати. В принципі, якщо ви використовуєте звичайний PRNG, єдине, що ви гарантовано, - це те, що він не використовує простий шаблон (сподіваюся) і що він має рівномірний розподіл між набором чисел, який він повертає.

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

Відповідь на перше запитання майже однакова: виконайте тест приблизно 100 разів за допомогою {1, 2, ..., n} і підрахуйте кількість разів, коли кожен елемент був у кожній позиції. Вони повинні бути приблизно рівними, якщо метод перемішування є будь-яким корисним.

Зовсім інша справа - це тестування PRNG-класів з криптографією. Це питання, в якому ви, мабуть, не повинні зупинятися, якщо ви дійсно не знаєте, що ви робите. Люди, як відомо, знищили (прочитайте: відкривайте катастрофічні дірки), хороші криптосистеми з лише декількома "оптимізаціями" або тривіальними редакціями .

РЕДАГУВАТИ: я ретельно перечитав це питання, головну відповідь і свій власний. Хоча точки, які я роблю, все ще стоять, я б відмітив відповідь Білла Ящірки. Типові тести булеві за своїм характером - вони невдалі або успішні, і тому не підходять для тестування "наскільки добре" властивості PRNG (або методу, що використовує PRNG), оскільки будь-яка відповідь на це питання буде кількісною , а не полярний.

14
додано
Я думаю, ви маєте на увазі, що кількість разів, коли кожен елемент знаходиться в кожній позиції, повинен бути приблизно рівним. Якщо вони постійно рівноцінні, то щось дуже неправильно.
додано Автор octern, джерело
@octern Спасибі, я не знаю, як я міг би написати, що ... це було повністю неправильно дотепер ...
додано Автор K.Steff, джерело

Існує дві частини: випробування рандомізації та тестування речей, які використовують рандомізацію.

Тестування рандомізації відносно просто. Ви перевіряєте, чи період генератора випадкових чисел є таким, як ви очікуєте, (для кількох зразків, що використовують декілька випадкових насіння, в межах певного порогу), і що розподіл виходу за великим обсягом вибірки є таким, як ви очікуєте це бути (в межах певного порогу).

Тестування речей, які використовують рандомізацію, краще всього проводити з детермінованим генератором псевдо випадкових чисел. Оскільки вихідний результат рандомізації відомий на основі насіння (його вхідних даних), то ви можете тестувати одиницю, як правило, на основі входів і очікуваних виходів. Якщо ваш RNG не детерміністичний, то висміюйте його тим, що є детерміністичним (або просто не випадковим). Перевірте рандомізацію окремо від коду, який його споживає.

6
додано

Загальні вказівки, які я виявив корисним при роботі з кодом, який приймає рандомізоване введення: Перевірте крайові випадки очікуваної випадковості (макс і min, а також макс. + 1 та min-1 значення, якщо це необхідно). Перевірте місця (на, вище, і нижче), де числа мають точки перевертання (тобто -1, 0, 1 або більше 1, менше 1 і неотрицательно для випадків, коли дрібне значення може перешкоджати функції). Перевірте кілька місць повністю за межами дозволеного входу. Перевірте кілька типових випадків. Ви також можете додати випадковий ввід, але для випробувань на одиницю, який має небажаний побічний ефект, що одне і те ж значення не піддається тесту при кожному запуску тесту (для насіннєвого підходу може працювати 1 000 випадкових чисел із насіння S або будь-який інший).

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

У конкретному прикладі, ви повинні припустити, що ваш генератор випадкових чисел є непрозорим (точно так само, як це не має сенсу для одиничного тестування OS syscall або malloc, якщо ви не напишете операційні системи). Можливо, буде корисно вимірювати генератор випадкових чисел, але ваша мета - не писати випадковий генератор, щоб побачити, що ви отримуєте 52 карти кожного разу, і що вони змінюють порядок.

Це тривалий спосіб сказати, що існують дві тестові завдання: тестування того, що RNG виробляє правильний розподіл, і перевіряє, чи використовує ваш кодований код кодування RNG для створення рандомізованих результатів. Якщо ви пишете RNG, використовуйте статистичний аналіз, щоб підтвердити свій розподіл, якщо ви пишете картковий шулер, переконайтеся, що на кожному виході існує 52 неповторних карт (це краще випадок для тестування за допомогою огляду, який ви використовуєте RNG).

4
додано

Ви можете покладатися на безпечні генератори випадкових чисел

I just had a horrible thought: you're not writing your own random number generator are you?

Припускаючи, що ви не є, ви повинні протестувати код, за який ви несете відповідальність , а не код іншого користувача (наприклад, реалізація SecureRandom для вашої структури).

Тестування вашого коду

Щоб перевірити, чи правильно відповідає ваш код, нормально використовувати метод низької видимості для створення випадкових чисел, щоб його можна було легко перевизначити за допомогою класу модульного тесту. Цей переопределений метод ефективно викривлює генератор випадкових чисел і дає вам повний контроль над тим, що виробляється і коли. Отже, ви можете повністю виконувати свій код, який є метою одиничного тестування.

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

Тестування безпечного генератора випадкових чисел

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

4
додано

Дозвольте йому запустити купу разів і візуалізувати свої дані .

Ось приклад випадкового переміщення з кодування жахів , ви можете побачити, що алгоритм OK або ні.

enter image description here

Легко побачити, що кожний можливий елемент повертається принаймні один раз (кордони є правильними) і що розподіл є OK.

4
додано
+1 візуалізація це ключ. Мені завжди сподобався приклад з зображенням пінгвіна в розділі "ЄЦБ" Стаття блочного шифру ). . Автоматизоване програмне забезпечення рідко може виявити такі закономірності
додано Автор Erik, джерело
Ах? Суть цієї візуалізації - показати, що розподіл не в порядку. Алгоритм наївного перемішування робить певні замовлення значно більш імовірними, ніж інші. Зверніть увагу, як далі далі вправо 2341, 2314, 2143 та 1342 бари продовжуються?
додано Автор hvd, джерело

Щоб перевірити, що джерелом випадкових чисел є те, що принаймні має вигляд випадковості, я б мав тестувати генерувати досить велику послідовність байтів, записати їх у тимчасовий файл, а потім розбити на інструмент Fourmilab ent . Дайте ent -t (краткий) перемикач, щоб він генерував простий в аналізі CSV. Потім перевірте різні номери, щоб побачити, що вони "хороші".

Щоб визначити, які номери хороші, використовуйте відомі джерела випадковості , щоб відкоригувати ваш тест. Тест повинен майже завжди проходити, коли дається хороший набір випадкових чисел. Оскільки навіть справді випадкова послідовність має ймовірність створення послідовності, яка виглядає невипадковою, ви не можете отримати тест, який, безумовно, пройде. Ви просто вибираєте пороги, що робить це малоймовірним, що випадкова послідовність призведе до невдалої перевірки. Не випадково весело?

Примітка: Ви не можете написати тест, який показує, що PRNG створює "випадкову" послідовність. Ви можете написати лише тест, який, якщо він проходить, вказує на певну ймовірність того, що послідовність, сформована PRNG, є "випадковою". Ласкаво просимо до радості випадковості!

1
додано

Випадок 1: перевірка перемішування:

Розглянемо масив [0, 1, 2, 3, 4, 5], перемішувати його, що може стати не так? Звичайний матеріал: а) взагалі не перемішується, б) перемішування 1-5, але не 0, перемішування 0-4, але не 5, перемішування, і завжди створюючи той же малюнок ...

Один тест, щоб зловити їх усіх:

Перемішайте 100 раз, додайте значення в кожному слоті. Сума кожного слоту повинна бути однаковою для кожного слоту. Середній/Stddev можна розрахувати. (5 + 0)/2 = 2,5, 100 * 2,5 = 25. Очікуване значення складає приблизно 25, наприклад.

Якщо значення недоступні, є невеликий шанс, що ви отримали хибний негативний результат. Ви можете обчислити, наскільки великий цей шанс. Повторіть тест. Ну - звичайно є невеликий шанс, що тест не вдається 2 рази поспіль. Але у вас немає процедури, яка автоматично видаляє ваше джерело, якщо пристрій не працює, чи не так? Запустіть його знову!

Це може вийти з ладу 3 рази поспіль? Може бути, ви повинні спробувати щастя на лотерею.

Справа 2: зніміть кістки

Той же питання - це питання про кістки. Киньте кістки 6000 разів.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;
1
додано

Ну, ви ніколи не будете на 100% впевнені, тому найкраще, що ви можете зробити, це те, що ці цифри є випадковими. Виберіть вірогідність - скажіть, що зразок чисел або предметів буде виходити в x разів, з урахуванням мільйонів зразків, в межах похибки. Запустіть річ у мільйон разів і подивіться, чи вона знаходиться в межах поля. На щастя, комп'ютери роблять подібні речі легко.

1
додано
@ К. Стефф, вау. Ви перевірили одиничний тест, щоб підтвердити, що алгоритм Dijkstra був правильним?
додано Автор BCS, джерело
Хороший момент, по суті - так, але на цей раз з "тривіальними" тестами. Однак вони також були уніфікованими тестами для оригінальної програми (A *). Я думаю, що це дійсно непогана практика - тестування швидких алгоритмів знову-таки лагідних (але правильних) реалізацій.
додано Автор K.Steff, джерело
Тестування на одиницю має бути правильним . Якщо це займає розгалуження, цикли, рекурсія - це ціна. Ви не можете випробувати надзвичайно складні, високооптимізовані класи з однорядковими одиничними тестами. Я застосував алгоритм Дейкстра для одноразового тестування класу.
додано Автор K.Steff, джерело
Але чи є подібні тести, як це вважається хорошим досвідом ..? Я завжди вважав, що тест на одиницю повинен бути максимально простий: без циклів, філій або чогось іншого, що можна уникнути.
додано Автор SuB, джерело