Computers are machines. While they might be fast, and get faster all the time, they are still only able to do a limited amount of work over a given period of time. In this lab we're going to learn the speed of various operations of ArrayList.
With these exercises you should start out with small numbers (in the tens of thousands) and then gradually increase to larger numbers (in the hundreds of thousands). Larger numbers will tend to cause Java to run out of memory, but we will often want to use the largest numbers we can achieve.
Write an ordinary Java class with a couple of data fields and a constructor (or borrow a Java class from a previous Comp132 lab)
Write a Java driver program to measure the time to add a large number of items
Make one instance of your Java class from the previous step
Make an ArrayList
Use a counted for loop to add the same item to the ArrayList some large number of times (tens of thousands or hundreds of thousands). Remember to use a named constant for the maximum value
static final int MAX_ITEMS = 50000;
Add a println at the start of the loop and again after the loop has completed. This will allow you to measure how long the program takes.
Try running the program with various gradually increasing values. Can you find a large value that is measurable via a stopwatch? (Note: there are timing facilities available in the Java libraries but we won't be using them. We want to do this from a user response time perspective)
Set the number of items back to something on the small side. Add another counted loop to remove all the items that were just added. ArrayList has a remove operation that removes by position. Try removing the zero-position element each time. As with the adding exercise, try using increasing the maximum values. Is the amount of time substantially different than adding? Record enough values that you can draw a graph which compares the number of items versus the amount of time to remove them.
Change your counted loop to remove items from the end of the list, rather than from the zero position. Hint: use the same counted for loop, but add a variable that will keep track of the position you want to remove. Alternate hint: always remove the size - 1 position (this isn't as efficient). How fast is removing from the end compared to removing from the beginning?
Write a different driver program to measure how often the equals method is called when ArrayList's indexOf operation is used.
This time, add different items to your ArrayList (rather than the same item many times). Hint: You can make your items different by concatenating the loop control variable to and Strings you're using when making your class. Note that since you're using more memory by creating unique items, you won't be able to create and add as many items as you did in the previous exercise.
Add an equals method to your class
Add a counter variable to your class that will increment each time the equals method is called.
Add a static getter method to return the equals counter (so you can call it from main with ClassName.getEqualsCounter()
In your main program, after the list has been filled, use Collections.shuffle on the list to randomize it.
Use ArrayList's indexOf to search for a newly created "fake" item that is similar to the one you're trying to find on the list
Print the position of the found item on the list, along with the number of times that equals was called.
Try finding different items on the list. What is the general rule/formula for the expected number of equals calls that will be required to find a random item on the list?