tinyrand
1.0.0
tinyrand Легкая спецификация RNG и несколько сверхбыстрых реализаций в ржавчине. tinyrand - это no_std и не использует распределитель кучи.
tinyrand ?std , что означает, что он встроен-он работает на микроконтроллерах и средах с обнаженным металлом (без ОС).Mock для тестирования кода, который зависит от случайных чисел. То есть, если вы заботитесь о покрытии кода.Ниже приведено сравнение нескольких известных PRNG.
| Прозрачный | Алгоритм | Пропускная способность (ГБ/с) | |
|---|---|---|---|
rand | Чача12 | 2.4 | |
tinyrand | Splitmix | 6.5 | |
tinyrand | Xorshift | 6.7 | |
fastrand | Уиран | 7,5 | |
tinyrand | Уиран | 14.6 |
TL; DR: tinyrand в 2 раза быстрее, чем fastrand и в 6 раз быстрее, чем rand .
Невозможно определить, хорош ли определенный PRNG; Ответ вероятносен. Все три алгоритма хорошо противостоят испытанию испытаний, но Wyrand и Splitmix немного лучше, чем Xorshift. (Протестировано на 30,8 миллиарда образцов.) Это означает, что tinyrand производит числа, которые кажутся достаточно случайными и, вероятно, подходят для использования в большинстве приложений.
Алгоритмы tinyrand не являются криптографически безопасными, что означает, что можно угадать следующее случайное число, наблюдая последовательность чисел. (Или в предыдущих числах, в этом отношении.) Если вам нужен надежный CSPRNG, настоятельно предполагает, чтобы вы пошли с rand . CSPRNG, как правило, намного медленнее, и большинству людей не нужны.
cargo add tinyrand Для генерации чисел требуется экземпляр Rand . Здесь мы используем StdRand , который является псевдонимом для по умолчанию/рекомендованному RNG. (В настоящее время установлена на Wyrand , но может измениться в будущем.)
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
for _ in 0 .. 10 {
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ;
}Точно так же мы можем генерировать количество других типов:
use tinyrand :: { Rand , StdRand } ;
let mut rand = StdRand :: default ( ) ;
let num = rand . next_u128 ( ) ;
println ! ( "generated wider {num}" ) ; Методы next_uXX генерируют числа во всем диапазоне без знака указанного типа. Часто мы хотим число в определенном диапазоне:
use tinyrand :: { Rand , StdRand , RandRange } ;
let mut rand = StdRand :: default ( ) ;
let tasks = vec ! [ "went to market" , "stayed home" , "had roast beef" , "had none" ] ;
let random_index = rand . next_range ( 0 ..tasks . len ( ) ) ;
let random_task = tasks [ random_index ] ;
println ! ( "This little piggy {random_task}" ) ; Другим общим вариантом использования является генерирование bool S. Мы также могли бы назначить взвешивание бинарным результатам:
use tinyrand :: { Rand , StdRand , Probability } ;
let mut rand = StdRand :: default ( ) ;
let p = Probability :: new ( 0.55 ) ; // a slightly weighted coin
for _ in 0 .. 10 {
if rand . next_bool ( p ) {
// expect to see more heads in the (sufficiently) long run
println ! ( "heads" ) ;
} else {
println ! ( "tails" ) ;
}
}Есть моменты, когда нам нужно некоторое время спать, ожидая условия. Когда многие потоки спят, обычно рекомендуется, чтобы они отключались случайным образом, чтобы избежать давления.
use tinyrand :: { Rand , StdRand , RandRange } ;
use core :: time :: Duration ;
use std :: thread ;
use tinyrand_examples :: SomeSpecialCondition ;
let mut rand = StdRand :: default ( ) ;
let condition = SomeSpecialCondition :: default ( ) ;
let base_sleep_micros = 10 ;
let mut waits = 0 ;
while !condition . has_happened ( ) {
let min_wait = Duration :: ZERO ;
let max_wait = Duration :: from_micros ( base_sleep_micros * 2u64 . pow ( waits ) ) ;
let random_duration = rand . next_range ( min_wait..max_wait ) ;
println ! ( "backing off for {random_duration:?}" ) ;
thread :: sleep ( random_duration ) ;
waits += 1 ;
} Вызов Default::default() на Rand инициализирует его с постоянным семенем. Это отлично подходит для повторяемости, но приводит к одному и тому же прогону «случайных» чисел, что не является тем, что нужно большинству людей.
tinyrand - это ящик no_std , и, к сожалению, нет хорошего, портативного способа генерации энтропии, если нельзя сделать предположения о базовой платформе. В большинстве приложений можно было бы часы, но что -то столь же тривиальное, как SystemTime::now().duration_since(SystemTime::UNIX_EPOCH) может быть не всегда доступно.
Если у вас есть источник энтропии в вашем распоряжении, вы можете заселить Rrnd , так же:
use tinyrand :: { Rand , StdRand , Seeded } ;
let seed = tinyrand_examples :: get_seed_from_somewhere ( ) ; // some source of entropy
let mut rand = StdRand :: seed ( seed ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Вы также можете рассмотреть возможность использования getrandom , который является кроссплатформенным методом для извлечения данных энтропии.
Если кто -то не заботится о no_std , они не должны быть связаны его ограничениями. Чтобы посетить с системных часов, вы можете выбрать std :
cargo add tinyrand-std Теперь у нас ClockSeed в нашем распоряжении, что также реализует черту Rand . ClockSeed получает u64 , приписывая верхнюю 64 бита наносекундной метки времени (из SystemTime ) с нижними 64 битами. Это не подходит для криптографического использования, но будет достаточно для большинства приложений общего назначения.
use tinyrand :: { Rand , StdRand , Seeded } ;
use tinyrand_std :: clock_seed :: ClockSeed ;
let seed = ClockSeed :: default ( ) . next_u64 ( ) ;
println ! ( "seeding with {seed}" ) ;
let mut rand = StdRand :: seed ( seed ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Крэт tinyrand-std также включает в себя внедорожную реализацию Rand с нитью:
use tinyrand :: Rand ;
use tinyrand_std :: thread_rand ;
let mut rand = thread_rand ( ) ;
let num = rand . next_u64 ( ) ;
println ! ( "generated {num}" ) ; Хорошее покрытие тестирования иногда может быть трудно достичь; Вдвойне, когда приложения зависят от случайности или других источников нетерминизма. tinyrand поставляется с фиктивным RNG, который предлагает мелкозернистый контроль над выполнением вашего кода.
Макет использует ящик alloc , поскольку он требует распределения кучей закрытий. Таким образом, макет распространяется в виде пакета сборов:
cargo add tinyrand-alloc На низовом уровне Mock - это структура, настроенная с горсткой делегатов . Делегат - это закрытие, которое вызывается макетом, когда конкретный метод признака вызывается тестируемой системой. Макет также поддерживает внутреннее состояние вызова, которое отслеживает количество раз, когда был осуществлен конкретный делегат. Таким образом, вы можете не только издеваться над поведением признака Rand , но и проверить количество типов, которую была вызвана конкретная группа связанных методов признаков.
Делегаты указываются с помощью тестового примера, в то время как максимальный экземпляр передается в тестовую систему в качестве реализации Rand . В настоящее время поддерживаются три типа делегатов:
FnMut(&State) -> u128 -вызывается, когда на макете вызывается один из методов next_uXX() . ( uXX является одним из u16 , u32 , u64 , u128 или usize .) Делегат возвращает следующее «случайное» число, которое может иметь ширину до 128 бит. Ширина предназначена для размещения u128 - самый широкий тип, поддерживаемый Rand . Если запрашивается один из более узких типов, макет просто возвращает нижние биты. (Например, для u32 высмеиваемое значение усекается с помощью as u32 под капотом.)FnMut(Surrogate, Probability) -> bool -вызывается при вызове метода next_bool(Probability) .FnMut(Surrogate, u128) -> u128 -Когда вызывается либо next_lim , либо next_range . Начиная с абсолютных оснований, давайте высмеивать next_uXX() , чтобы вернуть константу. Затем мы проверим, сколько раз наше было вызвано нашим макетом.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |_| 42 ) ;
for _ in 0 .. 10 {
assert_eq ! ( 42 , rand.next_usize ( ) ) ; // always 42
}
assert_eq ! ( 10 , rand.state ( ) .next_u128_invocations ( ) ) ; Хотя этот сценарий на самом деле довольно распространен, хотя и смущающе прост. То же самое может быть достигнуто с помощью fixed(uXX) функции.
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , fixed } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( fixed ( 42 ) ) ;
assert_eq ! ( 42 , rand.next_usize ( ) ) ; // always 42Поскольку делегаты являются регулярными закрытиями, мы можем связываться с переменными в прицеле. Это дает нам почти неограниченный контроль над поведением нашего макета.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
use core :: cell :: RefCell ;
let val = RefCell :: new ( 3 ) ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |_| * val . borrow ( ) ) ;
assert_eq ! ( 3 , rand.next_usize ( ) ) ;
// ... later ...
* val . borrow_mut ( ) = 17 ;
assert_eq ! ( 17 , rand.next_usize ( ) ) ;Делегат может быть переназначен в любой момент, даже после того, как макет был создан и осуществлен:
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , fixed } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( fixed ( 42 ) ) ;
assert_eq ! ( 42 , rand.next_usize ( ) ) ;
rand = rand . with_next_u128 ( fixed ( 88 ) ) ; // the mock's behaviour is now altered
assert_eq ! ( 88 , rand.next_usize ( ) ) ; Подпись делегата next_u128 принимает ссылку State , которое отражает количество раз, когда макет был вызван. (Подсчет увеличивается только после завершения вызова.) Давайте напишем макет, который возвращает «случайное» число, полученное из состояния вызова.
use tinyrand :: Rand ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_u128 ( |state| {
// return number of completed invocations
state . next_u128_invocations ( ) as u128
} ) ;
assert_eq ! ( 0 , rand.next_usize ( ) ) ;
assert_eq ! ( 1 , rand.next_usize ( ) ) ;
assert_eq ! ( 2 , rand.next_usize ( ) ) ; Это полезно, когда мы ожидаем, что макет будет вызван несколько раз, и каждый вызов должен вернуть другой результат. Аналогичный результат может быть достигнут с помощью функции counter(Range) , которая проходит через указанный диапазон чисел, удобно обертываясь на границе:
use tinyrand :: Rand ;
use tinyrand_alloc :: { Mock , counter } ;
let mut rand = Mock :: default ( ) . with_next_u128 ( counter ( 5 .. 8 ) ) ;
assert_eq ! ( 5 , rand.next_usize ( ) ) ;
assert_eq ! ( 6 , rand.next_usize ( ) ) ;
assert_eq ! ( 7 , rand.next_usize ( ) ) ;
assert_eq ! ( 5 , rand.next_usize ( ) ) ; // start again Предоставляя только делегат next_u128 , мы можем повлиять на результат любого другого метода в признаке Rand , потому что все они вытекают из одного и того же источника случайности и в конечном итоге будут называть нашего делегата под капотом ... в теории! На практике все намного сложнее.
Полученные методы Rand , такие как next_bool(Probability) , next_lim(uXX) и next_range(Range) поддерживаются различными распределениями вероятностей. Например, next_bool извлекает из распределения Бернулли, тогда как next_lim и next_range используют масштабированное равномерное распределение с добавленным слоем дебийса. Кроме того, картирование между различными распределениями является внутренней детализацией реализации, которая может быть изменена. Только у слоя дебийса есть несколько реализаций, оптимизированных для типов различной ширины. Другими словами, сопоставления от next_u128 до next_bool , next_lim и next_range и nontrivial; Это не то, что вы захотите издеваться без калькулятора и некоторых знаний о модульной арифметике.
К счастью, Rand позволяет нам «обходить» эти функции отображения. Именно здесь появляются два других делегата. В следующем примере мы издеваются над результатом next_bool .
use tinyrand :: { Rand , Probability } ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_bool ( |_ , _| false ) ;
if rand . next_bool ( Probability :: new ( 0.999999 ) ) {
println ! ( "very likely" ) ;
} else {
// we can cover this branch thanks to the magic of mocking
println ! ( "very unlikely" ) ;
} Делегату next_bool вручено Surrogate структуру, которая является как реализацией Rand , так и хранителем состояния вызова. Суррогат позволяет нам получить bool S, как так:
use tinyrand :: { Rand , Probability } ;
use tinyrand_alloc :: Mock ;
let mut rand = Mock :: default ( ) . with_next_bool ( |surrogate , _| {
surrogate . state ( ) . next_bool_invocations ( ) % 2 == 0
} ) ;
assert_eq ! ( true , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( false , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( true , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;
assert_eq ! ( false , rand.next_bool ( Probability ::new ( 0.5 ) ) ) ;Суррогат также позволяет делегату вызывать издевательные методы из макета.
Последний делегат используется для издевания как методов next_lim , так и next_range из -за их изоморфизма. Под капюшоном, next_range делегаты в next_lim , так что для любой пары предельных границ ( M , N ), M < N , next_range(M..N) = M + next_lim(N - M) . Вот как все издевалось на практике:
use tinyrand :: { Rand , RandRange } ;
use tinyrand_alloc :: Mock ;
enum Day {
Mon , Tue , Wed , Thu , Fri , Sat , Sun
}
const DAYS : [ Day ; 7 ] = [ Day :: Mon , Day :: Tue , Day :: Wed , Day :: Thu , Day :: Fri , Day :: Sat , Day :: Sun ] ;
let mut rand = Mock :: default ( ) . with_next_lim_u128 ( |_ , _| 6 ) ;
let day = & DAYS [ rand . next_range ( 0 .. DAYS . len ( ) ) ] ;
assert ! ( matches! ( day, Day :: Sun ) ) ; // always a Sunday
assert ! ( matches! ( day, Day :: Sun ) ) ; // yes!!!tinyrand ? В этом разделе кратко описывается подход к тестированию tinyrand . Он предназначен для тех, кто -
Процесс тестирования tinyrand разделен на четыре уровня:
tinyrand . Другими словами, каждая строка кода осуществляется хотя бы один раз, фундаментальные ожидания остаются в силе, и , вероятно, нет тривиальных дефектов.tinyrand . Это формальные тесты гипотезы, которые предполагают, что источник является случайным (нулевая гипотеза), и ищут доказательства для развеяния этого предположения (альтернативная гипотеза).Модульные тесты не направлены на утверждение численных качеств; Они являются чисто функциональными по своей природе. Цели включают -
tinyrand построен на философии, что если строка кода не осуществляется, она должна быть удалена. Нет никаких исключений из этого правила.true результата по сравнению false в генерации bool . Функции для картирования от равномерного распределения до пользовательского, нетривиальные и требуют слоя дебийса. tinyrand использует разные методы дебисирования в зависимости от ширины слова. Цель тестов преобразования домена состоит в том, чтобы убедиться, что эта функция работает, как и ожидалось, и происходит отбор отказа. Однако это не проверяет числовые свойства дебийского обмена. Синтетические тесты используются для использования горячих путей tinyrand PRNG, сравнивая результаты с библиотеками сверстников. Цитрицы проверяют генерацию чисел в различных длинах слов, преобразованиях/дебийском языке и генерации взвешенных bool . Подмножество этих критериев также включено в тесты CI, что облегчает сравнение производительности tinyrand в рамках версий коммит.
tinyrand поставляется в комплекте с интегрированным статистическим набором тестирования, вдохновленным такими, как Diehard, Dieharder и Nist SP 800-22. Комната tinyrand , по общему признанию, намного меньше, чем любой из этих тестов; Намерение состоит не в том, чтобы повторить уже существенную и легкодоступную работу в этой области, а для создания сети безопасности, которая очень эффективна для обнаружения общих аномалий и достаточно быстро, чтобы их можно было запустить на каждом коммите.
Следующие тесты включены.
Rand , маскируя значение одного бита, подтверждая, что количество раз, когда бит устанавливается на 1, находится в ожидаемом диапазоне. Для каждого последующего испытания маска смещается на одно слева, и гипотеза повторно. Тест проходит в течение нескольких циклов; Каждый цикл содержит 64 испытания в Бернулли (по одному для каждого бита u64 ).bool с выбранной вероятностью из 64-разрядного слова без знака. Тест включает в себя серию испытаний Бернулли с различным (случайно выбранным) взвешиванием на каждом испытании, имитируя пробег с монетами. В каждом исследовании H0 утверждает, что источник является случайным. (Т.е. количество «голов» попадает в статистически приемлемый интервал.)u64 S в отдельных испытаниях. В каждом испытании мы предполагаем, что значения отдельных битов являются IID с вероятностью 0,5, что подтверждает, что количество раз, когда бит устанавливается на 1, находится в пределах ожидаемого диапазона. Для случайного источника число 1s (и 0s) следует за процессом Бернулли. Каждый из тестов tinyrand осуществляется не только против своих собственных PRNG, но и против преднамеренно неисправных реализаций, которые используются для проверки эффективности теста. Тесты должны последовательно не отклонять H0 для правильных PRNG и принимать H1 для неисправных.
Статистические тесты сами высевают из случайных значений. Случайность используется для заселения тестирования PRNG (каждое исследование независимо засеяно), присваивать веса для экспериментов в Бернулли, выберите целые диапазоны для тестирования функций преобразования и освоения, контрольных значений для тестирования столкновений и т. Д. Мы используем пакет rand в качестве управляющего PRNG, так что дефект в tinyrand не может непреднамеренно подорвать тест таким образом, чтобы маскировать себя. Тесты просеяются таким образом, чтобы, хотя они, по -видимому, находятся на случайной экскурсии через пространство параметров, их выбор параметров является полностью детерминированным и, следовательно, повторяемым. Это важно из -за возможности ошибки типа I (неправильно отвергающего нулевую гипотезу), которая не должна возникать периодически, особенно в средах CI. Другими словами, тестирование случайности не может быть оставлено на случайность .
Один из способов проверки гипотезы о случайности - выбрать набор параметров (например, диапазон целочисленного генерации M .. N или вероятность получения true от распределения Бернулли) и выполнить длительный пробег, искать аномалии в большой случайной выборке Полем Обоснование состоит в том, что чем больше образец, тем более вероятно, что он будет содержать обнаруживаемую аномалию. Как правило, это не очень эффективно для определения определенных видов аномалий, которые могут влиять на PRNG только в очень специфических условиях. Например, плохо написанная функция дебисирования может по -прежнему работать хорошо для большинства небольших целочисленных диапазонов и даже некоторых крупных (те, которые близки к силам двух). Если тест выбирает параметры неблагоприятно, он может не найти аномалии, независимо от того, насколько исчерпывающе он проверяет эти параметры.
Гораздо лучший способ тестирования PRNG - ввести разнообразие в режим тестирования - провести большое количество небольших испытаний с различными параметрами, а не одним, очень большим испытанием. Это именно то, что проводят статистические тесты tinyrand - проводят несколько испытаний со случайным образом (но детерминистически) выбранными параметрами. Это немедленно раскрывает проблему множественных сравнений. Рассмотрим априорный идеальный PRNG. Он часто генерирует числа, которые будут выглядеть «случайными» в соответствии с некоторой согласованной мерой. Но иногда он будет производить выход, который будет выглядеть неслучайно по той же мере. Например, даже идеальный источник будет создавать очень длинный пробег или нулевые нули. На самом деле, неспособность сделать это также сделает это неровным. К сожалению, это даст p-значение, которое потерпит неудачу даже на самом расслабленном тесте ... в какой-то момент. Это проблема для тестирования единой гипотезы, но он пропорционально усугубляется в множественном тестировании гипотез.
Встроенные тесты tinyrand решают эту проблему с использованием метода последовательной коррекции Holm-Bonferroni. Коррекция Holm-Bonferroni подавляет ошибки типа I при сохранении хорошей статистической мощности-подавление ошибок типа II. Похоже, что он хорошо работает для потребностей tinyrand , особенно видя, что количество испытаний обычно хранится в диапазоне 100–1000. (Тесты tinyrand предназначены для того, чтобы быть очень быстрыми, что прилагает практическое связанное с количеством испытаний - в идеале все статистические тесты должны выполнять в течение нескольких секунд, чтобы они были предприняты как часть рутинного потока развития.)
The Deharder Test Suite расширяет оригинальную батарею испытаний Marsaglia. Он связан с большим количеством тестов и занимает много времени (~ 1 час), чтобы завершить. tinyrand имеет утилиту для перекачивания случайных выводов в Dieharder, который обычно работает на специальной основе. Батарея -несчастная батарея должна работать, когда PRNG претерпевает изменение материала, которое редко - после реализации алгоритма PRNG, он, как правило, остается нетронутым, если только он не рефактор, либо какой -то дефект не найден. Deharder, возможно, более полезен для строительства и тестирования экспериментальных PRNG с tinyrand . Другие три уровня тестов достаточны для обслуживания пакета tinyrand .
Чтобы бежать tinyrand против несгибаемости:
cargo run --release --bin random -- wyrand 42 binary 1T | dieharder -g 200 -a Вышеупомянутая команда использует Wyrand PRNG, посеянный номером 42, генерируя двоичный выход более 1 триллиона 64-битных слов. Это stdout накачивается для dieharder . (На практике Dieharder будет потреблять менее 31 миллиарда номеров.)
Слово осторожности: у анти -заработавшего нет механизма для решения ошибок типа I при многократном тестировании гипотез - отчасти потому, что тесты различаются по типу, а не только по параметрам. Dieharder ограничивает гипотезу тестирование на область индивидуального теста; Не существует всеобъемлющей гипотезы, которая классифицирует PRNG как подходящий или не подходящий на основе количества проходящих тестов, или иным образом корректирует уровень достоверности, чтобы учесть ошибки типа I.
