Как отсортировать вектор в порядке убывания в Rust?

Question

В Rust методы сортировки Vec всегда располагают элементы от наименьшего к наибольшему. Каков универсальный способ сортировки от наибольшего к наименьшему?

Если у вас есть вектор чисел, вы можете предоставить функцию извлечения ключа, которая «инвертирует» число следующим образом:

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

Но это не очень понятно, и это не просто расширить этот метод для других типов, таких как строки.

Answer 1

Есть как минимум три способа сделать это.

Функция сравнения с переворотом

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

Это переключает порядок, в котором сравниваются элементы, так что меньшие элементы кажутся больше функция сортировки и наоборот.

Оболочка с обратным экземпляром Ord

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

Reverse - это обобщенная оболочка c, которая имеет экземпляр 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"