5个不稳定版本
使用旧Rust 2015
| 0.3.1 | 2019年3月16日 |
|---|---|
| 0.3.0 | 2018年8月12日 |
| 0.2.0 | 2017年10月22日 |
| 0.1.1 | 2017年10月2日 |
| 0.1.0 | 2017年10月1日 |
#1296 in 算法
用于 crate-race
27KB
362 行
Rust的American Flag排序
afsort crate实现了一种基于American Flag排序的排序算法。当前实现仅限于排序字节切片，例如字符串。主要动机是排序文本字符串，因此大多数基准测试都基于英文文本字符串。在排序英文单词时，此实现似乎比Rust标准库中的sort_unstable快约40%。
对于小输入，此方法会回退到标准库。
安装
将依赖项添加到您的Cargo.toml
[dependencies]
afsort = "0.2"
在您的crate根目录下
extern crate afsort;
警告：版本0.1.0存在缺陷（慢），请使用0.1.1或更高版本。
关于0.1.x -> 0.2.x的升级说明：方法afsort::sort_unstable()已被移除。请使用AFSortable trait中的af_sort_unstable代替。
用法
现在您可以使用afsort来排序字符串数组或字符串切片等。
use afsort::AFSortable;
let mut strings = vec!("red", "green", "blue");
strings.af_sort_unstable();
assert_eq!(strings, vec!["blue", "green", "red"]);
它也适用于u8, u16, u32和u64
use afsort::AFSortable;
let mut strings = vec!(1u32, 2u32, 7u32);
strings.af_sort_unstable();
assert_eq!(strings, vec![1u32, 2u32, 7u32]);
您还可以通过提取函数进行排序，例如。
use afsort;
let mut tuples = vec![("b", 2), ("a", 1)];
afsort::sort_unstable_by(&mut tuples, |t| &t.0);
assert_eq!(tuples, vec![("a", 1), ("b", 2)]);
af_sort_unstable()方法对所有实现afsort::DigitAt和Ord trait的值的所有切片进行了实现。&str、String、[u8]、u8、u16、u32和u64实现了。所有这些也实现了Ord。您还可以为任何其他类型实现此trait。
动机
本质上，我发现使用 fst 包进行字符串排序耗时较长，因为它要求输入必须有序。由于字符串排序是一个普遍问题，现在这个功能已经成为一个包。
性能
如前所述，在排序随机的英文单词字符串时，这种实现似乎比标准库中的排序快约40%。对于已排序的字符串，它较慢。该实现相当简单，所以我不会惊讶如果它还能进一步改进。
对于数字，目前它似乎比标准库慢。我怀疑这可能是由于在 afsort 中比在标准库中发生更多交换。我想解决这个问题。
不过，这将严重受到输入值分布的影响。就像性能问题一样：效果可能因人而异。请分析你的使用情况。
你可以使用以下命令运行基准测试：cargo bench（目前需要nightly rust），如下所示
% cargo bench
Finished release [optimized] target(s) in 0.0 secs
Running target/release/deps/afsort-2f0d4e495216be99
running 10 tests
test tests::correct_radix_for_u16 ... ignored
test tests::correct_radix_for_u32 ... ignored
test tests::correct_radix_for_u64 ... ignored
test tests::correct_radix_for_u8 ... ignored
test tests::sorts_strings_same_as_unstable ... ignored
test tests::sorts_tuples_same_as_unstable ... ignored
test tests::sorts_u16_same_as_unstable ... ignored
test tests::sorts_u32_same_as_unstable ... ignored
test tests::sorts_u64_same_as_unstable ... ignored
test tests::sorts_u8_same_as_unstable ... ignored
test result: ok. 0 passed; 0 failed; 10 ignored; 0 measured; 0 filtered out
Running target/release/deps/bench-42a0c77149fb906a
running 16 tests
test sort_en_strings_lower_10_000_af ... bench: 1,881,300 ns/iter (+/- 618,858)
test sort_en_strings_lower_10_000_std ... bench: 2,594,388 ns/iter (+/- 767,774)
test sort_en_strings_rand_100_000_af ... bench: 23,101,465 ns/iter (+/- 12,052,025)
test sort_en_strings_rand_100_000_std ... bench: 31,536,516 ns/iter (+/- 12,910,887)
test sort_en_strings_rand_10_000_af ... bench: 1,588,372 ns/iter (+/- 568,509)
test sort_en_strings_rand_10_000_std ... bench: 2,193,132 ns/iter (+/- 648,297)
test sort_en_strings_sorted_10_000_af ... bench: 806,419 ns/iter (+/- 128,186)
test sort_en_strings_sorted_10_000_std ... bench: 589,161 ns/iter (+/- 340,707)
test sort_u16_1_000_000_af ... bench: 19,442,855 ns/iter (+/- 1,642,992)
test sort_u16_1_000_000_std ... bench: 21,401,736 ns/iter (+/- 3,607,120)
test sort_u32_1_000_000_af ... bench: 31,682,863 ns/iter (+/- 5,254,810)
test sort_u32_1_000_000_std ... bench: 30,809,651 ns/iter (+/- 1,623,271)
test sort_u64_1_000_000_af ... bench: 39,730,940 ns/iter (+/- 6,139,556)
test sort_u64_1_000_000_std ... bench: 32,477,660 ns/iter (+/- 1,733,969)
test sort_u8_1_000_af ... bench: 11,330 ns/iter (+/- 702)
test sort_u8_1_000_std ... bench: 8,764 ns/iter (+/- 163)
test result: ok. 0 passed; 0 failed; 0 ignored; 16 measured; 0 filtered out
局限性
美国国旗算法是不稳定的，这与标准库中的 sort_unstable 一样。也就是说，相等的元素可能会重新排序。
此包只能根据字符串的 utf-8 字节值进行排序。对于许多问题，这是可以的。然而，如果您想将字符串用于用户显示，则区域设置可能很重要。此包不试图解决这个问题。
测试
测试使用 quickcheck 包进行。我们运行了大约50k种不同的输入字符串和数字的变体。我们将标准库的 sort_unstable 视为黄金标准。这意味着这个库在功能上可能像标准库一样没有错误（至少在功能上）。
许可协议
此存储库在MIT许可下发布，但英文-american.txt词典文件除外，它来自Linux单词包，因此受GPL许可。该词典仅用于测试目的。