Rust In-Place Shuffle (rip_shuffle)
This crate contains several efficient in-place shuffling algorithms to generate random permutations. Their design and performances is analyzed in detail in the paper "Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place" [M. Penschuck].
At time of writing, the default sequential implementation is 1.5 to 4 times faster than rand::shuffling
.
The parallel implementation can get several orders of magnitute faster.
All implementations are in-place and do not use heap allocations (though, the parallel algorithms may set up a Rayon worker pool, if it's not already the case).
Usage
Include the following into your Cargo.toml
file:
[]
={="0.2"}
For general use cases, we export the two traits [RipShuffleSequential
] and [RipShuffleParallel
] which
expose the functions seq_shuffle
and par_shuffle
, respectively. The sequential variant seq_shuffle
can be used as a drop-in replacement for rand::shuffle
:
use RipShuffleSequential;
let mut data : = .into_iter.collect;
data.seq_shuffle;
The parallel variant imposes some constraints on the random number generator: it needs to be a [rand::SeedableRng
] and
support [std::marker::Send
] and [std::marker::Sync
]. Most prominently, this is not the case for [rand::rngs::ThreadRng
].
However, you can seed a compatible instace (e.g., [rand::rngs::StdRng
] or [rand_pcg::Pcg64
]) from [rand::rngs::ThreadRng
] and then pass them:
use RipShuffleParallel;
use *;
let mut data : = .into_iter.collect;
let mut rng = from_rng.unwrap;
data.par_shuffle;
As a short-hand you can use RipShuffleParallel::par_shuffle_seed_with
. This methods supports arbitrary Rng
s
to seed a Pcg64Mcg
from them:
use RipShuffleParallel;
let mut data : = .into_iter.collect;
data.par_shuffle_seed_with;
Features
This crate has two default feature sets which should be appropriate for most cases and do not change the API.
default
is supposed to work with all recent rust compilersnightly_default
requires nightly features but may yield slightly faster binaries. If you are using a non-stable compiler consider enabling this feature.
This crate supports the following features:
unsafe_algos
(enabled bydefault
) this feature enables algorithms that rely on pointer arithmetic, but are faster than their safe variantsseed_with
(enabled bydefault
) adds a dependency to [rand_pcg
] and offers the [RipShuffleParallel::par_shuffle_seed_with
] short-hand.prefetch
(enabled bynightly_default
) enables explicit prefetching via [std::intrinsics::prefetch_write_data
] to speed-up shuffling. This feature does require a nightly-channel compiler.
To disable these feature, you can adopt the dependency
in your Cargo.toml
, for instace:
={="0.2", = false, = ["seed_with"]}