rand::sample's API should be fallible

[vitiral]

Most rust operations are fallible if they don't make sense, either through a panic or by returning an Option or Result. However, rand::sample has the following API:

pub fn sample<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Vec<T> where
    I: IntoIterator<Item = T>,
    R: Rng, 

Randomly sample up to amount elements from a finite iterator.

This function will silently return less than amount if the size of I is less than amount. I would say this is very odd, and returning Option<Vec<T>> would have been a better design choice. You can imagine the confusion if you did rand::sample(rng, v, 100) but then only had 2 elements!

If it were changed to returning None if I.len() < amount then the current behavior could still be accomplished with:

rand::sample(&mut rng, vec.iter(), usize::min(amount, vec.len())).unwrap()

With the current behavior, user has to put guards around their code (which is not required by the compiler) to prevent getting less than amount, which is unusual in rust.

Another argument is that trying to sample when amount > len() will just return an "inadequately shuffled" version of the iterator. If someone wanted that behavior it would be more correct to just collect() the iterator and call shuffle() on it.

[dhardy]

Do you have a context where you're using this function? I'm not sure what the main use-cases are which makes it hard to say what it should do.

[vitiral]

The major point is how this behaves compared to functions like slice or even Vec::get which do not permit you to attempt to access slices that are outside of the range.

#[test]
fn it_works() {
    let v = vec![1,2,3,4];
    assert_eq!(&v[2..6], &[3,4]);
}

panics with:

        thread 'it_works' panicked at 'index 6 out of range for slice of length 4', /checkout/src/libcore/slice/mod.rs:745:4

The way this currently behaves is more like python's slice mechanics, where doing list[5:100] will raise an error only if the min-index does not exist, but doesn't care if it returns less than 95 elements.

The counterpoint is something like Iterator::take, but that actually returns an iterator, so you still get None values when it runs out.

Edit: I consider sample to be akin to a "random slice of values" -- obviously not in order, etc but in that vein. Therefore it should always return exactly amount values.

[vitiral]

Also, I a requesting this change as part of the rand crate stabilization: rust-lang/rfcs#2106

[dhardy]

Is it? I don't remember writing that. Do you mean it was requested in a comment?

Regarding the previous post: true. But another point related to sample is that the algorithm could be more efficient if the input is given as a slice (or something allowing random access), roughly when input.len() > 2 * amount, as well as providing true sorting.

So without use cases I still don't know what this function should do (I'd be tempted just not to stabilise it, e.g. put it behind a feature gate).

[vitiral]

sorry, I meant that I am requesting it as part of that effort :)

[vitiral]

I might be wrong, but I think rust allows you to overload to provide different implementations for different input types, so such efficiency could be provided.

Also, correct me if I'm wrong but the function already requires an iterator of a known length right?

... Hmm, I'm looking at it and I think it just requires the input to be an iterator, so it doesn't necessarily know anything about the length. I think there are really two use cases here that should mabe be two separate functions. At the very least, one that knows about the length and one that doesn't.

[dhardy]

Iterators never have a known length in Rust. At best, they have a size-hint, but that's too unreliable for this use-case.

You're right, two different functions are called for to cover this functionality fully. But I wonder which one(s) would actually be used?

[bluss]

I think the current interface of sample kind of makes sense and is self-consistent, but it's a very tricky to use function. This is reservoir sampling, and the function includes a note that the order of elements in the output is not random!

The interface is that you input a sequence of n elements and then you pick at most m of those elements, where each element has equal chance of ending up in the output. This generalizes quite nicely into supporting situations where n <= m; you simply get the whole sequence back.

[vitiral]

So I can see three major use cases and am starting to think that these should be implemented as traits

This one is the same as what exists and would be implemented just for any iterator

trait SampleIter<T: Clone>: IntoIter<Item=T> {
    /// Randomly sample up to amount elements from a finite iterator.
    /// The order of elements in the sample is not random.
    ///
    /// This consumes the entire iterator.
    pub fn sample<R: Rng>(&mut self, rng: &mut R, amount: usize) -> Vec<T> 
}

This is similar, but is for slices.

Edit: I've split it into two methods so that sample has identical behavior to its iterator friend.

trait SampleSlice<T> {
    /// Randomly sample up to amount elements from a a slice.
    ///
    /// This takes at most `O(amount)` time.
    ///
    /// returns a clone of `self` if `amount <= self.len()`
    pub fn sample<R: Rng>(&self, rng: &mut R, amount: usize) -> Vec<T> 

    /// Randomly sample up to amount elements from a a slice.
    ///
    /// This takes at most `O(amount)` time.
    ///
    /// Panics if self.len() < amount.
    pub fn sample_exact<R: Rng>(&self, rng: &mut R, amount: usize) -> Vec<T> 
}

Another implementation could hopefully be done on HashSet, HashMap, BTreeMap, etc -- I'm not sure if there is a way to reduce those to O(amount) work, but if there were it would be very nice!

The point here is that each is implementation specific and I can see use cases for all of them:

• Randomly select 20 lines from a file (or really any long stream): use SampleIter trait, it will not take up any extra memory!
• Randomly select 20 items from a Vec/Slice: use SampleSlice trait, it will only take `O(amount) time!
• Randomly select 20 possiblilities from a HashSet/Map: use SampleHash and (hopefully) get speedup over SampleIter, hopefully on-par with SampleSlice. Having these even be deterministic with the same seed + items would be very nice!

[vitiral]

@bluss I actually didn't realize that if n <= m it will actually be the elements in the order they were consumed. That is quite an interesting property that I think a SampleIter would want to preserve (and document).

[vitiral]

I edited SampleSlice slightly to add to methods to the trait.