Shuffling an IndexSet

[lovesegfault]

I have a need to periodically shuffle my IndexSets. Currently I built this by iterating, collecting to a vec, shuffling, iterating, collecting back into an IndexSet.

Is there a better way to do this? Could the IndexSet/Map expose a shuffle method?

[bluss]

A shuffle method is too application specific, a more general method is wanted for the map and set. The closest we have today is sorting, which can inform the design. However, we might not even want to commit to exposing all entries in a slice (which is what sort uses internally).

[cuviper]

You could implement a shuffle with a series of swap_indices -- that's basically how rand's shuffle works.

If we did this internally, it could be a bit faster because we would be able to shuffle the entries vector and then bulk-rebuild the indices table. That is basically what the sort methods do. However, we would also need randomness to do a shuffle -- perhaps that could be a callback:

    fn shuffle(&mut self, random_index: impl FnMut(Range<usize>));

Alternative hack: you could call sort_by with a randomized comparison function.

[lovesegfault]

I really like that sort_by idea! Here's an example for future readers:

Rust Playground

use indexmap::IndexSet;
use rand::{
    distributions::{Distribution, Standard},
    Rng,
};
use std::cmp::Ordering;

struct RandomOrdering(Ordering);

impl Into<Ordering> for RandomOrdering {
    fn into(self) -> Ordering {
        self.0
    }
}

impl Distribution<RandomOrdering> for Standard {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> RandomOrdering {
        RandomOrdering(match rng.gen_range(0..2) {
            0 => Ordering::Less,
            1 => Ordering::Equal,
            _ => Ordering::Greater,
        })
    }
}

fn main() {
    let mut letters: IndexSet<char> = ('a'..='z').collect();
    println!("{:?}", letters);
    letters.sort_by(|_, _| rand::random::<RandomOrdering>().into());
    println!("{:?}", letters);
}

[bluss]

No guarantees for the uniformity of the shuffle with such an ordering function in sort. There should be literature on it; IUUC it is biased. Sorting by a cached random key should be the way to go if needed.

[cuviper]

Sorting by a cached random key should be the way to go if needed.

Hmm, we could wrap slice::sort_by_cached_key for this purpose (and other natural uses).

[cuviper]

Since #244, you can write something like map.sort_by_cached_key(|_, _| fastrand::u64(..)).