1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//! # Chrono-probe
//!
//! **Chrono-probe** is a library for measuring the time complexity of algorithms.
//!
//! In order to measure the time complexity of an algorithm, you need to provide an algorithm (or
//! more) and a way to generate inputs for the algorithm. The library will then measure the time
//! it takes for the algorithm to run on the generated inputs of various lengths. In this way, it
//! is possible to obtain a plot of the time taken by the algorithm as a function of the input size.
//!
//! The library is designed to be as flexible as possible. It is possible to use the library to
//! measure the time complexity of any algorithm, as long as the algorithm can be expressed as a
//! function that takes an input and returns an output.
//!
//! ## How to use chrono-probe
//!
//! In this section, we will show how to use **chrono-probe** to measure the time complexity
//! of a sorting algorithm. We will use the `quicksort` algorithm as an example. This example and
//! more can be found in the [examples](https://github.com/ADS-laboratory/chrono-probe/tree/lib/examples) folder.
//!
//! The implementation of the quicksort algorithm is not important for this example, the definition
//! would look something like this:
//! ```ignore
//! fn quick_sort<T: Ord + Clone>(v: &mut [T]) {
//! // ...
//! }
//! ```
//!
//! The first step is to define a type that represents the input to the algorithm. In this case we
//! want to measure the time complexity of sorting vectors of u32, so we define a new type that is
//! a vector of u32. This is done because rust does not allow us to implement traits for types
//! defined in other crates and we need to implement the [Input]() trait for our type.
//!
//! ```ignore
//! #[derive(Clone)]
//! pub struct InputVec(Vec<u32>);
//! ```
//!
//! We can also implement `Deref` and `DerefMut` for InputVec, so that we can use it as a `Vec<u32>`.
//! This is not necessary, but it makes it easier to use.
//!
//! ```ignore
//! 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
//! }
//! }
//! ```
//!
//! Now we can define the quicksort algorithm as a function that takes an InputVec.
//! ```ignore
//! fn quick_sort_measure(v: &mut InputVec) {
//! quick_sort(v);
//! }
//! ```
//!
//! The next step is to implement the [input::Input] trait for `InputVec`. This trait defines how to generate
//! inputs for the algorithm and what the size of the input is. In this case we don't need to choose
//! between different input generators, so we don't need a Builder, for more information on how to
//! use Builders see the documentation for the [input::Input] trait.
//!
//! ```ignore
//! 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)
//! }
//! }
//! ```
//!
//! Now we implemented all the necessary traits and we can use the library to measure the algorithm.
//!
//!
//! In the main function we create a distribution for the length of the vectors. Here we use a linear
//! distribution with a minimum of 1000 and a maximum of 500_000. So all the vectors will have a
//! length between 1000 and 500_000 and the length will be chosen uniformly at random.
//!
//! ```ignore
//! let length_distribution = Linear::new(1000..=500_000);
//! ```
//!
//! The next step is to create a builder for the vectors. The builder is used to generate the
//! vectors, we only need to specify the distribution for the length of the vectors and because
//! we don't need a Builder for the InputVec, we can use `()` as the Builder.
//!
//! ```ignore
//! let vector_builder = InputBuilder::new(length_distribution, ());
//! ```
//!
//! Now we can build the vectors. Here we build 200 vectors, 10 of each length.
//!
//! ```ignore
//! let mut vectors = vector_builder.build_with_repetitions(200, 10);
//! ```
//!
//! Finally we can measure the algorithm. We need to specify the algorithm, the input and the
//! relative error. The relative error is used to determine how many times the algorithm should be
//! run for each input size. The algorithm will be run until the relative error is less than the
//! given relative error. We use the [`measurements::measure_mut`] function because the algorithm takes a mutable
//! reference to the input.
//!
//! ```ignore
//! // 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);
//! ```
//!
//! The results are returned as a vector of [`measurements::Measurement`]s. Each measurement contains the size of
//! the input, the time it took for the algorithm to run and the relative error of the measurement.
//!
//!
//! Results can be plotted using the [`plot::time_plot`] function.
//!
//! ```ignore
//! // 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);
//! ```
//!
//! The entire code and other examples can be found in the [examples](https://github.com/ADS-laboratory/chrono-probe/tree/lib/examples) folder.