首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在Rust中对向量进行降序排序?

问如何在Rust中对向量进行降序排序?
EN

Stack Overflow用户
提问于 2020-03-29 23:08:13
回答 1查看 10.5K关注 0票数 22

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

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

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

但这并不是很清楚,而且将该方法扩展到其他类型(如字符串)也不简单。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-03-29 23:08:13

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

翻转比较函数

代码语言:javascript
复制
vec.sort_by(|a, b| b.cmp(a))

这将围绕比较元素的顺序进行切换,以便较小的元素在排序函数中显示较大,反之亦然。

具有反向排序实例的包装器

代码语言:javascript
复制
use std::cmp::Reverse;
vec.sort_by_key(|w| Reverse(*w));

Reverse是一个通用包装器,它有一个与包装类型的顺序相反的Ord实例。

如果您试图通过删除Reverse来返回包含引用的*,则会导致生命周期问题,这与在sort_by_key中直接返回引用时相同(另请参阅this question)。因此,此代码片段只能与键为Copy类型的向量一起使用。

排序,然后反转

代码语言:javascript
复制
vec.sort();
vec.reverse();

它最初以错误的顺序排序,然后颠倒所有元素。

性能

我使用criterion对这三种方法进行了基准测试,以获得length 100_000 Vec<u64>。计时结果按上述顺序列出。左边和右边的值分别表示置信区间的下界和上界,中间的值是criterion的最佳估计。

性能是可比的,尽管翻转的比较函数似乎慢了一点:

代码语言:javascript
复制
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。这里有一个额外的基准测试,它检查克隆载体的成本与排序无关,它只需要几微秒。

代码语言:javascript
复制
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);
代码语言:javascript
复制
[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"
票数 68
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/60916194

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档