CS 261 Lab C - Benchmarking Lists

Due Wed Feb 05 at 9:00am

Overview

As an introduction to our discussion of data structure efficiency, in this lab you will write Java code to test the speed differences between distinct implementations of the List interface. In particular, you will be testing the following operations on three different implementations of List:

  1. Adding items at the end of the list
  2. Adding items at the beginning of the list
  3. Traversing the list using the get() method
  4. Traversing the list using an Iterator
  5. Accessing arbitrary items in the list
  6. Removing items from the front of the list
  7. Removing arbitrary items from the list

This lab will be completed in pairs. Review the pair programming guidelines if you don't remember them!

Objectives

Necessary Files

You will need to download the copy of the zipped source files. and import them into Eclipse (see below for specific instructions). These files include the class files for three different list implementations--you will consider them as 'black boxes' (where you can't look at the code itself, only how it runs!). Also included is the outline for the ListTester class you will fill in to get you started.

Details

  1. You'll need to jump through a few hoops in order to import the List class files into Eclipse. I'll walk you through it below:
    • Create a new project in Eclipse, and import the ListTester.java file into the src folder.
    • Next you'll need to set up a folder containing the SecretList class files necessary for this project. In the Package Explorer view, right-click your Lab C project and select New > Folder. In the New Folder dialog box enter a name (e.g., "lib") and hit Finish.
    • Now right-click your newly created folder in the Package Explorer view and select Import. Under the General folder select File System and click Next. You'll need to select the folder that contains the class files, and select them (with check marks) to import. Your project should look something like this:
    • Now we need to tell Eclipse where to find these class files. Right-click your Lab C project and select Properties. Select Java Build Path and then select the Libraries tab. On the right-hand side, select Add Class Folder, and then select the folder that contains the SecretList class files. Click OK, and your Properties window should look something like this: Note that this is about how you load external .jar files, such as if you want to use a third-party library.
    • Hit OK on the Properties window to save your changes. You should now have an additional Referenced Libraries option in your Package Explorer that has the lib folder inside it
  2. Now the SecretListTester class you imported should run. Try running the class and selecting the Add to End of List test. Try testing adding 10,000 items. Because Java code can run at different speeds depending on what else your computer is doing (and depending on whether Java's "just-in-time" optimization, called the "hotspot", has kicked in), it's a good idea to run each test multiple times. Try including 500 or 1000 repetitions (this is why we use computers for this stuff)!
  3. Take a few minutes to inspect the code--ask if there are any pieces you don't understand! Note the basic form of a test:
    • initialize the list
    • declare the timer variables and get test size from user
    • print the introduction
    • start the timer (System.out.currentTimeMillis() gets the current time in milliseconds; we basically mark the start and stop of the timer to determine time elapsed).
    • run the tests
    • stop the timer and print the results
  4. After you're familiar with the code, your task is to add the remaining test methods. Note that you can use the give code as a template--copy/paste will be your friend (but be careful to adjust output text and variables!). Some notes on the tests to add:
    • Adding items at the beginning of the list: You should perform this test using the List interfaces add(int,E) method to always add an item at the front of the list (to index 0);
    • Traversing the list using the get() method: When you initialize the list, you will need to fill it with the specified number of elements (remember not to include this initialization in your timer!) You should traverse the list using a for loop (not a foreach loop!), and then accessing every item with get(i) and assigning it to a local variable. Your basic code should look like: for(int i=0; i<n; i++) {String s = list.get(i);}
    • Traversing the list using an Iterator: This will work just like the previous test, but will use a foreach loop to force an Iterator. ALternatively, you can instantiate the iterator directly and use a while loop if you'd like the practice!
    • Accessing arbitrary items in the list: This test will be like traversing with the get() method, but instead of going in order you'll be getting a random item from the list.
    • Removing items from the front of the list: For this test you'll need to initialize the list and fill it with a number of elements. Then remove the the first item over and over using the List's .remove(int) method
    • Removing arbitrary items from the list: This test will work like the previous, but you'll need to remove an item at a random index. Note that every time you remove an item the size of the list will change, so you'll want to use the current size of the list as a parameter for picking the random index.
  5. Hint: it might preserve your sanity to hard-code in the size of the lists and the number of tests, commenting out the JOptionPane request to the user. But you make sure the JOptionPanes are in your final code.
  6. Be careful not to include any print() statements in your tests--printing is slow and will throw off your benchmarks!
  7. After you finish writing your tests, run each one on the lists with two different sizes: 100,000 elements and 1,000,000 elements. Document your results by writing them down in a table in Word or Excel. Also write a few observations from your results: what do you notice about the differences in speeds (if any)? These observations will be turned in along with your documentation.
  8. Check and double-check that your program works flawlessly before submitting it to the submission folder. Also be sure that your names are on the top of the file!
  9. Fill out the lab partner evaluation survey after you turn in your work!

Submitting

Submit the following files to the LabC submission folder on hedwig: SecretListTesterGUI.java, and the document containing your results and observations (e.g., Results.docx). Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

Remember to fill out your lab partner evaluation!

Extensions

For a good time, try testing the speeds of sorting each individual list!

Grading

This assignment will be graded based on approximately the following criteria: