Trait to get a random element from a collection

Opened by Adolfo Ochagavía at 2014-12-09 07:59:54

Sometimes you need to get a random element from a collection. Currently, we have Rng::choose, which returns a random element of a &[T]. This allows us to pick a random element from a Vec, by using .as_slice(). However, this does not work for collections which don't provide an as_slice() method (such as HashMap, RingBuf, and a long etc.)

I think it would be useful to have a RandomElement trait providing random_element<T: Rng>(&self, rng: T) -> Option<...>.

Does this need an RFC or should I just submit a PR?

cc @aturon

You mean something like:

fn random_sample<A, T>(mut iter: A) -> Option<T>
    where A: Iterator<T> {
{
    let mut elem = None;
    let mut i = 1f64;
    for new_item in iter {
        if std::rand::random::<f64>() < (1f64/i) {
            elem = Some(new_item);
        }
        i += 1.0;
    }
    elem
}

I'm not sure such a thing would be used often enough to justify its existence. Perhaps if you were to combine it with cool techniques such as resevoir sampling it could make a nice (external) crate?

Thiez at 2014-12-08 22:30:46

I'm not sure such a thing would be used often enough to justify its existence. Perhaps if you were to combine it with cool techniques such as resevoir sampling it could make a nice (external) crate?

Agreed. Especially with https://crates.io/ working, we are increasingly pushing toward experimentation happening in the crates.io ecosystem, and bringing APIs into std more gradually after they've proved their worth "on the market".
Aaron Turon at 2014-12-08 22:36:27
Such functionality cannot be "grafted on" out-of-tree though. At least, if you want any scrap of performance on key-based collections.
Aria Desires at 2014-12-08 23:06:26
@Gankro

Such functionality cannot be "grafted on" out-of-tree though. At least, if you want any scrap of performance on key-based collections.

Fair point. I'm mostly saying, it'd be good to have some harder evidence that this would be widely used before we drop it into std.
Aaron Turon at 2014-12-08 23:55:52
Actually, upon reflection it would also be expensive to provide even if it was in-tree. For tree-based structures you would have to be able to know the size of the subtrees to get any kind of "real" random distribution.

You basically have to be able to get the kth element of the collection to support this functionality efficiently. In which case it would be easy to offer up out-of-tree.
Aria Desires at 2014-12-09 00:10:35
One could easily provide it out-of-tree on top of RandomAccessIterator.
Aria Desires at 2014-12-09 00:11:18
I hadn't thought of the RandomAccessIterator... That would be a nice solution. I will close this and open an issue to provide a RandomAccessIterator for our collections.
Adolfo Ochagavía at 2014-12-09 07:59:53