A06

Due Date: Thursday, March 7
File(s) to be submitted: ListComparisons.java, A06Report.txt
Sample Output: SampleOutput.html
Starter Files:

• ListComparisons.java
• A06Report.txt

Comparing ArrayLists and LinkedLists (Preparing for Algorithmic Analysis)

Summary

There's very little programming for you to do this week. Most of your work is going to be thinking about what you see. This assignment is preparing you for when we start discussing algorithmic analysis.

The program I gave you tests two different tasks on ArrayLists versus on LinkedLists. On one task the ArrayList seems to be faster, and on the other the LinkedList appears to be faster.

You will be handing in a plain text document along with your revised program. The document you submit will contain answers to the questions in the document I provided you.

Details

Download the starter program and the report document. Open both in your IDE (if you're using one). Fill in your name and A-number in the spaces provided.

If you're not using an IDE, why not?

Use a text editor program to edit the document file, not a word processor! For example, Notepad on a Windows system, or textedit on a Macintosh.

After you submit your document, make sure it's plain text by using the View submissions tool to see what's saved on the pass-in computer. It should have exactly the same stuff in it as the file you see on your computer.

If it's got any kind of ŵεįŗđ $#|+ in it, then find a text editor and paste the text from your file into it—then fix anything that needs fixing.

Run the unmodified program. NOTE: it might take a few seconds for it to finish -- maybe even a minute or more. Don't stop it too soon.

If the elapsed time reported at the bottom of the program is more than ten seconds, then you should run it again. If it's still more than ten seconds, try turning off as many other programs running on your computer as you can. Keep trying until you either get the time consistently below ten seconds, or you can't find any other programs to turn off.

If you've turned off all the programs you can and your elapsed time is still over ten seconds, then you should go into the program and change two constants:

• Change MAX_N to 50000.
• Change MULT to 8.

Run your program using these new constant values. The tables printed will use the numbers 10, 80, 640, 5120 and 40960 instead of 10, 100, 1000, 10000, 100000. That's fine. Where I mention the powers of 10 later, just mentally substitute in the revised values.

If you need to make those changes, run the program again with these new sizes and copy the output into the space provided in the document.

If you didn't make those changes, don't put anything between the second set of lines.

Once you've got the program running OK, copy and paste the output (including the program introduction) into the space provided in the document. Don't start any of the remaining revisions until you've saved the result of an original run!

Run your program several more times, and compare the numbers you get with the numbers in your document. You'll probably notice that they change quite a bit from one run to the next. It's possible that, from time to time, one of the shorter lists will take longer than one of the longer lists! Weird! Some reasons for that include:

• Your computer is running other programs "in the background", and is sharing its attention between them. Any time one of your other programs takes up some of the computer's attention it slows down the Java program.
• Java is actually doing multiple things in the background, including something called "garbage collection" that slows it down. Those things are done as the Java virtual machine notices that they need doing, and so there's no good way to keep them from happening. Again, each time Java goes off to do something else, it slows down your program.

Anyway, this noise is one of the reasons we don't usually check how fast programs are in this way. There are better ways we'll learn about in the coming weeks.

Still, this exercise is not completely useless -- the times usually go up as the list lengthens. What we'll do to try to make the numbers a little better is run each test multiple times to "spread the noise around". Hopefully, the amount of noise will be spread pretty evenly around the various tests.

So, create a new constant called NUM_TESTS and set it to 10 or more. (The higher you set it, the better your numbers will be, but the longer it'll take for your program to finish. You probably don't want to go over 1000 -- a number that would keep my program running for over 15 minutes.)

Revise the method compareTimes so that it runs each list size NUM_TESTS times, adding up the times so that you can find the average amount of time it takes for each list length. The columns you get should be similar to (but not the same as) the columns from the original program. Some of them may be pretty different, but they should show more-or-less the same pattern of growth. The total time is going to go up by quite a bit, tho'.

Once you have the average times being calculated, revise the program again to add two more columns to the table:

• The ratio of the ArrayList time to the LinkedList time; and
• The ratio of the LinkedList time to the ArrayList time.

You'll need to revise the constants HEADER and RESULT to format the new header and result lines. You'll also need to revise the printf commands to include the new numbers you want printed.

The constants are format codes used by methods like printf and format, and the same or similar codes are used in other computer programming languages as well. If you took either of your first year programming courses from me, I encouraged you to learn how to use them. I'm encouraging you again. Nevertheless, some of you might not know:

• %10s means a String right-justified in a field 10 characters wide.
• %,15d means an integer value right-justified in a field 15 characters wide, using separators between the thousands groups. (In English we use a comma to separate the groups; French uses a dot (reserving the comma for separating the integer part from the decimal part in a non-integer number).)
• %n means a new-line character.

The ratio you need to print will not be an integer. The code for a number with a decimal is %f. You can specify how many digits you want after the decimal point by adding a decimal point and number after the field width. For example, a field 20 wide with 4 digits after the decimal, and commas between the thousands groups would be %,20.4f.

Make the columns for the ratios 8 characters wide with two decimal places.

Once you have the program working the way I said, copy its output into the space provided in the document. (in Part II).

Complete the document by adding or remving text as required to show your answers clearly.

• Do not modify the questions.
• Do modify the "answers" that are provided for you.
  • Anything in (parentheses) should be replaced either by new text or by one of the words/phrases in those parentheses.
  • The "______"s should be replaced by either "Array" or "Linked" (without the "quotes") as appropriate according to the data you got.
  • If there is no sample answer, then you need to compose an answer on your own.
  • In some cases, the answer will be N/A.