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

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

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

但这还不是很清楚,而且将该方法扩展到字符串等其他类型也不容易.

推荐答案

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

Flipped comparison function

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

这将切换元素的比较顺序,以便较小的元素在排序函数中显示为较大的元素,反之亦然.

Wrapper with reverse Ord instance

use std::cmp::Reverse;
vec.sort_by_key(|w| Reverse(*w));

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

如果试图通过删除*来返回包含引用的Reverse,则会导致终生问题,与直接在sort_by_key中返回引用时一样(另请参见this question).因此,此代码段只能用于键为Copy类型的向量.

Sorting then reversing

vec.sort();
vec.reverse();

它最初按错误的顺序排序,然后反转所有元素.

Performance

我对这三种方法进行了基准测试,长度为criterion_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"

Rust相关问答推荐

如何将C指针到指针转换为Rust切片?

使用nom将任何空白、制表符、白线等序列替换为单个空白

如何容器化Linux上基于Rust的Windows应用程序的编译过程?

如何将元素添加到向量并返回对该元素的引用?

如何为utoipa中的可选查询参数生成OpenAPI模式?

为什么std repeat trait绑定在impl块和关联函数之间?

为什么实例方法可以像Rust中的静态方法一样被调用?

通过解引用将值移出Box(以及它被脱糖到什么地方)?

在Rust中宏的表达式中提取对象

如何创建一个可变的嵌套迭代器?

如何在AVX2中对齐/旋转256位向量?

为什么实现特征的对象期望比具体对象有更长的生命周期?

在 Rust 中,是否可以定义一个需要实现类型的构造函数的对象安全特征?

tokio::sync::broadcast::Receiver 不是克隆

当推送到 HashMap 中的 Vector 时,类型 `()` 无法取消引用

在没有任何同步的情况下以非原子方式更新由宽松原子操作 Select 的值是否安全?

不安全块不返回预期值

如何获得对数组子集的工作可变引用?

如何异步记忆选项中的 struct 字段

为什么 Rust 标准库同时为 Thing 和 &Thing 实现特征?