Function sample_single_l_reservoir

Source

pub fn sample_single_l_reservoir<'a, Container, R, T>(
    rng: &mut R,
    set: &'a Container,
) -> Option<T>where
    R: Rng,
    Container: HasIter<Item<'a> = &'a T>,
    T: Clone + 'static,

Expand description

Sample a random element uniformly from a container of unknown length.

We do not assume the container is randomly indexable, only that it can be iterated over. The value is cloned.

This function implements “Algorithm L” from KIM-HUNG LI Reservoir-Sampling Algorithms of Time Complexity O(n(1 + log(N/n))) https://dl.acm.org/doi/pdf/10.1145/198429.198435

This algorithm is significantly slower than the “known length” algorithm (factor of 10^4). The reservoir algorithm from rand reduces to the “known lengthalgorithm when the iterator is anExactSizeIterator, or more precisely, when iterator.size_hint()returns(k, Some(k))for somek. Otherwise, this algorithm is much faster than the rand` implementation (factor of 100).

Function sample_single_l_reservoirCopy item path

Function sample_single_l_reservoir