Background

You are to explore the impact of selecting various data structures on the execution time of various operations. You will need to write very little code. Instead, the focus of this assignment is on the analysis of the benchmarking results. The benchmarking work done here is often referred to as micro-benchmarking. Generally speaking, this isn't a great approach, but, this is week 1.

Setup Procedure

First, create an IntelliJ project and add the following files to the project:

• Driver (download) – Main program
• Benchmarker (download) – Used to benchmark operations
• SortedArrayList (download) – Additional collection class that is not part of the Java Collections Framework

No other files are needed.

Assignment

Containers

You must compare the following containers: ArrayList<Integer>, SortedArrayList<Integer> (see above), and LinkedList<Integer>. All of these containers implement the List<Integer> interface.

Operations

You must compare the time it takes to complete the following operations on each container type:

• Add N (random valued) positive integers to an empty container (add to back).
• Add N (random valued) positive integers to an empty container where each new item is added to the front.
• Determine whether a given integer value is in a container of size N.
• Access the i^th element of a container of size N where i is between 0 and N.
• Access the (N/2)^th element of a container of size N.

Size of NMAX and NINC

You should run all (see exception below) of the tests setting NMAX to at least 100,000 and NINC to something in the hundreds range. The values for NMAX and NINC should be chosen so that you are able to accurately predict the growth rate of the operations under examination. You may find that you'll need to reduce the 100,000 NMAX size for one of the three containers in order to get results in a timely manner.

Procedure

You must run all of the tests for a number of values of N. The version of the Driver class available for download just runs test for the ArrayList class. You will need to modify the Driver class in order to test the other collections and vary the value of N. Pick a sufficient range of values for N so that you are able to accurately predict the growth rate of the operations being tested.

Please note that SortedArrayList class does not support adding elements to the front of the collection, so you'll need to modify the Driver class to skip that test when working with the SortedArrayList.

Lab Deliverables

Report

Submit your assignment as specified by your instructor. At a minimum, your report must contain:

• Results: You should include at least one plot for each method being analyzed (for a total of 14 plots).
• A discussion of:
• The parameters for each test (size, number of runs, etc.)
• Your results... any surprises? Be sure to point out and attempt to explain anything unusual/unexpected in the plots.
• Analysis and conclusions based on your results. Did you gather enough data to support your conclusions?