YCP Logo Lab 10: Benchmarking ArrayList

Due: Thursday, Oct 16th by 11:59 PM

Getting Started

Download CS201_Lab10.zip. Import it into Eclipse (File->Import...->Existing Projects into Workspace->Archive File.) You should see a project called CS201_Lab10 in the package explorer.

Your Task

Your task is to benchmark removing all elements from an ArrayList using two techniques:

  1. Repeatedly remove the last element
  2. Repeatedly remove the first element

Test both of these techniques on a series of ArrayLists containing increasing numbers of elements. Start at 10,000 elements, and increase by 10,000 elements up to 100,000 elements.

You can use the following method to create ArrayList objects with a specified number of elements:

public static ArrayList<Integer> create(int count) {
        ArrayList<Integer> a = new ArrayList<Integer>(count);
        for (int i = 0; i < count; i++) {
                a.add((Integer) 42);
        }
        return a;
}

You can measure the number of milliseconds required to execute a block of code as follows:

// force a garbage collection
System.gc();

long start = System.currentTimeMillis();

// ...code that you want to benchmark...

long end = System.currentTimeMillis();

long elapsed = end - start;

Important: run your benchmark on the ArrayList class included in the lab, not the built-in java.util.ArrayList class.

Output and Analysis

The output of the program should be a series of lines of comma-separated values:

  • The first value is the number of elements in the ArrayList
  • The second value is the number of milliseconds required to remove all elements by repeatedly removing the last element
  • The third value is the number of milliseconds required to remove all elements by repeatedly removing the first element

Your output should look something like this:

10000,10,294
20000,12,847
30000,0,4790
40000,0,7964
50000,0,12387
60000,1,15229
70000,0,19757
80000,0,28004
90000,2,42463
100000,0,48351

Once you have collected your benchmark data, import it into Excel (you should be able to simply select the output of your program, copy it to the clipboard, and paste it into Excel). Plot the data (second and third columns), using the first column as the X-axis. Your plot should look something like this:

figures/lab10-benchPlot.png

Copy your Excel file into the Eclipse project. (Put it in the subdirectory of your Eclipse workspace called CS201_Lab10, and in Eclipse right-click on the project and choose Refresh.)

Submit

Make sure that you have included your Excel file in the project!

When you are done, save the project (CS201_Lab10) to a zip file by right-clicking it and choosing

Export...->Archive File

Upload the saved zip file to the Marmoset server as lab10. The server URL is

https://camel.ycp.edu:8443/