20次发布
使用旧Rust 2015
| 0.2.1 | 2018年10月16日 |
|---|---|
| 0.2.0 | 2017年11月8日 |
| 0.1.1 | 2016年2月3日 |
| 0.1.0 | 2015年11月22日 |
| 0.0.2 | 2014年11月30日 |
#871 in 算法
3,711 每月下载量
用于 12 个crates（11个直接使用）
21KB
486 行
Lazysort
为迭代器添加了一个方法，该方法返回一个排序后的迭代器，该排序是使用快速排序算法进行惰性实现的。
可通过crates.io获取。
用法
extern crate lazysort;
use lazysort::Sorted;
use lazysort::SortedBy;
use lazysort::SortedPartial;
Sorted trait 为所有 Iterator<T: Ord> 添加了一个 sorted 方法，该方法返回默认顺序的同数据迭代器。
SortedBy trait 为所有 Iterator<T> 添加了一个 sorted_by 方法，该方法返回一个迭代器，该迭代器根据提供的闭包/函数类型 Fn(&T, &T) -> Ordering 对同数据进行排序。
SortedPartial trait 为所有 Iterator<T: PartialOrd> 添加了两个方法 sorted_partial_first 和 sorted_partial_last，它们返回默认顺序的同数据迭代器。这两个方法之间的区别在于不可比较的值在结果中是放在前面还是后面。
例如
let data: Vec<uint> = vec![9, 1, 3, 4, 4, 2, 4];
for x in data.iter().sorted() {
println!("{}", x);
}
将打印：1, 2, 3, 4, 4, 4, 9
更复杂的例子。按长度排序字符串，然后按默认字符串顺序排序
let before: Vec<&str> = vec!["a", "cat", "sat", "on", "the", "mat"];
before.iter().sorted_by(|a, b| {
match a.len().cmp(&b.len()) {
Equal => a.cmp(b),
x => x
}
})
返回一个迭代器，它产生： a， on， cat， mat， sat， the。
实现细节和性能
算法基本上与我在博客文章 使用惰性排序作为Clojure的惰性序列的例子 中描述的相同。但为了适应Rust的迭代器进行了修改。
从父迭代器读取完整序列，然后每次调用 next 都返回排序序列中的下一个值。排序是逐元素进行的，因此只有迭代到末尾才能实现完整的顺序。
算法是快速排序，但采用深度优先搜索；在每次调用 next 时，它执行查找下一个项目的必要工作，然后暂停状态，直到下一次调用 next。
为了测试性能，我们将其与使用标准库中的 sort 函数对整个向量进行排序，以及与 std::collections::BinaryHeap 进行比较。
首先，我们比较对整个向量进行排序时会发生什么
test benches::c_heap_bench ... bench: 3,703,166 ns/iter (+/- 454,189)
test benches::c_lazy_bench ... bench: 3,961,047 ns/iter (+/- 603,083)
test benches::c_standard_bench ... bench: 3,093,873 ns/iter (+/- 430,401)
三者之间存在差异，不出所料，内置排序是最快的。
这些基准测试是为排序 50,000 个随机 uint（0 <= x < 1000000）而设计的。运行 cargo bench 以运行它们。
那么，延迟排序有什么用呢？根据相关博客文章，当你不需要或打算需要每个值时，它们很有用；例如，你可能只需要从更大的集合中获取前 1,000 个有序值。
比较延迟方法 data.iter().sorted().take(x) 与标准方法（先排序向量然后取前 x 个值）的比较如下。
前 1,000 个中的第一个
test benches::a_heap_bench ... bench: 366,767 ns/iter (+/- 55,393)
test benches::a_lazy_bench ... bench: 171,923 ns/iter (+/- 52,784)
test benches::a_standard_bench ... bench: 3,055,734 ns/iter (+/- 348,407)
延迟方法要快得多；这是由于只有 50,000 个值被排序以识别前 1,000 个，其余的仍然未排序。 BinaryHeap 也相当快，原因相同。
前 10,000 个中的第一个
test benches::b_heap_bench ... bench: 1,126,774 ns/iter (+/- 156,833)
test benches::b_lazy_bench ... bench: 993,954 ns/iter (+/- 208,188)
test benches::b_standard_bench ... bench: 3,054,598 ns/iter (+/- 285,970)
在这种情况下，延迟方法仍然更快。
许可证
根据您的选择，许可权为以下之一
- 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 许可证定义，您有意提交的任何贡献，包括但不限于对工作的修改，都应按照上述方式双重许可，不得附加任何额外条款或条件。