Stable version of rand::seq::IteratorRandom::choose

[kevincox]

Background

What is your motivation?

Provide a way to produce predictable results for (a function similar to) rand::seq::IteratorRandom::choose no matter what type of iterator it is.

Right now the behaviour of rand::seq::IteratorRandom::choose depends on the type of Iterator that is passed in. This is mentioned in the docs as an "optimization" however it isn't clear that this is a behaviour affecting "optimization". Furthermore there is no good alternative function which doesn't have this "optimization".

Example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a62f77f38f4a0b66df57106d0cf6a4a4

extern crate rand; // 0.7.3
extern crate rand_pcg; // 0.2.1

fn choose(i: &mut dyn Iterator<Item=u32>) -> u32 {
    let mut rng = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
    rand::seq::IteratorRandom::choose(i, &mut rng).unwrap()
}

fn main() {
    dbg!(choose(&mut (0..32))); // 5
    dbg!(choose(&mut (0..32).filter(|_| true))); // 3
}

What type of application is this? numerical simulation

Feature request

1. Clarify the documentation to emphasize that rand::seq::IteratorRandom::choose has different behaviour depending on the return value of the size_hint method.
2. Provide an alternative function that will select the same element (including Rng state) for any iterator of the same length.

Workarounds

Unify type:

One option to get a consistent result is ensure that you are always working with the same type. For example the following always collects to a Vec.

fn stable_choose_collect<T>(i: impl Iterator<Item=T>, mut rng: impl rand::Rng) -> Option<T> {
    rand::seq::IteratorRandom::choose(i.collect::<Vec<_>>().into_iter(), &mut rng)
}

Get rid of size_hint.

It would be more "proper" to make a wrapper type but since rand::seq::IteratorRandom::choose only performs its "optimization" if lower == upper we just need to make those not equal. The easiest way to do this is is call .filter(|_| true) on the iterator. Because it can't tell how many elements you will filter it will set the lower bound to 0.

fn stable_choose_no_hint<T>(i: impl Iterator<Item=T>, mut rng: impl rand::Rng) -> Option<T> {
    rand::seq::IteratorRandom::choose(i.filter(|_| true), &mut rng)
}

[dhardy]

Making use of size hints enables much faster sampling for large iterators. Might I suggest that if you want more predictable behaviour you use SliceRandom::choose?

Perhaps we should explicitly document that size_hint affects sampling behaviour and not just performance. Sorry, I thought this would be obvious.

[kevincox]

I understand that it provides much faster sampling and it does make sense to have this option available. However it should be explicitly called out in the documentation and there should be an option provided that doesn't have this optimization. I think that using a PRNG is a common use case, especially for tests and people may be surprised when they are getting different results for a change that looks like it should be a no-op.

Might I suggest that if you want more predictable behaviour you use SliceRandom::choose?

This is often a good option however in some cases materializing the whole iterator is not desired.

[vks]

I think documenting the behavior is the best way forward (see #1052 for my attempt). I don't really see a strong motivation for providing a stable alternative implementation. As far as I can see, the only use case with somewhat surprising behavior are noop iterator combinators, which seems like an extreme edge case.

[kevincox]

I don't see how this is an extreme edge case. This affects any function that tries to use this function on an interator from an unknown source. Whether or not the difference matters depends on the application.

[vks]

I still can't think of an application, but I guess we could add IteratorRandom::choose_stable. @dhardy What do you think?

[kevincox]

In my example I have composible filters and rankers. Most of them fall back to a random selector if they can't narrow it down to one choice. However it is surprising when you have a filter that shouldn't have an effect do something. For example:

• Adding a filter that logically shouldn't change anything due to known state or being less selective than previous filters.
• A debugging filter that collects the iterator in order to make more intelligent printing decisions, then forwards the Vec.into_iter().

It also means that seemingly noop changes such as refactoring to avoid collecting the iterator will change the result which makes it harder to validate that the change is correct.

[kevincox]

If this method would be accepted I can write it.

[dhardy]

Yes, I guess we can accept choose_stable.

[dhardy]

That PR only updated documentation so not done yet.

[kevincox]

Thanks, I'll hopefully have time to make a PR soon.