rdst

rdst 是一个灵活的多线程不稳定基数排序的原生Rust实现。

用法

let mut my_vec = vec![4, 7, 1, 6, 5, 3, 2, 8, 9];

my_vec.radix_sort_unstable();

在最简单的情况下，你可以通过调用 my_vec.radix_sort_unstable() 来使用这个排序。如果你有一个自定义类型需要排序，你可能需要为该类型实现 RadixKey。

默认实现

RadixKey 已经为以下类型的 Vec 和 [T] 默认实现

• u8, u16, u32, u64, u128, usize
• i8, i16, i32, i64, i128, isize
• f32, f64
• [u8;N]

实现 RadixKey

为了能够排序自定义类型，按照以下方式实现 RadixKey。

• LEVELS 应设置为你要考虑的每个排序项的总字节数
• get_level 应返回从最低有效字节到最高有效字节的相应字节

注意

• 这允许你实现跨越多个值或仅查看值一部分的基数键
• 你应该尽可能使这个操作尽可能快，因此考虑在可能的情况下使用无分支实现

use rdst::RadixKey;

struct MyType(u32);

impl RadixKey for MyType {
    const LEVELS: usize = 4;

    #[inline]
    fn get_level(&self, level: usize) -> u8 {
        (self.0 >> (level * 8)) as u8
    }
}

部分 RadixKey

如果你知道你的类型有始终为零的字节，你可以跳过这些字节以加快排序过程。例如，如果你有一个值永远不会超过 10000 的 u32，你只需要考虑两个字节。你可以这样实现：

use rdst::RadixKey;
struct U32Wrapper(u32);

impl RadixKey for U32Wrapper {
    const LEVELS: usize = 2;

    #[inline]
    fn get_level(&self, level: usize) -> u8 {
        (self.0 >> (level * 8)) as u8
    }
}

多值 RadixKey

如果你的类型有多个需要搜索的值，只需创建一个涵盖这两个值的 RadixKey。

use rdst::RadixKey;
struct MyStruct {
    key_1: u8,
    key_2: u8,
    key_3: u8,
}
impl RadixKey for MyStruct {
    const LEVELS: usize = 3;

    #[inline]
    fn get_level(&self, level: usize) -> u8 {
        match level {
          0 => self.key_1[0],
          1 => self.key_2[1],
          _ => self.key_3[0],
        }
    }
}

低内存变体

use rdst::RadixSort;
let mut my_vec: Vec<usize> = vec![10, 15, 0, 22, 9];
my_vec
    .radix_sort_builder()
    .with_low_mem_tuner()
    .sort();

此库还包括一个 主要 原地变体的基数排序。在内存或内存带宽更有限的情况下很有用。通常，此算法比标准算法略慢，但在特定情况下，此算法甚至可能提供速度提升。如果你需要最高级别的性能，值得对此进行基准测试。

单线程变体

要使此库使用完全单线程的算法和进程集，可以使用以下代码片段。

use rdst::RadixSort;
let mut my_vec: Vec<usize> = vec![10, 15, 0, 22, 9];

my_vec
    .radix_sort_builder()
    // Use a tuner that only includes single-threaded algorithms
    .with_single_threaded_tuner()
    // Don't run multiple algorithms (even single-threaded ones) in parallel
    .with_parallel(false)
    .sort();

注意：如果你仅使用此基数排序的单线程变体，你可以禁用 "multi-threaded" 依赖项的默认功能，以删除像 Rayon 这样的大型子依赖项。

[dependencies.rdst]
version = "x.y.z"
default-features = false

禁用 "multi-threaded" 功能后，默认的 my_data.radix_sort_unstable() 也会使用单线程调谐器。

自定义调谐器

调谐器是你可以实现的东西，用于控制使用哪些排序算法。此 crate 实现了许多基数排序算法，它们都有优缺点。如果你有一个非常特定的用例，可能值得自己调整排序。

use rdst::RadixSort;
use rdst::tuner::{Algorithm, Tuner, TuningParams};

struct MyTuner;

impl Tuner for MyTuner {
    fn pick_algorithm(&self, p: &TuningParams, _counts: &[usize]) -> Algorithm {
        if p.input_len >= 500_000 {
            Algorithm::Ska
        } else {
            Algorithm::Lsb
        }
    }
}

let mut my_vec: Vec<usize> = vec![10, 25, 9, 22, 6];
my_vec
    .radix_sort_builder()
    .with_tuner(&MyTuner {})
    .sort();

许可协议

根据您的选择，受以下任一协议的许可：

• Apache License，版本 2.0，（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT 许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

。

贡献

除非你明确声明，否则任何有意提交给作品并由你根据 Apache-2.0 许可证定义的贡献，都将根据上述内容双许可，不附加任何额外条款或条件。