在Rust中,a的排序方法Vec
始终将元素从最小到最大排列。从最大到最小排序的通用方法是什么?
如果您有一个数字向量,则可以提供一个键提取函数来像这样“反转”数字:
let mut numbers: Vec<u32> = vec![100_000, 3, 6, 2];
numbers.sort_by_key(|n| std::u32::MAX - n);
但这还不是很清楚,并且将该方法扩展到其他类型(例如字符串)也不是一件容易的事。
至少有三种方法可以做到这一点。
vec.sort_by(|a, b| b.cmp(a))
这样可以切换比较元素的顺序,以便较小的元素在排序功能中显得较大,反之亦然。
use std::cmp::Reverse;
vec.sort_by_key(|w| Reverse(*w));
Reverse
是一个通用包装,其Ord
实例与包装类型的顺序相反。
如果您尝试Reverse
通过删除来返回包含引用的*
,则会导致生命周期问题,与直接在内部返回引用时相同sort_by_key
(另请参见此问题)。因此,此代码段只能与键为Copy
类型的向量一起使用。
vec.sort();
vec.reverse();
最初,它以错误的顺序排序,然后反转所有元素。
我criterion
以长度100_000为基准对这三种方法进行了基准测试Vec<u64>
。时序结果按上述顺序列出。左边和右边的值分别显示了置信区间的下限和上限,中间值是criterion
的最佳估计。
尽管翻转的比较功能似乎要慢一点,但性能是可比的:
Sorting/sort_1 time: [6.2189 ms 6.2539 ms 6.2936 ms]
Sorting/sort_2 time: [6.1828 ms 6.1848 ms 6.1870 ms]
Sorting/sort_3 time: [6.2090 ms 6.2112 ms 6.2138 ms]
要进行复制,请将以下文件另存为benches/sort.rs
和Cargo.toml
,然后运行cargo bench
。那里还有一个基准,用于检查克隆载体的成本与分拣相比是否无关紧要,仅需几微秒。
fn generate_shuffled_data() -> Vec<u64> {
use rand::Rng;
let mut rng = rand::thread_rng();
(0..100000).map(|_| rng.gen::<u64>()).collect()
}
pub fn no_sort<T: Ord>(vec: Vec<T>) -> Vec<T> {
vec
}
pub fn sort_1<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
vec.sort_by(|a, b| b.cmp(a));
vec
}
pub fn sort_2<T: Ord + Copy>(mut vec: Vec<T>) -> Vec<T> {
vec.sort_by_key(|&w| std::cmp::Reverse(w));
vec
}
pub fn sort_3<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
vec.sort();
vec.reverse();
vec
}
use criterion::{black_box, criterion_group, criterion_main, Criterion};
fn comparison_benchmark(c: &mut Criterion) {
let mut group = c.benchmark_group("Sorting");
let data = generate_shuffled_data();
group.bench_function("no_sort", |b| {
b.iter(|| black_box(no_sort(data.clone())))
});
group.bench_function("sort_1", |b| {
b.iter(|| black_box(sort_1(data.clone())))
});
group.bench_function("sort_2", |b| {
b.iter(|| black_box(sort_2(data.clone())))
});
group.bench_function("sort_3", |b| {
b.iter(|| black_box(sort_3(data.clone())))
});
group.finish()
}
criterion_group!(benches, comparison_benchmark);
criterion_main!(benches);
[package]
name = "sorting_bench"
version = "0.1.0"
authors = ["nnnmmm"]
edition = "2018"
[[bench]]
name = "sort"
harness = false
[dev-dependencies]
criterion = "0.3"
rand = "0.7.3"
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句