Rust原地洗牌 (rip_shuffle)

这个包包含几个高效的原地洗牌算法，用于生成随机排列。它们的设计和性能在论文“Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place” [M. Penschuck] 中被详细分析。

截至编写本文时，默认的顺序实现比 rand::shuffling 快1.5到4倍。并行实现可以快几个数量级。所有实现都是原地且不使用堆分配（尽管，并行算法可能会设置Rayon工作池，如果尚未设置）。

用法

将以下内容添加到您的 Cargo.toml 文件中

[dependencies]
rip_shuffle={version="0.2"}

对于通用用例，我们导出了两个特型 RipShuffleSequential 和 RipShuffleParallel，分别暴露了 seq_shuffle 和 par_shuffle 函数。顺序变体 seq_shuffle 可以用作 rand::shuffle 的直接替换。

use rip_shuffle::RipShuffleSequential;
let mut data : Vec<_> = (0..100).into_iter().collect();

data.seq_shuffle(&mut rand::thread_rng());

并行变体对随机数生成器施加了一些限制：它需要是一个 rand::SeedableRng 并支持 std::marker::Send 和 std::marker::Sync。最显著的是，这不适用于 rand::rngs::ThreadRng。然而，你可以从一个兼容实例（例如，rand::rngs::StdRng 或 rand_pcg::Pcg64）中对其进行播种，并将它们传递

use rip_shuffle::RipShuffleParallel;
use rand::prelude::*;

let mut data : Vec<_> = (0..1_000_000).into_iter().collect();

let mut rng = StdRng::from_rng(thread_rng()).unwrap();
data.par_shuffle(&mut rng);

作为简写，你可以使用 RipShuffleParallel::par_shuffle_seed_with。此方法支持任意 Rng 将其播种到一个 Pcg64Mcg

use rip_shuffle::RipShuffleParallel;
let mut data : Vec<_> = (0..1_000_000).into_iter().collect();

data.par_shuffle_seed_with(&mut rand::thread_rng());

特性

该包有两个默认特性集，适用于大多数情况，并且不更改API。

• default 应与所有最新的Rust编译器一起使用
• nightly_default 需要 nightly 特性，但可能生成稍微快一点的二进制文件。如果你使用的是非稳定编译器，请考虑启用此功能。

该包支持以下特性

• unsafe_algos（由 default 启用）此功能启用依赖于指针运算的算法，但比它们的安全变体更快
• seed_with（由 default 启用）添加了对 rand_pcg 的依赖关系，并提供了 RipShuffleParallel::par_shuffle_seed_with 简写。
• prefetch（由 nightly_default 启用）通过 std::intrinsics::prefetch_write_data 启用显式预取以加快洗牌。此功能需要一个 nightly-channel 编译器。

要禁用这些特性，你可以在你的 Cargo.toml 中采用 dependency，例如

rip_shuffle={version="0.2", default-features = false, features = ["seed_with"]}