rdxsort-rs

Rust 中的快速基数排序

• 仓库： https://github.com/crepererum/rdxsort-rs
• 文档： https://crepererum.github.io/rdxsort-rs/
• 许可证： MIT

版权 (c) 2016 Marco Neumann

lib.rs:

RdxSort

这个 crate 实现了对不同数据类型的切片进行基数排序，可以直接或通过利用其他数据类型的实现。

实现另一种排序算法的主要原因是因为大多数排序算法都是比较方法。为了排序数据，它们依赖于一个比较数据元素的函数。可以证明这会导致平均时间复杂度为 O(n*log(n))，在最坏情况下为 O(n^2)。相比之下，基数排序利用了这样一个事实，即许多数据类型有一个可能值的有限范围，并且在这个范围内有一个有限的分辨率（这也适用于浮点数）。关于详细解释，请参阅维基百科文章。这种特殊处理的结果是降低了并且是恒定的复杂度 O(n*k)，其中 k 是对特定数据类型进行排序所需的固定轮数。

支持的数据类型

目前支持以下数据类型

• bool: 简单分为 2 部分
• char: 类似于 u32
• 无符号整数：原生实现，取决于宽度
• 有符号整数：将其拆分为正负两部分并使用无符号实现
• 浮点数：将数据拆分为 -∞，(-∞,-0)，-0，+0，(+0,+∞)，+∞，并将这两个范围视为无符号整数值。不支持 非规格数 和 NaN！
• 数组，元组：使用内部数据类型的实现
• 自定义数据类型...：填写提供的模板特质

示例

use rdxsort::*;

fn main() {
    let mut data = vec![2, 10, 0, 1];
    data.rdxsort();
    assert!(data == vec![0, 1, 2, 10]);
}

性能

当然，基数排序较低的运行时间复杂度在排序特定数据类型时显示出其力量。优势取决于类型的大小和复杂性。虽然短的无符号整数受益最大，但长类型并不显示出巨大的改进。以下列表显示了不同大小数据集排序所需的运行时间（ns）。数据集使用均匀分布进行采样。以下标记了最佳的算法

• 快速排序
• rdxsort（此软件包）
• 标准库

请注意，结果可能因硬件、编译器版本、操作系统版本和配置以及天气而异。

小型（1,000个元素）

对于小型数据集，基数排序可以是无符号整数大小为32位的数据类型的优势。对于64位，应首选标准库排序。

中型（10,000个元素）

对于中型数据集，由于64位类型的劣势相当小，因此可以盲目地使用基数排序。

大型（100,000个元素）

对于大型数据集，基数排序对所有数据类型都是很好的。

实现新类型

此软件包通过实现 RdxSortTemplate 允许您添加对新类型的支持。它描述了数据如何排序到桶中以及安排了多少轮排序。

use rdxsort::*;

// `Clone` is required for `RdxSort`
// `PartialEq` is only required for the equality assert, not for the actual sorting
#[derive(Clone, PartialEq)]
struct Foo {
    a: u8,
    b: u8,
}

impl RdxSortTemplate for Foo {
    // using `#[inline]` is generally recommended since it helps
    // the compiler to optimize the sorting algorithm
    #[inline]
    fn cfg_nbuckets() -> usize {
        // usually too high, but works as a simple demonstration
        // `256 = 2^8`
        256
    }

    #[inline]
    fn cfg_nrounds() -> usize {
        // one per sub-type
        2
    }

    #[inline]
    fn get_bucket(&self, round: usize) -> usize {
        // return the least significant digit first
        if round == 0 {
            self.b as usize
        } else {
            self.a as usize
        }
    }

    #[inline]
    fn reverse(_round: usize, _bucket: usize) -> bool {
        // not required in our case
        false
    }
}

fn main() {
    let mut data = vec![
        Foo{a: 5, b: 2},
        Foo{a: 0, b: 1},
        Foo{a: 5, b: 1},
        Foo{a: 0, b: 2},
    ];
    data.rdxsort();

    let reference = vec![
        Foo{a: 0, b: 1},
        Foo{a: 0, b: 2},
        Foo{a: 5, b: 1},
        Foo{a: 5, b: 2},
    ];
    assert!(data == reference);
}