如何在Rust中按降序对Vector进行排序?

nnnm毫米

在Rust中,a的排序方法Vec始终将元素从最小到最大排列。从最大到最小排序的通用方法是什么?

如果您有一个数字向量,则可以提供一个键提取函数来像这样“反转”数字:

let mut numbers: Vec<u32> = vec![100_000, 3, 6, 2];
numbers.sort_by_key(|n| std::u32::MAX - n);

但这还不是很清楚,并且将该方法扩展到其他类型(例如字符串)也不是一件容易的事。

nnnm毫米

至少有三种方法可以做到这一点。

翻转比较功能

vec.sort_by(|a, b| b.cmp(a))

这样可以切换比较元素的顺序,以便较小的元素在排序功能中显得较大,反之亦然。

具有反向Ord实例的包装器

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.rsCargo.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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

如何在 SQLAlchemy 中按降序对结果进行排序?

如何在Ruby中按降序对数组进行排序

如何在MapReduce中按降序对数据进行排序?

如何在Scala中按数字对中的第二对按降序对数字对列表进行排序?

如何在dataweave中对降序进行排序?

如何在 Swift 中按倒序/降序按长度对字符串数组进行排序?

如何在表中按升序和降序对数据进行排序

如何在Java流中按值降序对LinkedHashMap进行排序?

如何在Bash中按降序对字符串数组进行排序?

如何在Reactjs中按升序或降序对数据进行排序?

如何在Power Bi中按矩阵的降序对列日期进行排序

如何在Spark SQL中按列降序排序?

如何在C中按降序对结构数组排序

如何按降序对评论进行排序?

如何在iOS的降序排列中对数组进行排序?

使用Python中的zip函数对2个相关列表进行排序,如何按降序排序?

如何按降序排序?

如何在Kibana的“发现”选项卡上按日期/时间降序进行排序。

按降序对结构进行排序

按降序对整数进行排序

按降序对堆栈进行排序

如何在R中按列按降序对数据排序

如何使用 React 中的功能组件按降序对数据进行排序并显示在表格中

如何(如果可能)在Rust中按值对BTreeMap进行排序?

VB-如何按升序或降序对数据库中的结果进行排序

如果JS中存在值,如何根据日期按降序对数组进行排序?

如何使用数组中的 moment.js 按降序对日期进行排序

如何找到在JavaScript中按降序对数字数组进行排序所需的最小交换次数

如何使用 LINQ 在 C# 中按降序对嵌套字典进行排序