HW10: Timing Collections

Again, note that for this assignment you will work with data structures defined in the Java standard library, so there's no additional helper code to download. However, the interfaces are a little different from those we've worked with in class so far, so it'll be important to read the documentation. Here are the four structures you will use to simulate the set of valid strings:

The dictionary types mentioned above are of course designed to map keys to values. But really, we just care about the keys, and how long it takes to find a particular one. Thus you should set all the values in your dictionaries to null.

Hand in via Moodle:

1. A report describing the timing experiments you performed, your timing data, and your interpretation of what your results say about the relationship between $n$, $k$, choice of implementation / search algorithm, and running time. Your report should be a PDF file no longer than 5 pages including charts and graphs, if any.

   You don't need to look too deeply into why the particular structures give you the performance that you see, but you should try to determine, from your observations, what the asymptotic running-time complexity of a single lookup is in each of the four implementations, as well as the complexity of $k$ lookups in a row. (That is, you should conjecture about the “big O” of each of these operations, and provide arguments from the timing data in support of your conjectures.)

2. Source code you used to collect your timing data. Your source code should be well-commented and provide ample guidance to an outside user/reader about how it's structured.

   Your program, called with no arguments, must run the full suite of timing tests on which your report is based — every combination of $n$ and $k$ that you measured. (The only exception is this: if any tests take more than a minute, please include their invocations but comment them out, so that the grader can see how you got the data but doesn't have to wait for a long time for your program to run.) This means that your “test suite” should be hard-coded into the program, which is sort of contrary to the software design practice that you've learned in 111 and 201 so far. In an instance like this, though, it's okay.

   The only output of your program (when called with no command-line arguments) must be the timing-data summary; for each test, report the values of $n$ and $k$ and which structure you're testing, followed by the running time.

You will be graded on the depth of your investigation and the clarity of your writeup, along with the quality of your code.

• What we care about measuring in this assignment is search time, not the time that it takes to parse files or create our data structures or anything else like that. Do all your prep work up front (making both the valid-word set and a simple list of test words), and then time just a simple loop over the list of $k$ test words, looking each one up in the valid set. It is critical that you do not include any additional processing in the portion of the code that you time; don't modify your sets in any way, don't do any string parsing, and definitely don't print anything out.
• What do we mean by “enormous” for $n$? The maximum value of $n$ that you examine should be at least 500,000. To get you started, your source of unique valid words could be this list of 267,754 words in alphabetical order (or the same word list in random order).
• You may have noticed in the last point that the list of valid words contains about half as many words as you'll need to really max out $n$. You can make $n$ larger by duplicating each valid word by appending some nonsense string to the end of it. So, for example, your valid word set might include the words “AALS” and “ABAC”, and also the fake words “AALSAAAAA” and “ABACAAAAA”. Make sure that the sorted-list implementation is actually sorted when you include these fake words; it's not necessarily the case that you can just interleave them! Instead, use Java's Collections.sort() method. (Alternately, you could write out the duplicated word list to a separate file, and then use the Unix sort command to save a sorted copy. This will save you from doing repeated work in multiple experiments.)
• You'll need pretty big values of $k$ in order to see noticeable distinctions between the really fast implementations. If the performance seems comparable between them, try increasing $k$ (and maybe $n$). It's possible that you might need a $k$ as high as 250,000 or more. As a source of test words, you could use War and Peace or some other huge book you can download from Project Gutenberg. (To use this latter list, pick a title you like and then search for it on Project Gutenberg. Make sure to download the plain-text version of your chosen book!)
• You need to test many combinations of $n$ and $k$ values over a large range; above I just described maximum values, but you should also try timing down into the low thousands, or whatever puts your performance at close to half a second. To do this, you may take subsets of some really big input data (word list and book text), or, for the book text, you could just duplicate a shorter book as many times as you need. This is okay to do since the test words need not be unique.
• It really doesn't matter what the “valid” words are, nor, for that matter, what the test words are. So it's okay if, for a measurement with small $n$, all your valid words begin with A or B, for example.
• The syntax for declaring and initializing a data structure using the interfaces and implementations that Java provides is identical to that which you've been using all along with our “mystery” implementations. So, for example, here's how you make a new List with the ArrayList implementation:

  List<String> validWords = new ArrayList<String>();
  

  At the top of the file, you would also need to import these types:

  import java.util.List;
  import java.util.ArrayList;