为什么 Rust 的默认排序功能比我的选择排序慢？

Question

标题。我对 Rust 很陌生，所以我可能会错过一些简单的东西。我正在使用 Rust 1.70.0-nightly。这是必要的代码：

fn selection_sort(original_vec: &mut Vec<i32>) -> Vec<i32> {
    for i in 0..original_vec.len()-1 {
        let mut smallest: usize = i;
        for j in i+1..original_vec.len() {
            if original_vec[j] < original_vec[smallest] {
                smallest = j;
            }
        }
        if smallest != i {
            original_vec.swap(i, smallest);
        }
    };
    original_vec.to_vec()
}

// helper function for testing (uses builtin sort function)
fn rust_sort<A, T>(mut array: A) -> A
where
    A: AsMut<[T]>,
    T: Ord,
{
    let slice = array.as_mut();
    slice.sort();

    array
}

const TEST_VECS: [[i32; 10]; 6] = [
    [1, 3, 2, 9, 6, 7, 4, 10, 8, 5],
    [1, 2, 7, 2, 9, 9, 7, 10, 2, 1],
    [0, 4, 1, 3, 9, 12, 3, 0, 13, 8],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    [-1, -5, -10, 1, 10, 2, -123, -34, 0, -32],
    [i32::MAX, -32984, i32::MIN, 31648, 5349857, -30954, -2343285, 0, 1, i32::MIN],
];

#[bench]
fn bench_rust_sort(b: &mut Bencher) {
    b.iter(|| {
        for i in TEST_VECS {
            (&mut i.to_vec()).sort()
        }
    })
}

#[bench]
fn bench_selection_sort(b: &mut Bencher) {
    b.iter(|| {
        for i in TEST_VECS {
            selection_sort(&mut i.to_vec());
        }
    })
}

当我跑步时

cargo bench

：

$ cargo bench
  Compiling rust-algs v0.1.0 (/home/josia/projects/rust-algs)
    Finished bench [optimized] target(s) in 0.25s
     Running unittests src/lib.rs (target/release/deps/rustalgs-ae260c07593c3aad)

running 3 tests
test test_selection_sort ... ignored
test bench_rust_sort      ... bench:         106 ns/iter (+/- 8)
test bench_selection_sort ... bench:         102 ns/iter (+/- 9)

test result: ok. 0 passed; 0 failed; 1 ignored; 2 measured; 0 filtered out; finished in 7.65s

我尝试了很多次，甚至重命名了测试函数来改变测试的顺序。不管怎样，我的自定义选择排序功能仍然执行得更快。我猜问题在于我必须调用一个函数来包装主要的默认排序函数。调用实际函数是行不通的，因为即使我将基准函数中的

TEST_VECS

常量克隆为向量，排序函数也会继续对其进行排序，这不会让其他基准迭代对其进行排序。如果我在基准闭包中克隆常量，它将极大地影响基准迭代的性能，并且我将无法仅对我尝试运行的代码进行基准测试。

我对这些函数进行基准测试的方式是否有问题，或者我的自定义函数是否更快？

Answer 1

您正在转换类型和应对记忆。

• 将数组转换为向量需要时间。
• 如果您来自其他语言，您应该知道该常量无法修改。

所以你必须在基准代码中定义测试集。

• b:&mut test::Bencher

  将用作长凳。

• b.iter

  之外的代码不会被计入bench。

所以你必须像这样准备你的代码：

#![feature(test)]
#![allow(dead_code)]
extern crate test;
fn selection_sort(original_vec: &mut Vec<i32>) -> Vec<i32> {
    for i in 0..original_vec.len()-1 {
        let mut smallest: usize = i;
        for j in i+1..original_vec.len() {
            if original_vec[j] < original_vec[smallest] {
                smallest = j;
            }
        }
        if smallest != i {
            original_vec.swap(i, smallest);
        }
    };
    original_vec.to_vec()
}

#[bench]
fn bench_rust_sort(b: &mut test::Bencher) {
    let mut test_vecs: Vec<Vec<i32>>= vec![
        vec![1, 3, 2, 9, 6, 7, 4, 10, 8, 5],
        vec![1, 2, 7, 2, 9, 9, 7, 10, 2, 1],
        vec![0, 4, 1, 3, 9, 12, 3, 0, 13, 8],
        vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
        vec![-1, -5, -10, 1, 10, 2, -123, -34, 0, -32],
        vec![i32::MAX, -32984, i32::MIN, 31648, 5349857, -30954, -2343285, 0, 1, i32::MIN],
    ];
    b.iter(|| {
        for i in test_vecs.iter_mut() {
            i.sort()
        }
    })
}

#[bench]
fn bench_selection_sort(b: &mut test::Bencher) {
    let mut test_vecs: Vec<Vec<i32>>= vec![
        vec![1, 3, 2, 9, 6, 7, 4, 10, 8, 5],
        vec![1, 2, 7, 2, 9, 9, 7, 10, 2, 1],
        vec![0, 4, 1, 3, 9, 12, 3, 0, 13, 8],
        vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
        vec![-1, -5, -10, 1, 10, 2, -123, -34, 0, -32],
        vec![i32::MAX, -32984, i32::MIN, 31648, 5349857, -30954, -2343285, 0, 1, i32::MIN],
    ];
    b.iter(|| {
        for i in test_vecs.iter_mut() {
            selection_sort(i);
        }
    })
}

fn main(){
    
}

结果如下：

➜  bench git:(master) ✗ cargo bench
    Finished bench [optimized] target(s) in 0.00s
     Running unittests src/main.rs (target/release/deps/bench-5bf7ec1e7001cf33)

running 2 tests
test bench_rust_sort      ... bench:          43 ns/iter (+/- 0)
test bench_selection_sort ... bench:         215 ns/iter (+/- 14)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 6.40s

我的笔记本电脑运行这个工作台： MacBook Pro 2020 i5，4 核 2.0Ghz。