Chrono-probe

Chrono-probe 是一个用于测量算法时间复杂度的库。

为了测量算法的时间复杂度，你需要提供一个算法（或多个）以及为该算法生成输入的方法。然后库将测量算法在生成的不同长度的输入上的运行时间。这样，可以绘制算法随输入大小变化的耗时图。

库设计得尽可能灵活。只要算法可以表示为一个接收输入并返回输出的函数，就可以使用库来测量任何算法的时间复杂度。

如何使用chrono-probe

在本节中，我们将展示如何使用 chrono-probe 来测量排序算法的时间复杂度。我们将以 quicksort 算法为例。更多示例可以在 示例 文件夹中找到。

对于此示例，quicksort 算法的实现并不重要，定义可能如下所示

fn quick_sort<T: Ord + Clone>(v: &mut [T]) {
    // ...
}

第一步是定义一个表示算法输入的类型。在这种情况下，我们希望测量排序向量 u32 的时间复杂度，因此我们定义了一个新的类型，它是一个 u32 的向量。这是因为 Rust 不允许我们为在其他包中定义的类型实现特性，我们需要为我们的类型实现 Input 特性。

#[derive(Clone)]
pub struct InputVec(Vec<u32>);

我们还可以为 InputVec 实现 Deref 和 DerefMut，这样我们就可以将其用作 Vec<u32>。这不是必需的，但它使得使用更加方便。

impl Deref for InputVec {
    type Target = Vec<u32>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl DerefMut for InputVec {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

现在我们可以将 quicksort 算法定义为接收 InputVec 的函数。

fn quick_sort_measure(v: &mut InputVec) {
    quick_sort(v);
}

下一步是实现为input::Input为InputVec实现的特质。这个特质定义了如何为算法生成输入以及输入的大小。在这种情况下，我们不需要在多个输入生成器之间进行选择，因此不需要Builder。有关如何使用Builder的更多信息，请参阅input::Input特质的文档。

impl Input for InputVec {
    // We don't need a Builder.
    type Builder = ();

    // Return the size of the input, in this case the size is the length of the vector.
    fn get_size(&self) -> usize {
        self.len()
    }

    // Generate a vector of the given size and fill it with random numbers.
    fn generate_input(size: usize, _builder: &Self::Builder) -> Self {
        let mut rng = thread_rng();
        let mut v = Vec::with_capacity(size);
        for _ in 0..size {
            let rand: u32 = rng.gen();
            v.push(rand);
        }
        InputVec(v)
    }
}

现在我们已经实现了所有必要的特质，我们可以使用这个库来衡量算法。

在主函数中，我们为向量的长度创建一个分布。这里我们使用最小值为1000，最大值为500_000的线性分布。因此，所有向量的长度将在1000到500_000之间，并且长度将随机均匀选择。

let length_distribution = Linear::new(1000..=500_000);

下一步是为向量创建一个Builder。Builder用于生成向量，我们只需要指定向量的长度分布，因为我们不需要为InputVec创建Builder，所以我们可以使用()作为Builder。

let vector_builder = InputBuilder::new(length_distribution, ());

let mut vectors = vector_builder.build_with_repetitions(200, 10);

// Create a slice of the algorithms we want to measure
let algorithms: & [( fn ( & mut input::InputVec), & str); 1] = & [
(quick_sort_input, "Quick sort"),
];

// Measure the algorithms on the vectors, given a relative error of 0.001
let results = measure_mut( & mut vectors, algorithms, 0.001);

// Plot the results
let config = PlotConfig::default ()
.with_title("Sorting algorithms")
.with_caption("The time plot of sorting algorithms");

time_plot(file_name, results, & config);

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh