CS 245 Lab 10 – Performance Comparison
First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab.
Don’t forget to work in pairs! Where possible, please work with someone that you did not work with last week. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.
Synopsis
In this lab, you will compare the performance of two kinds of Lists: LinkedList and ArrayList. LinkedList has certain strengths over ArrayList, and vice versa.
Checkpoint 1
Person A types.
First, let’s time appending numbers to the two kinds of list. Both ArrayList and LinkedList satisfy a common interface, List, so we’ll write one set of routines that can be used for both list types.
First, write a static method named insertRandom that accepts a List<Integer>. It generates some large number of random ints and appends them to the list. (Make the number of numbers a static constant so that it’s easy to change.)
Second, write a static method named timedInsertRandom that accepts a List<Integer>. It starts a timer, repeatedly clears its list parameter and inserts a bunch of random integers into it, and stops a timer. We fill the list repeatedly so that the timing numbers are a little bit bigger and easier to reason about.
Accurate timing can be accomplished with some Java magic. System.currentTimeMillis measures what is called wall-clock time. If our program gets paused while Internet Explorer gets the CPU, System.currentTimeMillis will count the browser’s time against us. We want to measure strictly the list operations, so we use a different timing mechanism:
ThreadMXBean timer = ManagementFactory.getThreadMXBean();
long start = timer.getCurrentThreadCpuTime();
// repeatedly fill the list
long end = timer.getCurrentThreadCpuTime();
long nNanos = end - start;
(There are 10^9 nanoseconds in 1 second.)
Now, in your main method, call your timing method twice. Once with an ArrayList and once with a LinkedList. Try different values for the number of repetitions and insertions to get a feel for how the two lists stand up.
What do you see? Are your assumptions upheld or violated?
Try prepending instead of appending. (Find a List method that lets you prepend.)
Checkpoint 2
Person B types.
Now try timing something else. Choose one of the following operations, or some operation of your own devising:
- Inserting into the list, but keep it sorted after each insertion. Choose the insertion point as we did in lecture for the SortedList class.
- Creating a new List implementation that uses a backing String instead of an an array or linked nodes. For example, the list might hold “1,2,3” after the numbers 1, 2, and 3 have been added.
- Create lists of the two types with identical contents before starting the timer. Then iterate through them and sum up the numbers.