]>
Commit | Line | Data |
---|---|---|
0731742a XL |
1 | // Copyright 2018 Developers of the Rand project. |
2 | // Copyright 2013-2017 The Rust Project Developers. | |
b7449926 XL |
3 | // |
4 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
5 | // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
6 | // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your | |
7 | // option. This file may not be copied, modified, or distributed | |
8 | // except according to those terms. | |
9 | ||
416331ca | 10 | //! Generating random samples from probability distributions |
b7449926 XL |
11 | //! |
12 | //! This module is the home of the [`Distribution`] trait and several of its | |
13 | //! implementations. It is the workhorse behind some of the convenient | |
416331ca XL |
14 | //! functionality of the [`Rng`] trait, e.g. [`Rng::gen`], [`Rng::gen_range`] and |
15 | //! of course [`Rng::sample`]. | |
b7449926 XL |
16 | //! |
17 | //! Abstractly, a [probability distribution] describes the probability of | |
18 | //! occurance of each value in its sample space. | |
19 | //! | |
20 | //! More concretely, an implementation of `Distribution<T>` for type `X` is an | |
21 | //! algorithm for choosing values from the sample space (a subset of `T`) | |
22 | //! according to the distribution `X` represents, using an external source of | |
23 | //! randomness (an RNG supplied to the `sample` function). | |
24 | //! | |
25 | //! A type `X` may implement `Distribution<T>` for multiple types `T`. | |
26 | //! Any type implementing [`Distribution`] is stateless (i.e. immutable), | |
27 | //! but it may have internal parameters set at construction time (for example, | |
28 | //! [`Uniform`] allows specification of its sample space as a range within `T`). | |
29 | //! | |
30 | //! | |
31 | //! # The `Standard` distribution | |
32 | //! | |
33 | //! The [`Standard`] distribution is important to mention. This is the | |
dfeec247 | 34 | //! distribution used by [`Rng::gen`] and represents the "default" way to |
b7449926 XL |
35 | //! produce a random value for many different types, including most primitive |
36 | //! types, tuples, arrays, and a few derived types. See the documentation of | |
37 | //! [`Standard`] for more details. | |
38 | //! | |
39 | //! Implementing `Distribution<T>` for [`Standard`] for user types `T` makes it | |
dfeec247 XL |
40 | //! possible to generate type `T` with [`Rng::gen`], and by extension also |
41 | //! with the [`random`] function. | |
b7449926 | 42 | //! |
416331ca | 43 | //! ## Random characters |
dfeec247 | 44 | //! |
416331ca XL |
45 | //! [`Alphanumeric`] is a simple distribution to sample random letters and |
46 | //! numbers of the `char` type; in contrast [`Standard`] may sample any valid | |
47 | //! `char`. | |
48 | //! | |
b7449926 | 49 | //! |
416331ca | 50 | //! # Uniform numeric ranges |
b7449926 XL |
51 | //! |
52 | //! The [`Uniform`] distribution is more flexible than [`Standard`], but also | |
53 | //! more specialised: it supports fewer target types, but allows the sample | |
54 | //! space to be specified as an arbitrary range within its target type `T`. | |
55 | //! Both [`Standard`] and [`Uniform`] are in some sense uniform distributions. | |
56 | //! | |
57 | //! Values may be sampled from this distribution using [`Rng::gen_range`] or | |
58 | //! by creating a distribution object with [`Uniform::new`], | |
59 | //! [`Uniform::new_inclusive`] or `From<Range>`. When the range limits are not | |
60 | //! known at compile time it is typically faster to reuse an existing | |
61 | //! distribution object than to call [`Rng::gen_range`]. | |
62 | //! | |
63 | //! User types `T` may also implement `Distribution<T>` for [`Uniform`], | |
64 | //! although this is less straightforward than for [`Standard`] (see the | |
416331ca | 65 | //! documentation in the [`uniform`] module. Doing so enables generation of |
b7449926 XL |
66 | //! values of type `T` with [`Rng::gen_range`]. |
67 | //! | |
416331ca | 68 | //! ## Open and half-open ranges |
b7449926 XL |
69 | //! |
70 | //! There are surprisingly many ways to uniformly generate random floats. A | |
71 | //! range between 0 and 1 is standard, but the exact bounds (open vs closed) | |
72 | //! and accuracy differ. In addition to the [`Standard`] distribution Rand offers | |
416331ca XL |
73 | //! [`Open01`] and [`OpenClosed01`]. See "Floating point implementation" section of |
74 | //! [`Standard`] documentation for more details. | |
b7449926 | 75 | //! |
416331ca | 76 | //! # Non-uniform sampling |
b7449926 | 77 | //! |
416331ca XL |
78 | //! Sampling a simple true/false outcome with a given probability has a name: |
79 | //! the [`Bernoulli`] distribution (this is used by [`Rng::gen_bool`]). | |
b7449926 | 80 | //! |
416331ca XL |
81 | //! For weighted sampling from a sequence of discrete values, use the |
82 | //! [`weighted`] module. | |
b7449926 | 83 | //! |
416331ca XL |
84 | //! This crate no longer includes other non-uniform distributions; instead |
85 | //! it is recommended that you use either [`rand_distr`] or [`statrs`]. | |
b7449926 XL |
86 | //! |
87 | //! | |
88 | //! [probability distribution]: https://en.wikipedia.org/wiki/Probability_distribution | |
416331ca XL |
89 | //! [`rand_distr`]: https://crates.io/crates/rand_distr |
90 | //! [`statrs`]: https://crates.io/crates/statrs | |
91 | ||
dfeec247 | 92 | //! [`random`]: crate::random |
416331ca XL |
93 | //! [`rand_distr`]: https://crates.io/crates/rand_distr |
94 | //! [`statrs`]: https://crates.io/crates/statrs | |
b7449926 | 95 | |
416331ca | 96 | use crate::Rng; |
dfeec247 | 97 | use core::iter; |
b7449926 | 98 | |
dfeec247 XL |
99 | pub use self::bernoulli::{Bernoulli, BernoulliError}; |
100 | pub use self::float::{Open01, OpenClosed01}; | |
0731742a | 101 | pub use self::other::Alphanumeric; |
b7449926 | 102 | #[doc(inline)] pub use self::uniform::Uniform; |
dfeec247 XL |
103 | #[cfg(feature = "alloc")] |
104 | pub use self::weighted::{WeightedError, WeightedIndex}; | |
416331ca XL |
105 | |
106 | // The following are all deprecated after being moved to rand_distr | |
107 | #[allow(deprecated)] | |
dfeec247 XL |
108 | #[cfg(feature = "std")] |
109 | pub use self::binomial::Binomial; | |
416331ca | 110 | #[allow(deprecated)] |
dfeec247 XL |
111 | #[cfg(feature = "std")] |
112 | pub use self::cauchy::Cauchy; | |
416331ca | 113 | #[allow(deprecated)] |
dfeec247 XL |
114 | #[cfg(feature = "std")] |
115 | pub use self::dirichlet::Dirichlet; | |
416331ca | 116 | #[allow(deprecated)] |
dfeec247 XL |
117 | #[cfg(feature = "std")] |
118 | pub use self::exponential::{Exp, Exp1}; | |
416331ca | 119 | #[allow(deprecated)] |
dfeec247 XL |
120 | #[cfg(feature = "std")] |
121 | pub use self::gamma::{Beta, ChiSquared, FisherF, Gamma, StudentT}; | |
416331ca | 122 | #[allow(deprecated)] |
dfeec247 XL |
123 | #[cfg(feature = "std")] |
124 | pub use self::normal::{LogNormal, Normal, StandardNormal}; | |
416331ca | 125 | #[allow(deprecated)] |
dfeec247 XL |
126 | #[cfg(feature = "std")] |
127 | pub use self::pareto::Pareto; | |
416331ca | 128 | #[allow(deprecated)] |
dfeec247 XL |
129 | #[cfg(feature = "std")] |
130 | pub use self::poisson::Poisson; | |
416331ca | 131 | #[allow(deprecated)] |
dfeec247 XL |
132 | #[cfg(feature = "std")] |
133 | pub use self::triangular::Triangular; | |
416331ca | 134 | #[allow(deprecated)] |
dfeec247 XL |
135 | #[cfg(feature = "std")] |
136 | pub use self::unit_circle::UnitCircle; | |
416331ca | 137 | #[allow(deprecated)] |
dfeec247 XL |
138 | #[cfg(feature = "std")] |
139 | pub use self::unit_sphere::UnitSphereSurface; | |
416331ca | 140 | #[allow(deprecated)] |
dfeec247 XL |
141 | #[cfg(feature = "std")] |
142 | pub use self::weibull::Weibull; | |
b7449926 | 143 | |
0731742a | 144 | mod bernoulli; |
dfeec247 XL |
145 | #[cfg(feature = "std")] mod binomial; |
146 | #[cfg(feature = "std")] mod cauchy; | |
147 | #[cfg(feature = "std")] mod dirichlet; | |
148 | #[cfg(feature = "std")] mod exponential; | |
149 | #[cfg(feature = "std")] mod gamma; | |
150 | #[cfg(feature = "std")] mod normal; | |
151 | #[cfg(feature = "std")] mod pareto; | |
152 | #[cfg(feature = "std")] mod poisson; | |
153 | #[cfg(feature = "std")] mod triangular; | |
154 | pub mod uniform; | |
155 | #[cfg(feature = "std")] mod unit_circle; | |
156 | #[cfg(feature = "std")] mod unit_sphere; | |
157 | #[cfg(feature = "std")] mod weibull; | |
158 | #[cfg(feature = "alloc")] pub mod weighted; | |
b7449926 XL |
159 | |
160 | mod float; | |
dfeec247 XL |
161 | #[doc(hidden)] |
162 | pub mod hidden_export { | |
163 | pub use super::float::IntoFloat; // used by rand_distr | |
416331ca | 164 | } |
b7449926 | 165 | mod integer; |
b7449926 | 166 | mod other; |
0731742a | 167 | mod utils; |
dfeec247 | 168 | #[cfg(feature = "std")] mod ziggurat_tables; |
b7449926 XL |
169 | |
170 | /// Types (distributions) that can be used to create a random instance of `T`. | |
171 | /// | |
172 | /// It is possible to sample from a distribution through both the | |
173 | /// `Distribution` and [`Rng`] traits, via `distr.sample(&mut rng)` and | |
174 | /// `rng.sample(distr)`. They also both offer the [`sample_iter`] method, which | |
175 | /// produces an iterator that samples from the distribution. | |
176 | /// | |
177 | /// All implementations are expected to be immutable; this has the significant | |
178 | /// advantage of not needing to consider thread safety, and for most | |
179 | /// distributions efficient state-less sampling algorithms are available. | |
180 | /// | |
dfeec247 XL |
181 | /// Implementations are typically expected to be portable with reproducible |
182 | /// results when used with a PRNG with fixed seed; see the | |
183 | /// [portability chapter](https://rust-random.github.io/book/portability.html) | |
184 | /// of The Rust Rand Book. In some cases this does not apply, e.g. the `usize` | |
185 | /// type requires different sampling on 32-bit and 64-bit machines. | |
186 | /// | |
416331ca | 187 | /// [`sample_iter`]: Distribution::method.sample_iter |
b7449926 XL |
188 | pub trait Distribution<T> { |
189 | /// Generate a random value of `T`, using `rng` as the source of randomness. | |
190 | fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T; | |
191 | ||
192 | /// Create an iterator that generates random values of `T`, using `rng` as | |
193 | /// the source of randomness. | |
194 | /// | |
416331ca XL |
195 | /// Note that this function takes `self` by value. This works since |
196 | /// `Distribution<T>` is impl'd for `&D` where `D: Distribution<T>`, | |
197 | /// however borrowing is not automatic hence `distr.sample_iter(...)` may | |
198 | /// need to be replaced with `(&distr).sample_iter(...)` to borrow or | |
199 | /// `(&*distr).sample_iter(...)` to reborrow an existing reference. | |
200 | /// | |
b7449926 XL |
201 | /// # Example |
202 | /// | |
203 | /// ``` | |
204 | /// use rand::thread_rng; | |
205 | /// use rand::distributions::{Distribution, Alphanumeric, Uniform, Standard}; | |
206 | /// | |
416331ca | 207 | /// let rng = thread_rng(); |
b7449926 XL |
208 | /// |
209 | /// // Vec of 16 x f32: | |
416331ca | 210 | /// let v: Vec<f32> = Standard.sample_iter(rng).take(16).collect(); |
b7449926 XL |
211 | /// |
212 | /// // String: | |
416331ca | 213 | /// let s: String = Alphanumeric.sample_iter(rng).take(7).collect(); |
b7449926 XL |
214 | /// |
215 | /// // Dice-rolling: | |
216 | /// let die_range = Uniform::new_inclusive(1, 6); | |
416331ca | 217 | /// let mut roll_die = die_range.sample_iter(rng); |
b7449926 XL |
218 | /// while roll_die.next().unwrap() != 6 { |
219 | /// println!("Not a 6; rolling again!"); | |
220 | /// } | |
221 | /// ``` | |
416331ca | 222 | fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T> |
dfeec247 XL |
223 | where |
224 | R: Rng, | |
225 | Self: Sized, | |
b7449926 XL |
226 | { |
227 | DistIter { | |
228 | distr: self, | |
dfeec247 | 229 | rng, |
b7449926 XL |
230 | phantom: ::core::marker::PhantomData, |
231 | } | |
232 | } | |
233 | } | |
234 | ||
235 | impl<'a, T, D: Distribution<T>> Distribution<T> for &'a D { | |
236 | fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T { | |
237 | (*self).sample(rng) | |
238 | } | |
239 | } | |
240 | ||
241 | ||
242 | /// An iterator that generates random values of `T` with distribution `D`, | |
243 | /// using `R` as the source of randomness. | |
244 | /// | |
245 | /// This `struct` is created by the [`sample_iter`] method on [`Distribution`]. | |
246 | /// See its documentation for more. | |
247 | /// | |
416331ca | 248 | /// [`sample_iter`]: Distribution::sample_iter |
b7449926 | 249 | #[derive(Debug)] |
416331ca XL |
250 | pub struct DistIter<D, R, T> { |
251 | distr: D, | |
252 | rng: R, | |
b7449926 XL |
253 | phantom: ::core::marker::PhantomData<T>, |
254 | } | |
255 | ||
416331ca | 256 | impl<D, R, T> Iterator for DistIter<D, R, T> |
dfeec247 XL |
257 | where |
258 | D: Distribution<T>, | |
259 | R: Rng, | |
b7449926 XL |
260 | { |
261 | type Item = T; | |
262 | ||
263 | #[inline(always)] | |
264 | fn next(&mut self) -> Option<T> { | |
416331ca XL |
265 | // Here, self.rng may be a reference, but we must take &mut anyway. |
266 | // Even if sample could take an R: Rng by value, we would need to do this | |
267 | // since Rng is not copyable and we cannot enforce that this is "reborrowable". | |
268 | Some(self.distr.sample(&mut self.rng)) | |
b7449926 XL |
269 | } |
270 | ||
271 | fn size_hint(&self) -> (usize, Option<usize>) { | |
272 | (usize::max_value(), None) | |
273 | } | |
274 | } | |
275 | ||
416331ca | 276 | impl<D, R, T> iter::FusedIterator for DistIter<D, R, T> |
dfeec247 XL |
277 | where |
278 | D: Distribution<T>, | |
279 | R: Rng, | |
280 | { | |
281 | } | |
0731742a XL |
282 | |
283 | #[cfg(features = "nightly")] | |
416331ca | 284 | impl<D, R, T> iter::TrustedLen for DistIter<D, R, T> |
dfeec247 XL |
285 | where |
286 | D: Distribution<T>, | |
287 | R: Rng, | |
288 | { | |
289 | } | |
0731742a | 290 | |
b7449926 XL |
291 | |
292 | /// A generic random value distribution, implemented for many primitive types. | |
293 | /// Usually generates values with a numerically uniform distribution, and with a | |
294 | /// range appropriate to the type. | |
416331ca XL |
295 | /// |
296 | /// ## Provided implementations | |
b7449926 XL |
297 | /// |
298 | /// Assuming the provided `Rng` is well-behaved, these implementations | |
299 | /// generate values with the following ranges and distributions: | |
300 | /// | |
301 | /// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed | |
302 | /// over all values of the type. | |
303 | /// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all | |
304 | /// code points in the range `0...0x10_FFFF`, except for the range | |
305 | /// `0xD800...0xDFFF` (the surrogate code points). This includes | |
306 | /// unassigned/reserved code points. | |
307 | /// * `bool`: Generates `false` or `true`, each with probability 0.5. | |
308 | /// * Floating point types (`f32` and `f64`): Uniformly distributed in the | |
309 | /// half-open range `[0, 1)`. See notes below. | |
310 | /// * Wrapping integers (`Wrapping<T>`), besides the type identical to their | |
311 | /// normal integer variants. | |
312 | /// | |
416331ca XL |
313 | /// The `Standard` distribution also supports generation of the following |
314 | /// compound types where all component types are supported: | |
315 | /// | |
316 | /// * Tuples (up to 12 elements): each element is generated sequentially. | |
317 | /// * Arrays (up to 32 elements): each element is generated sequentially; | |
318 | /// see also [`Rng::fill`] which supports arbitrary array length for integer | |
319 | /// types and tends to be faster for `u32` and smaller types. | |
320 | /// * `Option<T>` first generates a `bool`, and if true generates and returns | |
321 | /// `Some(value)` where `value: T`, otherwise returning `None`. | |
322 | /// | |
323 | /// ## Custom implementations | |
324 | /// | |
325 | /// The [`Standard`] distribution may be implemented for user types as follows: | |
326 | /// | |
327 | /// ``` | |
328 | /// # #![allow(dead_code)] | |
329 | /// use rand::Rng; | |
330 | /// use rand::distributions::{Distribution, Standard}; | |
b7449926 | 331 | /// |
416331ca XL |
332 | /// struct MyF32 { |
333 | /// x: f32, | |
334 | /// } | |
b7449926 | 335 | /// |
416331ca XL |
336 | /// impl Distribution<MyF32> for Standard { |
337 | /// fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> MyF32 { | |
338 | /// MyF32 { x: rng.gen() } | |
339 | /// } | |
340 | /// } | |
341 | /// ``` | |
342 | /// | |
343 | /// ## Example usage | |
b7449926 XL |
344 | /// ``` |
345 | /// use rand::prelude::*; | |
346 | /// use rand::distributions::Standard; | |
347 | /// | |
416331ca | 348 | /// let val: f32 = StdRng::from_entropy().sample(Standard); |
b7449926 XL |
349 | /// println!("f32 from [0, 1): {}", val); |
350 | /// ``` | |
351 | /// | |
352 | /// # Floating point implementation | |
353 | /// The floating point implementations for `Standard` generate a random value in | |
354 | /// the half-open interval `[0, 1)`, i.e. including 0 but not 1. | |
355 | /// | |
356 | /// All values that can be generated are of the form `n * ε/2`. For `f32` | |
dfeec247 | 357 | /// the 24 most significant random bits of a `u32` are used and for `f64` the |
b7449926 XL |
358 | /// 53 most significant bits of a `u64` are used. The conversion uses the |
359 | /// multiplicative method: `(rng.gen::<$uty>() >> N) as $ty * (ε/2)`. | |
360 | /// | |
361 | /// See also: [`Open01`] which samples from `(0, 1)`, [`OpenClosed01`] which | |
362 | /// samples from `(0, 1]` and `Rng::gen_range(0, 1)` which also samples from | |
363 | /// `[0, 1)`. Note that `Open01` and `gen_range` (which uses [`Uniform`]) use | |
364 | /// transmute-based methods which yield 1 bit less precision but may perform | |
365 | /// faster on some architectures (on modern Intel CPUs all methods have | |
366 | /// approximately equal performance). | |
367 | /// | |
416331ca | 368 | /// [`Uniform`]: uniform::Uniform |
b7449926 XL |
369 | #[derive(Clone, Copy, Debug)] |
370 | pub struct Standard; | |
371 | ||
b7449926 | 372 | |
416331ca | 373 | #[cfg(all(test, feature = "std"))] |
b7449926 | 374 | mod tests { |
416331ca | 375 | use super::{Distribution, Uniform}; |
dfeec247 | 376 | use crate::Rng; |
b7449926 | 377 | |
b7449926 XL |
378 | #[test] |
379 | fn test_distributions_iter() { | |
416331ca XL |
380 | use crate::distributions::Open01; |
381 | let mut rng = crate::test::rng(210); | |
382 | let distr = Open01; | |
383 | let results: Vec<f32> = distr.sample_iter(&mut rng).take(100).collect(); | |
b7449926 XL |
384 | println!("{:?}", results); |
385 | } | |
dfeec247 | 386 | |
416331ca XL |
387 | #[test] |
388 | fn test_make_an_iter() { | |
dfeec247 XL |
389 | fn ten_dice_rolls_other_than_five<'a, R: Rng>( |
390 | rng: &'a mut R, | |
391 | ) -> impl Iterator<Item = i32> + 'a { | |
416331ca XL |
392 | Uniform::new_inclusive(1, 6) |
393 | .sample_iter(rng) | |
394 | .filter(|x| *x != 5) | |
395 | .take(10) | |
396 | } | |
dfeec247 | 397 | |
416331ca XL |
398 | let mut rng = crate::test::rng(211); |
399 | let mut count = 0; | |
400 | for val in ten_dice_rolls_other_than_five(&mut rng) { | |
401 | assert!(val >= 1 && val <= 6 && val != 5); | |
402 | count += 1; | |
403 | } | |
404 | assert_eq!(count, 10); | |
405 | } | |
b7449926 | 406 | } |