More efficient random selection for iterators of unknown length?

[CarlKCarlK]

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.

[CarlKCarlK]

There may also be an opportunity to support weighted streaming selection.

Issue #1365 already proposes weighted reservoir sampling for arbitrary iterators. For the special case k == 1, the weighted skip algorithm is especially simple: the next replacement can be determined from a cumulative-weight threshold using one random variate per replacement.

See:
#1365
https://arxiv.org/html/2403.20256v7

[dhardy]

Shame on the interviewer for calling deterministic code with fixed inputs random just because it uses a PRNG — it's no more random than https://xkcd.com/221/ , and without being able to change the seed any statistical test of randomness would tell you the same thing.

Overall this seems a nice approach (though the proofs in the paper aren't the easiest to follow).

It seems obvious that when the length of the iterator is known, directly sampling random_range(0..len) is the best approach and when the length is completely unknown (no hinting and without the expectation that it will be very short) that your (Meek-Kadie) approach is at least close to the optimum. When partial hinting is available or the expected length is very short the best approach is less obvious, but the Meek-Kadie algorithm is likely reasonable. (But a note on the example in your interview: the cost of the random sampling in lines.choose(&mut rng) is likely irrelevant compared to the file access and line scanning.)

On the topic of reproducibility, any change to choose is considered a breaking change. Further, choose_stable exists largely because size_hint may affect the result of choose. Potentially it would make sense to use Meek-Kadie in choose_stable and have choose use choose_stable when the length is not precisely known, though there are likely users who wouldn't appreciate the breaking change.

[CarlKCarlK]

Attribution correction: Adriano Meligrana pointed me to Park et al. (SDM 2004), which already derives the general skip distribution and inverse-CDF sampler. Its m = 1 specialization is exactly the single-item method Chris Meek and I derived in 2022.

I've updated the issue body to cite Park et al. as the earlier source.

[CarlKCarlK]

@dhardy writes:

On the topic of reproducibility, any change to choose is considered a breaking change.

Thanks — the reproducibility concern makes sense.

Given that, would it make sense to keep choose unchanged in 0.10.x, add an opt-in skip-based method such as choose_skip, and then consider using the skip implementation for choose in 0.11?

Aside: I tried to think of the most extreme realistic case where this could matter: sampling from a depth-first traversal of a large in-memory tree whose nodes do not store subtree sizes, combined with an expensive RNG such as a cryptographic or hardware random source. The traversal itself is cheap, the total length is unknown, and reducing random-number work from linear to logarithmic could matter substantially. Of course, my real motivation is that I love optimal solutions.