Function sample_single_l_reservoir 

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,

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 length” algorithm when the iterator is an ExactSizeIterator, or more precisely, when iterator.size_hint() returns (k, Some(k)) for some k. Otherwise, this algorithm is much faster than the rand implementation (factor of 100).