Add choose_multiple_fill for SliceRandom

[mendess]

Background

Currently IteratorRandom provides an allocation free way to sample members from it with choose_multiple_fill, problem is it's O(n) over the size of the iterator. This makes sense but then the docs point to SliceRandom::choose_multiple which is O(amount) but it always allocates a new vec of indexes to back the iterator it returns.

I need to sample exactly 2 members of a slice in a loop, it would be nice to have a way to avoid allocating in a loop that doesn't need to as this will be a major performance hit.

Right now I have to do

let (u, w) = slice
    .choose(&mut rng)
    .and_then(|u| loop {
        let w = slice.choose(&mut rng)?;
        if w != u {
            break Some((u, w));
        }
    })?;

which I doubt is a good way to achieve randomness.

Feature request

Add to SliceRandom

fn choose_multiple_fill(
    &self,
    rng: &mut Rng,
    slice: &mut [Self::Item]
) -> usize

I can try to write a PR for this if it seems feasible but I don't have experience with rng, I would look at the rest of the implementations, specially SliceRandom::choose_multiple for inspiration.

[dhardy]

which I doubt is a good way to achieve randomness

Rejection sampling is a very good approach in this case (amount = 2). For more general algorithms, take a look at src/seq/index.rs. There is at least one other algorithm that ended up being coded but not included here.

All these have something in common: they need some buffer to store selected indices in. We can't directly use the output buffer, since we need to avoid sampling any index multiple times but multiple copies of an output value may be valid (if appearing in your slice multiple times). So the best we could do without allocating is:

pub fn sample_buf<R>(rng: &mut R, length: usize, buf: &mut [usize])
where R: Rng + ?Sized { ... }

Unfortunately, we'd have to duplicate all the methods in index.rs, which isn't really desirable (though it isn't that much code).

Note further: IndexVec specifically supports output to Vec<u32> as well as the more general Vec<usize>, since for most cases u32 is large enough and the extra memory-usage of usize (on 64-bit platforms) has real performance impacts. You can't do the same with the method above, so it could be slower despite avoiding allocation — although for large amount you probably need to allocate anyway.

[dhardy]

This ("sample exactly 2 members of a slice") was implemented in #1453.