5.1: Performance profiling results

Last updated
Save as PDF

Page ID: 12750

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In the previous exercise, we used Profiler.java to run various ArrayList and LinkedList operations with a range of problem sizes. We plotted run time versus problem size on a log-log scale and estimated the slope of the resulting curve, which indicates the leading exponent of the relationship between run time and problem size.

For example, when we used the add method to add elements to the end of an ArrayList, we found that the total time to perform n adds was proportional to n; that is, the estimated slope was close to 1. We concluded that performing n adds is in \( O(n) \), so on average the time for a single add is constant time, or \( O(1) \), which is what we expect based on algorithm analysis.

The exercise asks you to fill in the body of profileArrayListAddBeginning, which tests the performance of adding new elements at the beginning of an ArrayList. Based on our analysis, we expect each add to be linear, because it has to shift the other elements to the right; so we expect n adds to be quadratic.

Here’s a solution, which you can find in the solution directory of the repository.

public static void profileArrayListAddBeginning() {
    Timeable timeable = new Timeable() {
        List<String> list;
        
        public void setup(int n) {
            list = new ArrayList<String>();
        }
        
        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add(0, "a string");
            }
        }
    };
    int startN = 4000;
    int endMillis = 10000;
    runProfiler("ArrayList add beginning", timeable, startN, endMillis);
}

This method is almost identical to profileArrayListAddEnd. The only difference is in timeMe, which uses the two-parameter version of add to put the new element at index 0. Also, we increased endMillis to get one additional data point.

Here are the timing results (problem size on the left, run time in milliseconds on the right):

4000, 14
8000, 35
16000, 150
32000, 604
64000, 2518
128000, 11555

Figure \(\PageIndex{1}\) shows the graph of run time versus problem size.

Profiling results: run time versus problem size for adding n elements at the beginning of an ArrayList.

Figure \(\PageIndex{1}\): Profiling results: run time versus problem size for adding n elements at the beginning of an ArrayList.

Remember that a straight line on this graph does not mean that the algorithm is linear. Rather, if the run time is proportional to \( n^k \) for any exponent, k, we expect to see a straight line with slope k. In this case, we expect the total time for n adds to be proportional to \( n^2 \), so we expect a straight line with slope 2. In fact, the estimated slope is 1.992, which is so close I would be afraid to fake data this good.