sorting - 为什么我的 InsertionSort 的 Rust 实现比我的 C 版本慢？

Question

我决定开始学习一种编程语言来重写我的程序。第一个是大学二年级的一个简单程序。但是……看看测试!为什么简单的插入排序这么慢？

在 C 上测试:

ARRAY SIZE: 100000
< counting_sort:  0.003602
< insertion_sort: 8.273647
< heap_sort:      0.017918

Rust 测试:

ARRAY SIZE: 100000
< counting_sort:  PT0.039530982S
< insertion_sort: PT276.529915469S
< heap_sort:      PT0.117946209S

如何改进转换后的代码？

C 版:

void insertion_sort(int a[], int length) {
    int i, j, value;
    for (i = 1; i < length; i++) {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
    }
}

Rust 版本:

pub fn insertion_sort(array: &mut [i32]) {
    let mut value;
    for i in 1..array.len() {
        value = array[i];
        let mut flag = true;
        for j in (0..i).rev() {
            if array[j] > value {
                array[j + 1] = array[j];
            } else {
                flag = false;
                array[j + 1] = value;
                break;
            }
        }
        if flag {
            array[0] = value;
        }
    }
}

我没有在 Release模式下构建。即使在 Release模式下编译之后:

C 版本(gcc -O3):

ARRAY SIZE: 100000
< counting_sort:  0.001252
< insertion_sort: 1.672351
< heap_sort:      0.008694

Rust 版本(cargo build --release):

ARRAY SIZE: 100000
< counting_sort:  PT0.001556914S
< insertion_sort: PT3.291146043S
< heap_sort:      PT0.008269021S

Answer 1

Why is a simple insertion sort so slow?

我敢打赌这是对数组访问的边界检查。你做了很多。

如果你使用迭代器而不是直接访问，你就不会付出这种代价。不幸的是，目前我没有方便您使用迭代器的版本。也许其他人可以贡献一个。 :)