// Copyright 2018 Developers of the Rand project. // Copyright 2013-2017 The Rust Project Developers. // // Licensed under the Apache License, Version 2.0 or the MIT license // , at your // option. This file may not be copied, modified, or distributed // except according to those terms. //! Generating random samples from probability distributions. //! //! This module is the home of the [`Distribution`] trait and several of its //! implementations. It is the workhorse behind some of the convenient //! functionality of the [`Rng`] trait, including [`gen`], [`gen_range`] and //! of course [`sample`]. //! //! Abstractly, a [probability distribution] describes the probability of //! occurance of each value in its sample space. //! //! More concretely, an implementation of `Distribution` for type `X` is an //! algorithm for choosing values from the sample space (a subset of `T`) //! according to the distribution `X` represents, using an external source of //! randomness (an RNG supplied to the `sample` function). //! //! A type `X` may implement `Distribution` for multiple types `T`. //! Any type implementing [`Distribution`] is stateless (i.e. immutable), //! but it may have internal parameters set at construction time (for example, //! [`Uniform`] allows specification of its sample space as a range within `T`). //! //! //! # The `Standard` distribution //! //! The [`Standard`] distribution is important to mention. This is the //! distribution used by [`Rng::gen()`] and represents the "default" way to //! produce a random value for many different types, including most primitive //! types, tuples, arrays, and a few derived types. See the documentation of //! [`Standard`] for more details. //! //! Implementing `Distribution` for [`Standard`] for user types `T` makes it //! possible to generate type `T` with [`Rng::gen()`], and by extension also //! with the [`random()`] function. //! //! //! # Distribution to sample from a `Uniform` range //! //! The [`Uniform`] distribution is more flexible than [`Standard`], but also //! more specialised: it supports fewer target types, but allows the sample //! space to be specified as an arbitrary range within its target type `T`. //! Both [`Standard`] and [`Uniform`] are in some sense uniform distributions. //! //! Values may be sampled from this distribution using [`Rng::gen_range`] or //! by creating a distribution object with [`Uniform::new`], //! [`Uniform::new_inclusive`] or `From`. When the range limits are not //! known at compile time it is typically faster to reuse an existing //! distribution object than to call [`Rng::gen_range`]. //! //! User types `T` may also implement `Distribution` for [`Uniform`], //! although this is less straightforward than for [`Standard`] (see the //! documentation in the [`uniform` module]. Doing so enables generation of //! values of type `T` with [`Rng::gen_range`]. //! //! //! # Other distributions //! //! There are surprisingly many ways to uniformly generate random floats. A //! range between 0 and 1 is standard, but the exact bounds (open vs closed) //! and accuracy differ. In addition to the [`Standard`] distribution Rand offers //! [`Open01`] and [`OpenClosed01`]. See [Floating point implementation] for //! more details. //! //! [`Alphanumeric`] is a simple distribution to sample random letters and //! numbers of the `char` type; in contrast [`Standard`] may sample any valid //! `char`. //! //! [`WeightedIndex`] can be used to do weighted sampling from a set of items, //! such as from an array. //! //! # Non-uniform probability distributions //! //! Rand currently provides the following probability distributions: //! //! - Related to real-valued quantities that grow linearly //! (e.g. errors, offsets): //! - [`Normal`] distribution, and [`StandardNormal`] as a primitive //! - [`Cauchy`] distribution //! - Related to Bernoulli trials (yes/no events, with a given probability): //! - [`Binomial`] distribution //! - [`Bernoulli`] distribution, similar to [`Rng::gen_bool`]. //! - Related to positive real-valued quantities that grow exponentially //! (e.g. prices, incomes, populations): //! - [`LogNormal`] distribution //! - Related to the occurrence of independent events at a given rate: //! - [`Pareto`] distribution //! - [`Poisson`] distribution //! - [`Exp`]onential distribution, and [`Exp1`] as a primitive //! - [`Weibull`] distribution //! - Gamma and derived distributions: //! - [`Gamma`] distribution //! - [`ChiSquared`] distribution //! - [`StudentT`] distribution //! - [`FisherF`] distribution //! - Triangular distribution: //! - [`Beta`] distribution //! - [`Triangular`] distribution //! - Multivariate probability distributions //! - [`Dirichlet`] distribution //! - [`UnitSphereSurface`] distribution //! - [`UnitCircle`] distribution //! //! # Examples //! //! Sampling from a distribution: //! //! ``` //! use rand::{thread_rng, Rng}; //! use rand::distributions::Exp; //! //! let exp = Exp::new(2.0); //! let v = thread_rng().sample(exp); //! println!("{} is from an Exp(2) distribution", v); //! ``` //! //! Implementing the [`Standard`] distribution for a user type: //! //! ``` //! # #![allow(dead_code)] //! use rand::Rng; //! use rand::distributions::{Distribution, Standard}; //! //! struct MyF32 { //! x: f32, //! } //! //! impl Distribution for Standard { //! fn sample(&self, rng: &mut R) -> MyF32 { //! MyF32 { x: rng.gen() } //! } //! } //! ``` //! //! //! [probability distribution]: https://en.wikipedia.org/wiki/Probability_distribution //! [`Distribution`]: trait.Distribution.html //! [`gen_range`]: ../trait.Rng.html#method.gen_range //! [`gen`]: ../trait.Rng.html#method.gen //! [`sample`]: ../trait.Rng.html#method.sample //! [`new_inclusive`]: struct.Uniform.html#method.new_inclusive //! [`random()`]: ../fn.random.html //! [`Rng::gen_bool`]: ../trait.Rng.html#method.gen_bool //! [`Rng::gen_range`]: ../trait.Rng.html#method.gen_range //! [`Rng::gen()`]: ../trait.Rng.html#method.gen //! [`Rng`]: ../trait.Rng.html //! [`uniform` module]: uniform/index.html //! [Floating point implementation]: struct.Standard.html#floating-point-implementation // distributions //! [`Alphanumeric`]: struct.Alphanumeric.html //! [`Bernoulli`]: struct.Bernoulli.html //! [`Beta`]: struct.Beta.html //! [`Binomial`]: struct.Binomial.html //! [`Cauchy`]: struct.Cauchy.html //! [`ChiSquared`]: struct.ChiSquared.html //! [`Dirichlet`]: struct.Dirichlet.html //! [`Exp`]: struct.Exp.html //! [`Exp1`]: struct.Exp1.html //! [`FisherF`]: struct.FisherF.html //! [`Gamma`]: struct.Gamma.html //! [`LogNormal`]: struct.LogNormal.html //! [`Normal`]: struct.Normal.html //! [`Open01`]: struct.Open01.html //! [`OpenClosed01`]: struct.OpenClosed01.html //! [`Pareto`]: struct.Pareto.html //! [`Poisson`]: struct.Poisson.html //! [`Standard`]: struct.Standard.html //! [`StandardNormal`]: struct.StandardNormal.html //! [`StudentT`]: struct.StudentT.html //! [`Triangular`]: struct.Triangular.html //! [`Uniform`]: struct.Uniform.html //! [`Uniform::new`]: struct.Uniform.html#method.new //! [`Uniform::new_inclusive`]: struct.Uniform.html#method.new_inclusive //! [`UnitSphereSurface`]: struct.UnitSphereSurface.html //! [`UnitCircle`]: struct.UnitCircle.html //! [`Weibull`]: struct.Weibull.html //! [`WeightedIndex`]: struct.WeightedIndex.html #[cfg(any(rust_1_26, features="nightly"))] use core::iter; use Rng; pub use self::other::Alphanumeric; #[doc(inline)] pub use self::uniform::Uniform; pub use self::float::{OpenClosed01, Open01}; pub use self::bernoulli::Bernoulli; #[cfg(feature="alloc")] pub use self::weighted::{WeightedIndex, WeightedError}; #[cfg(feature="std")] pub use self::unit_sphere::UnitSphereSurface; #[cfg(feature="std")] pub use self::unit_circle::UnitCircle; #[cfg(feature="std")] pub use self::gamma::{Gamma, ChiSquared, FisherF, StudentT, Beta}; #[cfg(feature="std")] pub use self::normal::{Normal, LogNormal, StandardNormal}; #[cfg(feature="std")] pub use self::exponential::{Exp, Exp1}; #[cfg(feature="std")] pub use self::pareto::Pareto; #[cfg(feature="std")] pub use self::poisson::Poisson; #[cfg(feature="std")] pub use self::binomial::Binomial; #[cfg(feature="std")] pub use self::cauchy::Cauchy; #[cfg(feature="std")] pub use self::dirichlet::Dirichlet; #[cfg(feature="std")] pub use self::triangular::Triangular; #[cfg(feature="std")] pub use self::weibull::Weibull; pub mod uniform; mod bernoulli; #[cfg(feature="alloc")] mod weighted; #[cfg(feature="std")] mod unit_sphere; #[cfg(feature="std")] mod unit_circle; #[cfg(feature="std")] mod gamma; #[cfg(feature="std")] mod normal; #[cfg(feature="std")] mod exponential; #[cfg(feature="std")] mod pareto; #[cfg(feature="std")] mod poisson; #[cfg(feature="std")] mod binomial; #[cfg(feature="std")] mod cauchy; #[cfg(feature="std")] mod dirichlet; #[cfg(feature="std")] mod triangular; #[cfg(feature="std")] mod weibull; mod float; mod integer; mod other; mod utils; #[cfg(feature="std")] mod ziggurat_tables; /// Types (distributions) that can be used to create a random instance of `T`. /// /// It is possible to sample from a distribution through both the /// `Distribution` and [`Rng`] traits, via `distr.sample(&mut rng)` and /// `rng.sample(distr)`. They also both offer the [`sample_iter`] method, which /// produces an iterator that samples from the distribution. /// /// All implementations are expected to be immutable; this has the significant /// advantage of not needing to consider thread safety, and for most /// distributions efficient state-less sampling algorithms are available. /// /// [`Rng`]: ../trait.Rng.html /// [`sample_iter`]: trait.Distribution.html#method.sample_iter pub trait Distribution { /// Generate a random value of `T`, using `rng` as the source of randomness. fn sample(&self, rng: &mut R) -> T; /// Create an iterator that generates random values of `T`, using `rng` as /// the source of randomness. /// /// # Example /// /// ``` /// use rand::thread_rng; /// use rand::distributions::{Distribution, Alphanumeric, Uniform, Standard}; /// /// let mut rng = thread_rng(); /// /// // Vec of 16 x f32: /// let v: Vec = Standard.sample_iter(&mut rng).take(16).collect(); /// /// // String: /// let s: String = Alphanumeric.sample_iter(&mut rng).take(7).collect(); /// /// // Dice-rolling: /// let die_range = Uniform::new_inclusive(1, 6); /// let mut roll_die = die_range.sample_iter(&mut rng); /// while roll_die.next().unwrap() != 6 { /// println!("Not a 6; rolling again!"); /// } /// ``` fn sample_iter<'a, R>(&'a self, rng: &'a mut R) -> DistIter<'a, Self, R, T> where Self: Sized, R: Rng { DistIter { distr: self, rng: rng, phantom: ::core::marker::PhantomData, } } } impl<'a, T, D: Distribution> Distribution for &'a D { fn sample(&self, rng: &mut R) -> T { (*self).sample(rng) } } /// An iterator that generates random values of `T` with distribution `D`, /// using `R` as the source of randomness. /// /// This `struct` is created by the [`sample_iter`] method on [`Distribution`]. /// See its documentation for more. /// /// [`Distribution`]: trait.Distribution.html /// [`sample_iter`]: trait.Distribution.html#method.sample_iter #[derive(Debug)] pub struct DistIter<'a, D: 'a, R: 'a, T> { distr: &'a D, rng: &'a mut R, phantom: ::core::marker::PhantomData, } impl<'a, D, R, T> Iterator for DistIter<'a, D, R, T> where D: Distribution, R: Rng + 'a { type Item = T; #[inline(always)] fn next(&mut self) -> Option { Some(self.distr.sample(self.rng)) } fn size_hint(&self) -> (usize, Option) { (usize::max_value(), None) } } #[cfg(rust_1_26)] impl<'a, D, R, T> iter::FusedIterator for DistIter<'a, D, R, T> where D: Distribution, R: Rng + 'a {} #[cfg(features = "nightly")] impl<'a, D, R, T> iter::TrustedLen for DistIter<'a, D, R, T> where D: Distribution, R: Rng + 'a {} /// A generic random value distribution, implemented for many primitive types. /// Usually generates values with a numerically uniform distribution, and with a /// range appropriate to the type. /// /// ## Built-in Implementations /// /// Assuming the provided `Rng` is well-behaved, these implementations /// generate values with the following ranges and distributions: /// /// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed /// over all values of the type. /// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all /// code points in the range `0...0x10_FFFF`, except for the range /// `0xD800...0xDFFF` (the surrogate code points). This includes /// unassigned/reserved code points. /// * `bool`: Generates `false` or `true`, each with probability 0.5. /// * Floating point types (`f32` and `f64`): Uniformly distributed in the /// half-open range `[0, 1)`. See notes below. /// * Wrapping integers (`Wrapping`), besides the type identical to their /// normal integer variants. /// /// The following aggregate types also implement the distribution `Standard` as /// long as their component types implement it: /// /// * Tuples and arrays: Each element of the tuple or array is generated /// independently, using the `Standard` distribution recursively. /// * `Option` where `Standard` is implemented for `T`: Returns `None` with /// probability 0.5; otherwise generates a random `x: T` and returns `Some(x)`. /// /// # Example /// ``` /// use rand::prelude::*; /// use rand::distributions::Standard; /// /// let val: f32 = SmallRng::from_entropy().sample(Standard); /// println!("f32 from [0, 1): {}", val); /// ``` /// /// # Floating point implementation /// The floating point implementations for `Standard` generate a random value in /// the half-open interval `[0, 1)`, i.e. including 0 but not 1. /// /// All values that can be generated are of the form `n * ε/2`. For `f32` /// the 23 most significant random bits of a `u32` are used and for `f64` the /// 53 most significant bits of a `u64` are used. The conversion uses the /// multiplicative method: `(rng.gen::<$uty>() >> N) as $ty * (ε/2)`. /// /// See also: [`Open01`] which samples from `(0, 1)`, [`OpenClosed01`] which /// samples from `(0, 1]` and `Rng::gen_range(0, 1)` which also samples from /// `[0, 1)`. Note that `Open01` and `gen_range` (which uses [`Uniform`]) use /// transmute-based methods which yield 1 bit less precision but may perform /// faster on some architectures (on modern Intel CPUs all methods have /// approximately equal performance). /// /// [`Open01`]: struct.Open01.html /// [`OpenClosed01`]: struct.OpenClosed01.html /// [`Uniform`]: uniform/struct.Uniform.html #[derive(Clone, Copy, Debug)] pub struct Standard; /// A value with a particular weight for use with `WeightedChoice`. #[deprecated(since="0.6.0", note="use WeightedIndex instead")] #[allow(deprecated)] #[derive(Copy, Clone, Debug)] pub struct Weighted { /// The numerical weight of this item pub weight: u32, /// The actual item which is being weighted pub item: T, } /// A distribution that selects from a finite collection of weighted items. /// /// Deprecated: use [`WeightedIndex`] instead. /// /// [`WeightedIndex`]: struct.WeightedIndex.html #[deprecated(since="0.6.0", note="use WeightedIndex instead")] #[allow(deprecated)] #[derive(Debug)] pub struct WeightedChoice<'a, T:'a> { items: &'a mut [Weighted], weight_range: Uniform, } #[deprecated(since="0.6.0", note="use WeightedIndex instead")] #[allow(deprecated)] impl<'a, T: Clone> WeightedChoice<'a, T> { /// Create a new `WeightedChoice`. /// /// Panics if: /// /// - `items` is empty /// - the total weight is 0 /// - the total weight is larger than a `u32` can contain. pub fn new(items: &'a mut [Weighted]) -> WeightedChoice<'a, T> { // strictly speaking, this is subsumed by the total weight == 0 case assert!(!items.is_empty(), "WeightedChoice::new called with no items"); let mut running_total: u32 = 0; // we convert the list from individual weights to cumulative // weights so we can binary search. This *could* drop elements // with weight == 0 as an optimisation. for item in items.iter_mut() { running_total = match running_total.checked_add(item.weight) { Some(n) => n, None => panic!("WeightedChoice::new called with a total weight \ larger than a u32 can contain") }; item.weight = running_total; } assert!(running_total != 0, "WeightedChoice::new called with a total weight of 0"); WeightedChoice { items, // we're likely to be generating numbers in this range // relatively often, so might as well cache it weight_range: Uniform::new(0, running_total) } } } #[deprecated(since="0.6.0", note="use WeightedIndex instead")] #[allow(deprecated)] impl<'a, T: Clone> Distribution for WeightedChoice<'a, T> { fn sample(&self, rng: &mut R) -> T { // we want to find the first element that has cumulative // weight > sample_weight, which we do by binary since the // cumulative weights of self.items are sorted. // choose a weight in [0, total_weight) let sample_weight = self.weight_range.sample(rng); // short circuit when it's the first item if sample_weight < self.items[0].weight { return self.items[0].item.clone(); } let mut idx = 0; let mut modifier = self.items.len(); // now we know that every possibility has an element to the // left, so we can just search for the last element that has // cumulative weight <= sample_weight, then the next one will // be "it". (Note that this greatest element will never be the // last element of the vector, since sample_weight is chosen // in [0, total_weight) and the cumulative weight of the last // one is exactly the total weight.) while modifier > 1 { let i = idx + modifier / 2; if self.items[i].weight <= sample_weight { // we're small, so look to the right, but allow this // exact element still. idx = i; // we need the `/ 2` to round up otherwise we'll drop // the trailing elements when `modifier` is odd. modifier += 1; } else { // otherwise we're too big, so go left. (i.e. do // nothing) } modifier /= 2; } self.items[idx + 1].item.clone() } } #[cfg(test)] mod tests { use rngs::mock::StepRng; #[allow(deprecated)] use super::{WeightedChoice, Weighted, Distribution}; #[test] #[allow(deprecated)] fn test_weighted_choice() { // this makes assumptions about the internal implementation of // WeightedChoice. It may fail when the implementation in // `distributions::uniform::UniformInt` changes. macro_rules! t { ($items:expr, $expected:expr) => {{ let mut items = $items; let mut total_weight = 0; for item in &items { total_weight += item.weight; } let wc = WeightedChoice::new(&mut items); let expected = $expected; // Use extremely large steps between the random numbers, because // we test with small ranges and `UniformInt` is designed to prefer // the most significant bits. let mut rng = StepRng::new(0, !0 / (total_weight as u64)); for &val in expected.iter() { assert_eq!(wc.sample(&mut rng), val) } }} } t!([Weighted { weight: 1, item: 10}], [10]); // skip some t!([Weighted { weight: 0, item: 20}, Weighted { weight: 2, item: 21}, Weighted { weight: 0, item: 22}, Weighted { weight: 1, item: 23}], [21, 21, 23]); // different weights t!([Weighted { weight: 4, item: 30}, Weighted { weight: 3, item: 31}], [30, 31, 30, 31, 30, 31, 30]); // check that we're binary searching // correctly with some vectors of odd // length. t!([Weighted { weight: 1, item: 40}, Weighted { weight: 1, item: 41}, Weighted { weight: 1, item: 42}, Weighted { weight: 1, item: 43}, Weighted { weight: 1, item: 44}], [40, 41, 42, 43, 44]); t!([Weighted { weight: 1, item: 50}, Weighted { weight: 1, item: 51}, Weighted { weight: 1, item: 52}, Weighted { weight: 1, item: 53}, Weighted { weight: 1, item: 54}, Weighted { weight: 1, item: 55}, Weighted { weight: 1, item: 56}], [50, 54, 51, 55, 52, 56, 53]); } #[test] #[allow(deprecated)] fn test_weighted_clone_initialization() { let initial : Weighted = Weighted {weight: 1, item: 1}; let clone = initial.clone(); assert_eq!(initial.weight, clone.weight); assert_eq!(initial.item, clone.item); } #[test] #[should_panic] #[allow(deprecated)] fn test_weighted_clone_change_weight() { let initial : Weighted = Weighted {weight: 1, item: 1}; let mut clone = initial.clone(); clone.weight = 5; assert_eq!(initial.weight, clone.weight); } #[test] #[should_panic] #[allow(deprecated)] fn test_weighted_clone_change_item() { let initial : Weighted = Weighted {weight: 1, item: 1}; let mut clone = initial.clone(); clone.item = 5; assert_eq!(initial.item, clone.item); } #[test] #[should_panic] #[allow(deprecated)] fn test_weighted_choice_no_items() { WeightedChoice::::new(&mut []); } #[test] #[should_panic] #[allow(deprecated)] fn test_weighted_choice_zero_weight() { WeightedChoice::new(&mut [Weighted { weight: 0, item: 0}, Weighted { weight: 0, item: 1}]); } #[test] #[should_panic] #[allow(deprecated)] fn test_weighted_choice_weight_overflows() { let x = ::core::u32::MAX / 2; // x + x + 2 is the overflow WeightedChoice::new(&mut [Weighted { weight: x, item: 0 }, Weighted { weight: 1, item: 1 }, Weighted { weight: x, item: 2 }, Weighted { weight: 1, item: 3 }]); } #[cfg(feature="std")] #[test] fn test_distributions_iter() { use distributions::Normal; let mut rng = ::test::rng(210); let distr = Normal::new(10.0, 10.0); let results: Vec<_> = distr.sample_iter(&mut rng).take(100).collect(); println!("{:?}", results); } }