Lib.rs

› 算法 | 并发
#排序 #算法 #研究 #radix-sort

voracious_radix_sort

最先进的基数排序算法。单线程和多线程版本。

作者： lakwet

5个版本 (稳定)

1.2.0 2023年3月20日
1.1.1 2022年8月20日
1.1.0 2020年11月7日
1.0.0 2020年9月9日
0.1.0 2020年3月16日

#349 in 算法

Download history 16/week @ 2024-03-11 38/week @ 2024-03-18 8/week @ 2024-03-25 41/week @ 2024-04-01 24/week @ 2024-04-08 22/week @ 2024-04-15 36/week @ 2024-04-22 38/week @ 2024-04-29 9/week @ 2024-05-06 20/week @ 2024-05-13 25/week @ 2024-05-20 40/week @ 2024-05-27 31/week @ 2024-06-03 35/week @ 2024-06-10 33/week @ 2024-06-17 54/week @ 2024-06-24

每月155次下载
在 6 个crate中（直接使用2个）使用

MIT许可证

715KB
16K SLoC

Voracious sort

Rust Rust

尊敬的访客，欢迎。

简介

本项目的目的是提供一个单线程和多线程版本的最先进的基数排序的Rust实现。

这个crate应该易于使用，排序应该能够对几乎所有内容进行排序。基数排序因其只能对无符号整数进行排序而受到批评。本项目证明这是错误的，Voracious sort可以排序所有Rust原生类型（目前除String、Tuple和Array外）以及自定义结构体。它在大多数类型和数据分布上比Rust标准排序和Rust不稳定排序要快得多。

由于Rust孤儿规则，我们选择不支持元组排序。您可以使用结构体。

您在这里可以找到

  • 版本
  • 许可证
  • 关于排序名称的一些说明
  • 如何使用此排序的文档说明，
  • 基数排序：基本概念，
  • 基准测试,
  • 针对开发人员和研究人员
  • 本项目中使用的参考文献，
  • 未来工作，

版本

测试/使用过的最新版本

  • Rustc: 1.46.0稳定版
  • Rustfmt: 1.4.18稳定版
  • Cargo: 1.46.0稳定版
  • Clippy: 0.0.212

许可证

本项目采用 MIT 许可证。

请参阅许可证文件。

关于排序名称的一些说明

当我询问该给这个排序起什么名字时，我的一个同事提出了voracious sort（对基数排序的一种巧妙构思，想象在无数次的会话中）。这个名字很有趣，所以我采用了它。确实，我花了很多时间来编写这个项目。

您也可以把它想象成一个非常贪吃的萝卜...

关于内存消耗的免责声明

在voracious特性行为中实现的排序可能位置不正确，这意味着它可以使用达到数组大小2倍的内存。如果您想确保使用原地算法，请使用排序函数而不是特性行为。

关于数组大小的免责声明

基数排序旨在用于非常大的数组。我创建了这个crate以也能对较小的数组进行排序，但voracious将回退到Rust的本地排序。我让用户阅读基准测试结果，以了解他们是否需要voracious排序。

文档：如何使用它？

因为它已经在crate文档中解释过了，所以我们只提供链接

我们假设您知道如何用Rust编写代码...

其他实现示例

基数排序：基本概念

基数排序是一种非比较排序。它需要一个键和使用二进制表示来排序输入，而不是比较函数。在基数排序中，有两种子组

  • LSD：最不重要的最高有效位（或LSB：最不重要的最高有效位）
  • MSD：最重要的最高有效位（或MSB：最重要的最高有效位）

它们之间的区别在于算法如何迭代二进制表示。

排序可以是稳定的或不稳定的；一般来说，LSD是稳定的，而MSD往往是不稳定的。请注意，计算机科学领域中“稳定”这个术语可能是有歧义的，我们指的是排序算法稳定性的维基百科页面上的这个定义。

排序可以是原地或非原地的。如果一个排序不需要比输入使用的初始内存更多的内存，则称其为原地排序。如果一个排序确实需要更多内存（通常，为O(n)），则称其为非原地排序。LSD排序是非原地的，而MSD排序可以是任一种。

回退是我们执行的操作，因为基数排序在小输入上表现不佳。为了避免这种性能损失，当输入变得太小时，基数排序会回退到另一种排序。插入排序非常适合长度小于或等于32个元素的输入。回退可以在算法的开始发生，我们检查输入的长度并相应地选择排序，或者当剩余输入足够小的时候在递归调用的末尾触发它。

基数本身，是排序算法每次遍历时考虑的位数。选择基数的通常值是8，然而，这可能会根据您的用例而变化。

在基数排序中，您使用一个大小为2.pow(基数)的直方图。给定一个级别[1]和基数，我们可以计算直方图。这个直方图提供了所有桶的大小，因此，算法知道每个元素应该移动到哪里。关于一个详细示例，我让读者阅读基数排序的维基百科页面。

[1]：如果选择了8的基数，级别1是前8位，级别2是接下来的8位，以此类推，直到没有更多的位要处理。

基准测试

首先，请阅读：PROFILING.md。

基准测试可用于此处：结果文件夹

对于每种排序，3列

  • 第1列：微秒时间
  • 第2列：标准差（如果有多次迭代）纳秒
  • 第3列：每项时间纳秒

针对开发人员和研究人员

  • 美国国旗排序是一种MSD基数排序。它是著名的算法https://en.wikipedia.org/wiki/American_flag_sort的实现。

  • 贪婪排序是一种MSD基数排序。它是Ska排序的改进，并使用Verge排序预处理启发式。根据类型和输入大小，可能会选择另一种排序算法（LSD排序、计数排序等）。

  • DLSD（转向LSD基数排序）是DFR排序的简化版本，具有不同的转向和可变基数（见文章）。

  • Thiel排序是一种LSD基数排序。它是快速基数排序的实现：放宽对最低有效位基数排序的计数要求（C/C++实现并非来自文章作者）。

  • 过山车排序是一种混合基数排序。它开始时是一个MSD基数排序，然后切换为LSD基数排序。它是贪婪排序和DLSD排序的混合体。这种排序算法针对有符号整数有启发式方法。它在32位或64位浮点数和有符号整数上表现非常好。这是我向科学界的贡献。

  • Peeka排序是一种多线程MSD基数排序。它是MIT研究人员区域排序算法的改进：区域排序Regions sort：理论高效且实用的并行就地基数排序。这也是我向科学界的贡献。

  • 所有排序在非常小的输入或Rust（稳定）排序中都会回退到PDQ排序（Rust不稳定排序）。

参考文献

未来工作

  • 完成性能分析。
  • 改进k-way-merge算法（添加多线程）。
  • 添加字符串排序（Spreadsort和/或Burstsort）。
  • 找到多线程Verge排序预处理启发式的方法。
  • 添加稳定的并行排序。
  • 改进针对有符号整数的并行排序。
  • 添加按键稳定的/不稳定的排序（避免在排序过程中移动/复制元素）。
  • 更多改进！

依赖项