tinyrand
1.0.0
tinyrand軽量RNG仕様と錆のいくつかの超高速実装。 tinyrandはno_stdであり、ヒープアロケーターを使用していません。
tinyrand ？stdを必要としません。つまり、埋め込み可能です。マイクロコントローラーと裸金属（OSなし）環境で実行されます。Mockが付属しています。つまり、コードカバレッジを気にかけている場合です。以下は、いくつかの顕著なPRNGの比較です。
| prng | アルゴリズム | 帯域幅（gb/s） | |
|---|---|---|---|
rand | Chacha12 | 2.4 | |
tinyrand | splitmix | 6.5 | |
tinyrand | XORSHIFT | 6.7 | |
fastrand | ワンド | 7.5 | |
tinyrand | ワンド | 14.6 |
TL; DR： tinyrand 、 fastrandよりも2倍高速で、 randよりも6倍高速です。
特定のPRNGが良いかどうかを確実に伝えることは不可能です。答えは確率的です。 3つのアルゴリズムはすべて、テストの頑固な弾幕に対してよく立ち上がっていますが、WyrandとSplitmixはXorshiftよりも少し優れています。 （308億サンプルでテストされています。）これは、 tinyrand十分にランダムに見える数値を生成し、ほとんどのアプリケーションで使用する可能性が高いことを意味します。
tinyrandアルゴリズムは暗号的に安全ではありません。つまり、一連の数字を観察することで次の乱数を推測することが可能です。 （または、前述の数字、その点について。）堅牢なcsprngが必要な場合は、 randと一緒に行くことを強くお勧めします。 csprngsは一般にはるかに遅く、ほとんどの人は必要ありません。
cargo add tinyrand数値を生成するには、 Randインスタンスが必要です。ここでは、デフォルト/推奨RNGのエイリアスであるStdRandを使用します。 （現在、 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を生成することです。また、バイナリの結果に重み付けを割り当てたいかもしれません。
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 ;
} RandのDefault::default()を呼び出して、一定の種子で初期化します。これは再現性に最適ですが、同じ「ランダム」な数値が同じように実行されます。これは、ほとんどの人が必要とするものではありません。
tinyrandはno_stdクレートであり、悲しいことに、基礎となるプラットフォームについて仮定を行うことができない場合、エントロピーを生成するための良い、ポータブルな方法はありません。ほとんどのアプリケーションでは、1つはクロックかもしれませんが、 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 、ナノ秒タイムスタンプの上部64ビット（ SystemTimeから）を下部64ビットでXAREDすることにより、 u64を導き出します。暗号化には適していませんが、ほとんどの一般的なアプリケーションには十分です。
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特性の動作をock笑するだけでなく、関連する特性法の特定のグループが呼び出されたタイプの数も検証できます。
代表者はテストケースによって指定され、モックインスタンスはRand実装としてテスト中のシステムに渡されます。現在、3つのデリゲートタイプがサポートされています。
FnMut(&State) -> u128 - next_uXX()メソッドのいずれかがmockで呼び出されたときに呼び出されます。 （ uXXはu16 、 u32 、 u64 、 u128またはusizeの1つです。）デリゲートは、幅128ビットまでの次の「ランダム」数を返します。幅は、 Randがサポートする最も広いタイプであるu128に対応するように設計されています。狭いタイプの1つが要求された場合、模擬は単に低いビットを返します。 （たとえば、 u32の場合、モックされた値はフードの下でas u32使用して切り捨てられます。）FnMut(Surrogate, Probability) -> bool - next_bool(Probability)メソッドが呼び出されたときに呼び出されます。FnMut(Surrogate, u128) -> u128 - next_limまたはnext_rangeいずれかが呼び出された場合。絶対的な基本から始めて、 next_uXX()をmockして定数を返します。次に、モックが何回呼ばれたかを確認します。
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 Delegateのみを提供することで、 Rand特性の他のすべての方法の結果に影響を与えることができます。これらはすべて同じランダム性のソースに由来し、最終的にはデリゲートをフードの下に呼び出すからです...理論的に！実際には、物事はもっと複雑です。
next_bool(Probability) 、 next_lim(uXX) 、 next_range(Range)などの派生したRandメソッドは、異なる確率分布に裏付けられています。たとえば、 next_bool Bernoulliの分布から引き出されますが、 next_limとnext_range 、追加の層を追加したスケーリングされた均一な分布を使用します。さらに、さまざまな分布間のマッピングは、変更の対象となる内部実装の詳細です。 Debiasingレイヤーだけには、さまざまな幅の種類に最適化されたいくつかの実装があります。言い換えれば、 next_u128からnext_bool 、 next_lim 、 next_rangeおよびnontrivialへのマッピング。計算機とモジュラー算術の知識なしでock笑したいものではありません。
幸いなことに、 Randこれらのマッピング機能を「バイパス」することができます。これは、他の2人の代表者が登場する場所です。次の例では、 next_boolの結果をock笑します。
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 Delegateには、 Surrogate structが渡されます。これは、 Rand実装であり、Invocation Stateのキーパーです。代理人は、私たちがboolを導き出すことを可能にします：そうです：
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メソッドの両方をmock笑するために使用されます。ボンネットのM M N 、 next_range next_limにN者next_range(M..N) Mしますnext_lim(N - M)これが実際にすべてock笑される方法です：
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テストプロセスは4つの層に分割されます。
tinyrandの元素の正気を主張するために使用されます。言い換えれば、コードのすべての行は少なくとも一度は行使されます。基本的な期待は支持されており、些細な欠陥はない可能性があります。tinyrandを構成するPRNGの特定の特性を検証します。これらは、ソースがランダム（帰無仮説）であると仮定し、この仮定を払拭する証拠（代替仮説）を探す正式な仮説テストです。単体テストは、数値性を主張することを目的としていません。それらは本質的に純粋に機能的です。目的は次のとおりです。
tinyrand 、コードの行が実証されていない場合、削除する必要があるという哲学に基づいて構築されています。この規則には例外はありません。boolの生成におけるtrue結果とfalse重み付け。均一な分布からカスタム分布へのマッピングのための機能は、わずかなものであり、衰弱層が必要です。 tinyrand 、単語の幅に応じて異なる脱毛方法を使用します。ドメイン変換テストの目的は、この機能が期待どおりに機能しており、拒絶サンプリングが行われていることを確認することです。ただし、衰弱の数値特性は検証されません。 合成ベンチマークは、結果をピアライブラリと比較して、 tinyrand PRNGのホットパスを行使するために使用されます。ベンチマークでは、さまざまな単語の長さ、変換/beasing、および加重boolの生成で数値の生成をテストします。これらのベンチマークのサブセットもCIテストに含まれているため、COMMINDバージョン全体でtinyrandのパフォーマンスを比較するのが少し簡単です。
tinyrand 、Diehard、Dieharder、Nist SP 800-22などに触発された統合された統計テストスイートにバンドルされています。 tinyrand Suiteは、これらのテストのいずれよりもはるかに小さいことは明らかです。意図は、この分野ですでに実質的で容易にアクセス可能な作業を再現することではなく、一般的な異常を検出するのに非常に効果的であり、すべてのコミットで実行されるのに十分な速度であるセーフティネットを作成することです。
次のテストが含まれています。
Randインスタンスで一連のベルヌーリトライアルを実施し、ビットが1に設定されている回数が予想範囲内にあることを確認します。後続の各試験で、マスクは左にシフトされ、仮説が再テストされます。テストは数サイクルにわたって進行します。 64個のベルヌーリトライアル（ u64のビットごとに1つ）を含む各サイクル。boolを取得します。このテストでは、各試験で異なる（ランダムに選択された）重み付けを伴う一連のベルヌーリトライアルで構成され、一連のコインフリップをシミュレートします。各トライアル内で、H0はソースがランダムであると主張します。 （つまり、「ヘッド」の数は統計的に許容される間隔内に収まります。）u64のMSBセグメントとLSBセグメントを交互に採取することによって採取されています。各トライアルでは、個々のビットの値が0.5の確率でIIDであると仮定し、ビットが1に設定されている回数が予想範囲内であることを確認します。ランダムソースの場合、1（および0s）の数はベルヌーリプロセスに従います。 tinyrandのそれぞれのテストは、独自のPRNGに対してだけでなく、テストの有効性を検証するために使用される意図的に誤った実装に対しても行使されます。テストは、正しいPRNGのH0を一貫して拒否し、故障したものについてH1を受け入れることに失敗する必要があります。
統計テスト自体はランダム値からシードされます。ランダム性は、テスト中のPRNGをシードするために使用され（すべての試行が独立してシードされます）、ベルヌーリの実験に重み付けを割り当て、変換関数と債務をテストするための整数範囲を選択、衝突のテストのためのコントロール値などを選択します。 randパッケージをコントロールPRNGとして使用して、 tinyrandの欠陥が不注意にテストをマスクする方法でテストを覆すことができないようにします。テストはシードされているため、パラメーター空間を介してランダムな遠足をしているように見えますが、パラメーターの選択は完全に決定的であり、したがって再現可能です。これは、特にCI環境では断続的に発生することを許可してはならないタイプIエラー（帰無仮説を誤って拒否する）の可能性のために不可欠です。言い換えれば、ランダム性のテストを偶然に任せることはできません。
ランダム性仮説をテストする1つの方法は、パラメーターのセット（整数N範囲M ..またはベルヌーリ分布からtrueの取得の確率）を選択し、大きなランダムサンプルで異常を求めて長期的に実行することです。 。理論的根拠は、サンプルが大きいほど、検出可能な異常が含まれる可能性が高いということです。これは一般に、非常に特定の条件下でのみPRNGに影響を与える可能性のある特定の種類の異常を発見するのにあまり効果的ではありません。たとえば、書かれていない衰弱関数は、ほとんどの小整数範囲やいくつかの大きな範囲（2つの力に近いもの）でも依然としてうまく機能する可能性があります。テストがパラメーターを不利に選択した場合、それらのパラメーターをどれほど徹底的にテストしても、異常を見つけられない場合があります。
PRNGをテストするより良い方法は、テスト体制に多様性を導入することです。これは、非常に大きな試験ではなく、異なるパラメーターで多数の小さな試験を実施します。これはまさにtinyrand統計テストが行うことです。ランダムに（ただし決定論的に）選択されたパラメーターを使用していくつかの試験を実施します。これにより、複数の比較問題がすぐに公開されます。先験的な理想的なPRNGを考えてみましょう。合意された尺度に従って「ランダム」に見える数値を頻繁に生成します。しかし、時には、同じ尺度によって非ランダムに見える出力を生成します。たとえば、理想的なソースでさえ、非常に長期的なものやゼロを生成します。実際、そうしないと、それを非ランダムにすることもできます。残念ながら、これにより、最もリラックスしたテストでも失敗するp値が生成されます...ある時点で。これは単一の仮説検査の問題ですが、複数の仮説検査では比例して悪化しています。
tinyrandビルトインテストは、Holm-Bonferroni順次補正法を使用してこの問題に対処します。 Holm-Bonferroni補正は、タイプIのエラーを抑制し、適切な統計的パワーを維持しながら、タイプIIエラーの抑制を維持します。 tinyrandのニーズに合わせてパフォーマンスが発生しているようです。特に、数の試行が一般的に100〜1000の範囲に保たれていることがわかります。 （ tinyrandテストは非常に速いように設計されており、試行の数に実用的な拘束力を置いています。理想的には、すべての統計テストは、定期的な開発フローの一部として義務付けられるために数秒以内に完了するはずです。）
Dieharder Test Suiteは、Marsagliaのオリジナルの頑固なテストバッテリーを拡張します。多数のテストにバンドルされており、完了するまでに長い時間（〜1時間）かかります。 tinyrandは、ランダム出力をDeiharderにポンピングするためのユーティリティがあります。これは通常、アドホックベースで実行されます。 PRNGが材料の変更を受けるときに頑固なバッテリーを実行する必要があります。これはまれです。PRNGアルゴリズムが実装されると、リファクタリングまたは何らかの欠陥が見つからない限り、通常は触れられないままです。 Dieharderは、おそらくtinyrandで実験的なPRNGを構築およびテストするのに役立ちます。他の3つのテスト層は、 tinyrandパッケージのメンテナンスに十分です。
tinyrand Dieharderに対して実行するには：
cargo run --release --bin random -- wyrand 42 binary 1T | dieharder -g 200 -a上記のコマンドは、1兆個の64ビット単語を超えるバイナリ出力を生成し、数字42でシードされたWyrand PRNGを使用しています。それはstdoutがdieharderに汲み上げられています。 （実際には、Dieharderは310億件未満の数を消費します。）
注意事項：Dieharderには、複数の仮説テストでタイプIエラーを扱うメカニズムはありません。これは、テストのパラメーターだけでなくタイプが異なるためです。 Dieharderは、個々のテストの範囲に仮説テストを制限します。 PRNGを合格したテストの数に基づいて適合または不適格であると分類する包括的な仮説はありません。そうしないと、タイプIエラーを説明するために信頼レベルを調整します。
