Випадковість у

Про концепцію Випадковість

Багатьом програмам потрібні (здавалося б) випадкові значення, щоб імітувати події реального світу.

Поширені й добре знайомі приклади:

• Кидання монети: випадкове значення з ('H', 'T').
• Кидання грального кубика: випадкове ціле число від 1 до 6.
• Перемішування колоди карт: випадковий порядок масиву карт.

Генерувати справді випадкові значення на компʼютері - напрочуд складна технічна задача, тож ці результати іноді називають «псевдовипадковими».

Важливо: ця концепція не охоплює криптографічно стійкі випадкові числа, які є набагато складнішою задачею.

Однак добре спроєктовані бібліотеки, як-от модуль Random зі стандартної бібліотеки Julia, швидкі, гнучкі й дають результати, цілком достатні для більшості застосунків у моделюванні, симуляції та іграх.

Julia розділяє роботу з випадковими значеннями між кількома місцями:

• Лише кілька базових, але дуже універсальних функцій у Base, які доступні завжди.
• Ширший набір можливостей у модулі Random.
• Вузькоспеціалізовану функціональність у пакунках, які потрібно встановити перед використанням (і яких немає в Exercism).

Random є частиною стандартної бібліотеки й, імовірно, уже встановлений, але щоб його вміст потрапив у простір імен, потрібно додати using Random на початку програми.

Функція rand()

Те, що робить ця функція, залежить від переданих їй аргументів. Варіантів багато.

Без аргументів вона генерує число з плаваючою комою між 0 (включно) та 1. Це uniform розподіл, у якому всі значення однаково ймовірні, як описано нижче в розділі «Робота з розподілами».

Один цілочисельний аргумент генерує вектор такої довжини.

julia> rand()
0.10261774967264703

julia> rand(5)
5-element Vector{Float64}:
 0.24134501977563894
 0.5664193284851202
 0.9804412082089355
 0.6229551330613335
 0.47589221741904664

Щоб отримати інший діапазон, достатньо відповідно зсунути й масштабувати результат.

У прикладі нижче для віднімання використовується broadcasting, про який ідеться в концепції Операції з векторами. .- просто застосовує цю арифметику до кожного елемента вектора.

# numbers between -1.0 and +1.0
julia> (rand(5) .- 0.5) * 2
5-element Vector{Float64}:
 -0.5303906759076336
  0.9635682226775855
 -0.048823697086981754
  0.465842804648374
  0.9880834344780736

Якщо передати лише тип, rand використає як межі typemin і typemax. Імовірно, це не те, чого ми хочемо!

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

julia> rand(Int64)
-9159538335234594326 # not very useful

julia> rand(1:10, 5)
5-element Vector{Int64}:
 1
 1
 1
 4
 7

У наведеному вище прикладі rand(1:10, 5) зауважмо, що значення (випадково) повторюються, бо кожен вибір незалежний. Це «вибірка з поверненням», докладніше про неї нижче.

Для чисел з плаваючою комою в діапазоні зазвичай потрібно вказати розмір кроку. Інакше крок типово дорівнюватиме 1.0, що рідко буває корисним.

julia> rand(2.4:0.01:3.2, 4)
4-element Vector{Float64}:
 3.19
 2.53
 3.14
 3.13

Або можна передати масив чи кортеж, і rand поверне випадковий елемент:

julia> rand([4, 9, 16, 25])
16

# coin flip
julia> rand(['H', 'T'])
'H': ASCII/Unicode U+0048 (category Lu: Letter, uppercase)

# mixed types in tuple
julia> rand( (1, 3.2, "name"), 2 )
2-element Vector{Any}:
 1
  "name"

Вибірка з поверненням і без повернення

Уявімо, що в нас є мішок із 3 червоними та 4 зеленими кульками, і ми навмання витягуємо з нього одну кульку. Щоб витягти другу кульку, є два варіанти:

1. Повернути першу кульку в мішок, добре все струсити й аж потім витягти наступну. Кількість кульок тепер така сама, як була (7), і співвідношення червоних до зелених теж не змінилося.
2. Покласти першу кульку на стіл, перш ніж витягти другу. Тепер у мішку лише 6 кульок, і співвідношення червоних і зелених залежить від кольору першої кульки.

Сценарій 1 - це вибірка з поверненням, сценарій 2 - без повернення, і вони дають різні результати.

Щоб змоделювати вибірку без повернення в Julia, є кілька варіантів.

Найпростіший варіант (і в межах Exercism єдиний) - скористатися Random.shuffle(), щоб розставити елементи у випадковому порядку, а потім узяти перші n елементів. Це цілком годиться для невеликих задач, але може погано масштабуватися на великі колекції: shuffle має згенерувати весь масив, навіть якщо нам потрібна лише невелика його частина.

Щоб робити вибірку з поверненням «як слід», установімо пакунок StatsBase.jl. Він надає функцію sample() з повним набором можливостей.

Можна цілком сподіватися, що подібну функціональність додадуть у Random у майбутньому випуску й зроблять її частиною стандартної бібліотеки (приклади коду в цьому документі перевірено на Julia 1.11).

Робота з розподілами

Досі ми зосереджувалися на випадках, де всі результати однаково ймовірні. Наприклад, rand(1:100) з однаковою ймовірністю видає будь-яке ціле число від 1 до 100.

Багато ситуацій реального світу значно складніші за це. Тож статистики створили безліч distributions, щоб математично описувати результати «реального світу».

Рівномірні розподіли

Функцію rand(), описану вище, використовують, коли всі ймовірності однакові. Це називають [uniform][uniform-distribution] розподілом.

Гаусів розподіл

Його також називають «нормальним» розподілом або «дзвоноподібною» кривою; це дуже поширений спосіб описати неточність виміряних значень.

Наприклад, уявімо, що завод, де ми працюємо, щойно купив 10 000 болтів, які мають бути однаковими. Ми хочемо налаштувати заводського робота для роботи з ними, тож зважуємо вибірку зі 100 болтів і бачимо, що їхня середня (або mean) вага становить 4.731 г. Це аж ніяк не означає, що всі вони важать рівно 4.731 г. Можливо, значення лежать у межах від 4.627 до 4.794 г, але гуртуються навколо 4.731 г.

Це Gaussian distribution, у якому ймовірності сягають піку біля середнього й симетрично спадають з обох боків (звідси й «дзвоноподібна» форма). Щоб змоделювати це в програмі, нам потрібен спосіб задати ширину кривої (зазвичай дорогі болти гуртуються щільніше навколо середнього, ніж дешеві!).

За домовленістю для цього використовують standard deviation: малі значення дають гостру вузьку криву, великі - низьку широку. Математики люблять грецькі літери, тож середнє ми позначаємо як μ («мю»), а стандартне відхилення - як σ («сигма»). Тож якщо ми читаємо, що «95% значень лежать у межах 2σ від μ» або що «бозон Гіґґса виявлено з 5-сигма довірою», такі зауваження стосуються стандартного відхилення.

Докладніше про це йтиметься в концепції Statistics.

Функція randn()

Це скорочення від «random normal»; функція схожа на варіант rand() для чисел з плаваючою комою, але значення розподілені за Гаусом із середнім 0 і стандартним відхиленням 1.

Знову ж таки, може знадобитися масштабувати необроблений результат randn під потрібне стандартне відхилення та зсунути його під потрібне середнє. У прикладі нижче результат перетворено на середнє 30 і стандартне відхилення 5.

julia> raw = randn(5)
5-element Vector{Float64}:
  3.0762588867281475
  1.5101100620253902
 -0.5914858221637778
  0.684175554069735
 -0.8416433926114673

julia> raw * 5 .+ 30
5-element Vector{Float64}:
 45.38129443364074
 37.55055031012695
 27.04257088918111
 33.420877770348675
 25.791783036942665

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

Модуль Random

Цей модуль містить наступний рівень функціональності, який не включили в Base, щоб зменшити розмір типової конфігурації Julia.

Random доповнює rand і randn з Base мутувальними версіями rand! і randn!.

Корисне доповнення - randstring, який генерує рядок тексту (англ. string) заданої довжини. Типово він використовує великі й малі літери, а також цифри від 0 до 9, але можна вказати й інші варіанти.

julia> using Random

julia> randstring(20)
"BoJnIxrS33pJiWggXZQV"

Крім того, є функція bitrand, яка генерує випадковий BitArray заданої довжини.

julia> bitrand(5)
julia> bitrand(5)
5-element BitVector:
 1
 1
 0
 0
 1

Перемішування та перестановки

Щоб випадково перемішати елементи у Vector, є shuffle, а також shuffle!, який змінює вхідний вектор на місці.

julia> v = ['A', '1', '2', 'J', 'Q', 'K'];

julia> shuffle(v)
6-element Vector{Char}:
 'K': ASCII/Unicode U+004B (category Lu: Letter, uppercase)
 '1': ASCII/Unicode U+0031 (category Nd: Number, decimal digit)
 'A': ASCII/Unicode U+0041 (category Lu: Letter, uppercase)
 'J': ASCII/Unicode U+004A (category Lu: Letter, uppercase)
 '2': ASCII/Unicode U+0032 (category Nd: Number, decimal digit)
 'Q': ASCII/Unicode U+0051 (category Lu: Letter, uppercase)

# shuffles are random:
julia> shuffle(v)
6-element Vector{Char}:
 '2': ASCII/Unicode U+0032 (category Nd: Number, decimal digit)
 'K': ASCII/Unicode U+004B (category Lu: Letter, uppercase)
 'A': ASCII/Unicode U+0041 (category Lu: Letter, uppercase)
 'Q': ASCII/Unicode U+0051 (category Lu: Letter, uppercase)
 'J': ASCII/Unicode U+004A (category Lu: Letter, uppercase)
 '1': ASCII/Unicode U+0031 (category Nd: Number, decimal digit)

Іноді корисно мати натомість перемішані індекси. Для цього скористаймося randperm(n), де n позначає довжину послідовності.

julia> randperm(6)
6-element Vector{Int64}:
 6
 2
 4
 1
 3
 5

По суті, приклад вище дає ті самі результати, що й shuffle(1:6).

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

Зерна та алгоритми

У Random стандартно вбудовано кілька алгоритмів генератора випадкових чисел (ГВЧ), і будь-хто з належною математичною підготовкою може додати ще. Але такі речі далеко поза межами цього документа!

Значно частіше з ГВЧ працюють, щоб задати seed, завдяки чому послідовність «випадкових» результатів стає відтворюваною від запуску до запуску.

Така відтворюваність недоречна в робочому коді, але допомагає під час тестування й налагодження.

Інші пакунки

Поза Exercism є багато пакунків, які можна встановити, повʼязаних із випадковістю, імовірністю та статистикою. Трохи більше інформації є в концепції Statistics.

Пакунок StatsBase.jl

Більшість функцій StatsBase досить технічні й не стосуються цього документа.

Виняток - StatsBase.sample, яка дає повну реалізацію вибірки з поверненням і без нього (див. попередній розділ вище). Є також функції для зваженої (нерівномірної) вибірки.

Пакунок Distributions.jl

Розподіли uniform і normal (або гаусів) описано вище.

Модуль Random також містить randexp для вибірки з експоненційного розподілу, який повʼязаний із (дуже поширеним) розподілом Пуассона.

Для значно ширшого набору можливостей є пакунок Distributions.jl, розрахований на тих, хто має належну підготовку зі статистики.