为什么排序需要这么长时间？

Question

我目前正在尝试通过解决一些小任务来学习 Rust 的语法。如果我以正确的方式使用语言，我会比较执行时间作为完整性检查。

一个任务是：

在运行ge 0 - 1000000000
排序并测量时间
打印排序时间

我得到了以下结果：

| #   | Language             | Speed  | LOCs |
| --- | -------------------- | ------ | ---- |
| 1   | C++ (with -O3)       | 1.36s  | 1    |
| 2   | Python (with PyPy)   | 3.14s  | 1    |
| 3   | Ruby                 | 5.04s  | 1    |
| 4   | Go                   | 6.17s  | 1    |
| 5   | C++                  | 7.95s  | 1    |
| 6   | Python (with Cython) | 11.51s | 1    |
| 7   | PHP                  | 36.28s | 1    |

现在我写了下面的 Rust 代码：

rust.rs

extern crate rand;
extern crate time;

use rand::Rng;
use time::PreciseTime;

fn main() {
    let n = 10000000;
    let mut array = Vec::new();

    let mut rng = rand::thread_rng();
    for _ in 0..n {
        //array[i] = rng.gen::<i32>();
        array.push(rng.gen::<i32>());
    }

    // Sort
    let start = PreciseTime::now();
    array.sort();
    let end = PreciseTime::now();

    println!("{} seconds for sorting {} integers.", start.to(end), n);
}

与以下 Cargo.toml:

[package]
name = "hello_world" # the name of the package
version = "0.0.1"    # the current version, obeying semver
authors = [ "you@example.com" ]
[[bin]]
name = "rust"
path = "rust.rs"
[dependencies]
rand = "*" # Or a specific version
time = "*"

我用 cargo run rust.rs 和运行二进制文件编译了它。它输出

PT18.207168155S seconds for sorting 10000000 integers.

请注意，这比 Python 慢得多。我想我做错了什么。（如果您有兴趣，rust 和其他语言的完整代码是 here。）

为什么用 Rust 排序需要这么长时间？我怎样才能让它更快？

Answer 1

我在我的电脑上试过你的代码，运行它与 cargo run 给出：

PT11.634640178S seconds for sorting 10000000 integers.

并且 cargo run --release（打开优化）给出：

PT1.004434739S seconds for sorting 10000000 integers.

为什么排序需要这么长时间？

Why does sorting take so long?

rust