pub fn sample_single_l_reservoir<I, R, T>(rng: &mut R, iterable: I) -> Option<T>where
R: Rng,
I: IntoIterator<Item = T>,Expand description
Sample a random element uniformly from an iterator of unknown length.
We do not assume the container is randomly indexable, only that it can be iterated over.
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 iterator.size_hint() returns (k, Some(k)) for some k. Otherwise,
this algorithm is much faster than the rand implementation (factor of 100).