More efficient random selection for iterators of unknown length?

Background

What is your motivation?

IteratorRandom::choose currently falls back to considering each element when size_hint() gives little useful information. There is a skip-based method for choosing one item uniformly from a stream of unknown length that generates only the positions where the current selection changes, avoiding a random decision for every element.

For choosing multiple items, Vitter’s reservoir-sampling algorithms use the same general idea: skip elements that cannot enter the reservoir instead of drawing for every element.

What type of application is this?

General-purpose iterator sampling. This is most useful for long or streaming iterators with unknown length and weak size_hint() information.

Feature request

Would you be interested in a PR exploring these skip-based algorithms for IteratorRandom::choose and possibly sample?

Current implementation:
https://github.com/rust-random/rand/blob/master/src/seq/iterator.rs

Single-item skip method / prior work:
Park, Ostrouchov, Samatova & Geist, Reservoir-based Random Sampling with Replacement from Data Stream (2004)

Meek & Kadie independently derived and presented the m = 1 special case in 2022:
https://cm1x.github.io/static/Attenuated_Geometric_Distribution.pdf
https://medium.com/data-science/interview-question-select-a-random-line-from-a-file-in-rust-c0a8cddcddfb

Vitter, Random Sampling with a Reservoir:
https://www.cs.umd.edu/~samir/498/vitter.pdf

Random-number efficiency

For a stream of 10 million items with unknown length and k = 1:

• The current rand::IteratorRandom::choose fallback does O(n) random selection work: about 10,000,000 random decisions.
• A general Vitter-style skip algorithm reduces this to O(log n) random variates for k = 1: roughly 30–35 random variates for 10 million items.
• The single-item algorithm is also O(log n), but is specialized for k = 1 and needs only about 17 random variates for 10 million items.

The expected number of times the selected item actually changes is

ln(10,000,000) + γ ≈ 16.7.

The single-item skip algorithm samples those replacement positions directly instead of making a random decision for every input item.

Start in src/seq/iterator.rs at IteratorRandom::choose and its size_hint fallback. Read the linked skip-based and Vitter reservoir-sampling papers, then determine whether the approach applies to choose, sample, or both. Done means a scoped algorithm decision with uniform sampling and random-number efficiency evaluated.