Как мне частично отсортировать Vec или срез?

Question

Мне нужно получить N лучших предметов от Vec, который довольно большой в производстве.В настоящее время я делаю это неэффективным способом:

let mut v = vec![6, 4, 3, 7, 2, 1, 5];
v.sort_unstable();
v = v[0..3].to_vec();

В C ++ я бы использовал std::partial_sort, но я не могу найти эквивалент в документах Rust.

Я просто пропускаю это или он не существует (пока)?

Answer 1

Стандартная библиотека не содержит этой функции, но, похоже, ящик lazysort - это именно то, что вам нужно:

Так в чем смысл ленивой сортировки?Согласно связанному сообщению в блоге, они полезны, когда вам не нужно или намереваетесь понадобиться каждое значение;например, вам могут понадобиться только первые 1000 упорядоченных значений из большего набора.

#![feature(test)]

extern crate lazysort;
extern crate rand;
extern crate test;

use std::cmp::Ordering;

trait SortLazy<T> {
    fn sort_lazy<F>(&mut self, cmp: F, n: usize)
    where
        F: Fn(&T, &T) -> Ordering;
    unsafe fn sort_lazy_fast<F>(&mut self, cmp: F, n: usize)
    where
        F: Fn(&T, &T) -> Ordering;
}

impl<T> SortLazy<T> for [T] {
    fn sort_lazy<F>(&mut self, cmp: F, n: usize)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        fn sort_lazy<F, T>(data: &mut [T], accu: &mut usize, cmp: &F, n: usize)
        where
            F: Fn(&T, &T) -> Ordering,
        {
            if !data.is_empty() && *accu < n {
                let mut pivot = 1;
                let mut lower = 0;
                let mut upper = data.len();
                while pivot < upper {
                    match cmp(&data[pivot], &data[lower]) {
                        Ordering::Less => {
                            data.swap(pivot, lower);
                            lower += 1;
                            pivot += 1;
                        }
                        Ordering::Greater => {
                            upper -= 1;
                            data.swap(pivot, upper);
                        }
                        Ordering::Equal => pivot += 1,
                    }
                }
                sort_lazy(&mut data[..lower], accu, cmp, n);
                sort_lazy(&mut data[upper..], accu, cmp, n);
            } else {
                *accu += 1;
            }
        }
        sort_lazy(self, &mut 0, &cmp, n);
    }

    unsafe fn sort_lazy_fast<F>(&mut self, cmp: F, n: usize)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        fn sort_lazy<F, T>(data: &mut [T], accu: &mut usize, cmp: &F, n: usize)
        where
            F: Fn(&T, &T) -> Ordering,
        {
            if !data.is_empty() && *accu < n {
                unsafe {
                    use std::mem::swap;
                    let mut pivot = 1;
                    let mut lower = 0;
                    let mut upper = data.len();
                    while pivot < upper {
                        match cmp(data.get_unchecked(pivot), data.get_unchecked(lower)) {
                            Ordering::Less => {
                                swap(
                                    &mut *(data.get_unchecked_mut(pivot) as *mut T),
                                    &mut *(data.get_unchecked_mut(lower) as *mut T),
                                );
                                lower += 1;
                                pivot += 1;
                            }
                            Ordering::Greater => {
                                upper -= 1;
                                swap(
                                    &mut *(data.get_unchecked_mut(pivot) as *mut T),
                                    &mut *(data.get_unchecked_mut(upper) as *mut T),
                                );
                            }
                            Ordering::Equal => pivot += 1,
                        }
                    }
                    sort_lazy(&mut data[..lower], accu, cmp, n);
                    sort_lazy(&mut data[upper..], accu, cmp, n);
                }
            } else {
                *accu += 1;
            }
        }
        sort_lazy(self, &mut 0, &cmp, n);
    }
}

#[cfg(test)]
mod tests {
    use test::Bencher;

    use lazysort::Sorted;
    use std::collections::BinaryHeap;
    use SortLazy;

    use rand::{thread_rng, Rng};

    const SIZE_VEC: usize = 100_000;
    const N: usize = 42;

    #[bench]
    fn sort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = thread_rng();
            let mut v: Vec<i32> = std::iter::repeat_with(|| rng.gen())
                .take(SIZE_VEC)
                .collect();
            v.sort_unstable();
        })
    }

    #[bench]
    fn lazysort(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = thread_rng();
            let v: Vec<i32> = std::iter::repeat_with(|| rng.gen())
                .take(SIZE_VEC)
                .collect();
            let _: Vec<_> = v.iter().sorted().take(N).collect();
        })
    }

    #[bench]
    fn lazysort_in_place(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = thread_rng();
            let mut v: Vec<i32> = std::iter::repeat_with(|| rng.gen())
                .take(SIZE_VEC)
                .collect();
            v.sort_lazy(i32::cmp, N);
        })
    }

    #[bench]
    fn lazysort_in_place_fast(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = thread_rng();
            let mut v: Vec<i32> = std::iter::repeat_with(|| rng.gen())
                .take(SIZE_VEC)
                .collect();
            unsafe { v.sort_lazy_fast(i32::cmp, N) };
        })
    }

    #[bench]
    fn binaryheap(b: &mut Bencher) {
        b.iter(|| {
            let mut rng = thread_rng();
            let v: Vec<i32> = std::iter::repeat_with(|| rng.gen())
                .take(SIZE_VEC)
                .collect();

            let mut iter = v.iter();
            let mut heap: BinaryHeap<_> = iter.by_ref().take(N).collect();
            for i in iter {
                heap.push(i);
                heap.pop();
            }
            let _ = heap.into_sorted_vec();
        })
    }
}

running 5 tests
test tests::binaryheap             ... bench:   3,283,938 ns/iter (+/- 413,805)
test tests::lazysort               ... bench:   1,669,229 ns/iter (+/- 505,528)
test tests::lazysort_in_place      ... bench:   1,781,007 ns/iter (+/- 443,472)
test tests::lazysort_in_place_fast ... bench:   1,652,103 ns/iter (+/- 691,847)
test tests::sort                   ... bench:   5,600,513 ns/iter (+/- 711,927)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured; 0 filtered out

Этот код позволяет нам увидеть, что lazysort быстрее, чем решение с BinaryHeap,Мы также видим, что решение BinaryHeap ухудшается при увеличении N.

Проблема с lazysort заключается в том, что оно создает второе Vec<_>.«Лучшим» решением было бы реализовать частичную сортировку на месте.Я привел пример такой реализации.

Имейте в виду, что все эти решения идут с накладными расходами.Когда N равен SIZE_VEC / 3, классический sort выигрывает.

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