You now have two implementations of MapSet: the BSTMap you used in Project 06 to count the words of Shakespeare and Reddit, and the HashMap you built in Lab 07. The text files are large enough that a list, or an otherwise inefficient implementation, would take a prohibitively long time to count them. In this project you measure how long each of your maps takes, both to build the word counts and to use them, and use what you know about the two structures to explain the differences.

Setup

Keep working in Projects/Project07, with your Lab 07 files. Finish Lab 07 first, including Tasks 6 and 7: java Lab07Tester should show every section passing.

Copy from your Projects/Project06 folder into Projects/Project07:

  • your BSTMap.java;
  • the two data files, CLEANED_shakespeare.txt and CLEANED_reddit_comments_2015.txt. If you no longer have them, download data.zip below and unzip it into Project07.

Do not copy your Project 06 WordCounter.java: this project comes with a new one.

Download now:

The programs you will run

Open a Terminal and cd into your Project07 folder, as in Lab 07. Every command on this page is typed there. Always compile first with javac *.java. Each time you need to run something, a blue Run it box shows what to type and what you should see.

CommandWhat it runsWhen
java WordCounter BST tiny.txt
java WordCounter HashMap tiny.txt
The timer: builds, looks up, and removes with one map on one text, 5 times, and prints the timesTasks 1 to 4
java Project07TesterThe project tester: checks the two methods you write in Task 2Task 2, and before you submit
java Lab07TesterThe lab tester: checks your HashMap againNow, and before you submit
Run it in Terminal, in your Project07 folder

Type:

$ javac *.java
$ java Lab07Tester

You should see: every section passes, and the summary at the end says Summary: 84 passed, 0 failed, 0 skipped. Your timings are only meaningful if your HashMap is correct.

If not: finish Lab 07 first: the first FAIL names the task to go back to.

Task 1 — Meet the new WordCounter READ

WordCounter creates and manages a MapSet<String, Integer> of word counts. It does the same counting as your Project 06 WordCounter, with four differences: you choose the map when you make it, buildMap times itself, it can report the map's maxDepth, and it has two timing methods that you write in Task 2. Everything else is provided.

MethodWhat it does
WordCounter(String dataStructure)constructor, where dataStructure is "BST" or "HashMap". It creates a BSTMap or a new HashMap() (16 bins, load factor 0.75) and stores it in the field wordCounts
readWords(filename)reads a text file and returns an ArrayList of all its words
buildMap(words)puts the words into the map, counting each one, and returns the time taken in milliseconds, measured with System.nanoTime()
timeLookups(words)you write it (Task 2): looks up every word with get, and returns the time in milliseconds
timeRemoveAll()you write it (Task 2): removes every key, and returns the time in milliseconds
clearMap()clears the map
totalWordCount()the number of words counted, repeats included
uniqueWordCount()the number of different words: the size of the map
getCount(word)how many times the word appears; 0 if it never does
getFrequency(word)the word's count divided by the total number of words; 0 if it never appears
maxDepth()the map's maxDepth: the number of levels for a BSTMap, the biggest bin for a HashMap
writeWordCount(filename)writes a word count file: the total number of words on the first line, then each word and its count
mainreads one text, then makes 5 runs with the map you choose. Each run builds the map, looks up every word, and removes every key, and prints the three times. At the end it prints the number of different words and the maxDepth after building

Read buildMap in WordCounter.java now: the two methods you write in Task 2 follow the same pattern. Then try WordCounter on tiny.txt, with each map. Your timing methods aren't written yet, so their columns show a dash.

Run it in Terminal, in your Project07 folder

Type:

$ javac *.java
$ java WordCounter BST tiny.txt
$ java WordCounter HashMap tiny.txt

You should see: five runs with a build time each, then 20 different words. The maxDepth is 6 for the BSTMap (the 6 levels you found in Lab 06) and 3 for the HashMap (what HashDemo showed in Lab 07).

Timing a BSTMap on the 60 words of tiny.txt, 5 times (all times in ms):
                build      lookups   remove all
  run 1:          0.6            -            -
  run 2:          0.1            -            -
  ...
20 different words.  maxDepth after building: 6
(- means not timed: timeLookups is not written yet (Task 2).)

If not: Stopped: … Finish Lab 07 first means a HashMap or BSTMap method is still missing. A different maxDepth means your maxDepth from Lab 06 or Lab 07 needs another look.

On a text this small the times are tiny and jumpy: a fraction of a millisecond. That is why Task 3 uses the big files.

Task 2 — Time using the map REUSE

buildMap times how long it takes to make the word counts. Once a map is built, a program uses it: it looks words up, and it may remove them. Write two methods in WordCounter.java that time those operations. Each one is built like buildMap: record the start time, do the work, and return the time since the start in milliseconds. Replace the placeholder throw line in each method with your code.

2a. timeLookups: look up every word

/**
 * Looks up every word in the list with the map's get, without changing the map.
 * Returns the time it took, in milliseconds, measured with System.nanoTime().
 */
public double timeLookups(ArrayList<String> words) {
    // TODO 1: record the start time, as buildMap does
    // TODO 2: for each word in the list, call get on the map with that word
    //         (only get: no put, so the map doesn't change)
    // TODO 3: return the time since the start, in milliseconds, as buildMap does
}

main calls timeLookups with the same list of words it built the map from: every word of the text, repeats included. So timeLookups calls get exactly as many times as buildMap does, but never put. You don't need to use the value get returns: the point is to time the lookups.

2b. timeRemoveAll: remove every key

/**
 * Removes every key from the map, one at a time, in the order of keySet, and sets
 * the total word count back to 0. Returns the time the removes took, in milliseconds.
 */
public double timeRemoveAll() {
    // TODO 1: get the list of keys with keySet (before starting the timer:
    //         we are timing remove, not keySet)
    // TODO 2: record the start time
    // TODO 3: for each key in that list, call remove on the map with that key
    // TODO 4: compute the time since the start, in milliseconds
    // TODO 5: set totalWords to 0: the map is empty now
    // TODO 6: return the time
}

timeRemoveAll removes each different word once: a word that appears 1,000 times is one key. keySet gives a new ArrayList, so removing keys from the map doesn't change the list you are looping over. When timeRemoveAll is done, the map is empty, like after clearMap, and main builds it again on the next run.

Run it in Terminal, in your Project07 folder

Type:

$ javac *.java
$ java Project07Tester

You should see: the Setup section and both Task 2 sections pass, and the summary says Summary: 35 passed, 0 failed, 0 skipped. While a method still has its throw line, its section says SKIP.

== Task 2: timeLookups ==
   Builds the map of tiny.txt, then calls your timeLookups with the same 60 words.
  [PASS] BSTMap: timeLookups calls get once for each of the 60 words
  [PASS] BSTMap: timeLookups never calls put: looking up doesn't change the map
  ...
  [PASS] timeLookups with 1,200,000 words: your time (23.5 ms) agrees with the tester's clock (23.5 ms)

If not: each FAIL says which call was wrong, and its hint says what to change. The tester watches which map methods your code calls, so a method that calls put, or calls keySet many times, is caught even when its times look fine.

Then: run WordCounter on tiny.txt again: the lookups and remove all columns now have times.

Ask Yourself — what are we timing?

  1. buildMap calls get and put for every word; timeLookups calls only get. Before you measure: should timeLookups take about half as long as buildMap, more, or less?
  2. Shakespeare has 365,342 words but 13,120 different words. Which of the three operations does each number describe?
  3. Why does TODO 1 call keySet before the start time? What would the remove times include otherwise?

Task 3 — Time the two maps READ AND EXPERIMENT

Run WordCounter four times: each map on each text. The Reddit file has about 15 million words, so its runs take a while: the BSTMap may take a minute for all 5 runs.

Run it in Terminal, in your Project07 folder

Type:

$ javac *.java
$ java WordCounter BST CLEANED_shakespeare.txt
$ java WordCounter HashMap CLEANED_shakespeare.txt
$ java WordCounter BST CLEANED_reddit_comments_2015.txt
$ java WordCounter HashMap CLEANED_reddit_comments_2015.txt

You should see: for each command, five runs with three times each, then the number of different words and the maxDepth. Your times will be different from these; the pattern should be similar.

Timing a HashMap on the 365,342 words of CLEANED_shakespeare.txt, 5 times (all times in ms):
                build      lookups   remove all
  run 1:         80.5         23.4          3.3
  run 2:         33.3         19.6          2.9
  run 3:         30.7         16.4          3.3
  run 4:         28.5         14.2          2.2
  run 5:         38.2         14.3          2.0
13,120 different words.  maxDepth after building: 5

If not: FileNotFoundException or Could not read means the data file isn't in your Project07 folder. java.lang.OutOfMemoryError means Java needs more memory: add -Xmx2g, for example java -Xmx2g WordCounter BST CLEANED_reddit_comments_2015.txt.

Record and summarize the times

Copy all five times of each run into three tables in your report, one for each operation (Google Docs tables, or a Google Sheet you paste from), in run order:

Table 1: build (buildMap)

TextMapRun 1Run 2Run 3Run 4Run 5Average of the middle 3 (ms)
ShakespeareBSTMap
ShakespeareHashMap
RedditBSTMap
RedditHashMap

Table 2: lookups (timeLookups)

TextMapRun 1Run 2Run 3Run 4Run 5Average of the middle 3 (ms)
ShakespeareBSTMap
ShakespeareHashMap
RedditBSTMap
RedditHashMap

Table 3: remove all (timeRemoveAll)

TextMapRun 1Run 2Run 3Run 4Run 5Average of the middle 3 (ms)
ShakespeareBSTMap
ShakespeareHashMap
RedditBSTMap
RedditHashMap

Task 4 — maxDepth CONNECT

Each WordCounter run also prints the map's maxDepth() after building it, before the removes. Record it for each map and each text in a fourth table:

TextDifferent wordsBSTMap maxDepthHashMap maxDepth
Shakespeare
Reddit

Remember what maxDepth means for each map: for the BSTMap it is the number of levels of the tree, the most nodes get may look at in a tree; for the HashMap it is the number of items in the biggest bin, the most nodes get may look at in a chain.

The testers: what each one checks

You have run both testers already. Run them both again before you submit:

Run it in Terminal, in your Project07 folder

Type:

$ javac *.java
$ java Lab07Tester
$ java Project07Tester

You should see: every section of both testers passes: Summary: 84 passed, 0 failed, 0 skipped. for Lab07Tester, and Summary: 35 passed, 0 failed, 0 skipped. for Project07Tester.

SectionWhat it checks
Lab07Tester, every sectionyour HashMap, as in Lab 07. Your BSTMap passed Lab06Tester and Project06Tester in Project 06
Project07Tester, Setupthe provided WordCounter counts tiny.txt with each of your maps: 60 words, 20 different, "times" twice
Project07Tester, Task 2: timeLookupswith each map: get once for each of the 60 words, never put or remove, the map and the total word count unchanged, a time of 0 or more; and with 1,200,000 words, a time in milliseconds that agrees with the tester's own clock
Project07Tester, Task 2: timeRemoveAllwith each map: keySet once, remove once for each of the 20 keys in keySet order, never put, an empty map and a total word count of 0, a time of 0 or more, and the map works again afterwards; your HashMap shrinks back to 16 bins

Report Format

Your intended audience is your peers who are not in this class but who have taken a computer science course. Your reader should be able to understand what you built, the important computer science ideas behind it, what experiments you performed, and what your results mean without having completed this assignment themselves.

Your project report should contain the following sections. Please include a header for each section. Tell us how to replicate your results: which commands you ran, and how you summarized the times.

Abstract

Briefly summarize the project in your own words. Identify both the core computer science ideas and the application: two implementations of the same map, a binary search tree and a hash table with separate chaining, used to count every word in two large texts, and then to look up and remove those words. Briefly identify the questions you investigated. Detailed results belong in the Results section.

Results

Answer the three required analyses below. For each, include your table, then explain it. Include your predictions, and say where they were right or wrong.

  1. Required analysis 1: time. Analyze the total time it takes for your different data structures in the buildMap method of your WordCounter class, in both datasets. Present your table of times, averaged over several runs as described in Task 3 (Table 1). Which map is faster, and by how much on each text? Point to JVM warm-up in your run 1 times: is it easy to see for Shakespeare? For Reddit? Why might it be easier to see in one than the other?
  2. Required analysis 2: maxDepth. Analyze the maxDepth() of your data structures after calling the buildMap method of your WordCounter class, in both datasets. Does this help to explain your results from analyses 1 and 3? Why or why not?
  3. Required analysis 3: using the map. Present your lookup and remove-all tables (Tables 2 and 3).
    • Lookups vs. building. buildMap calls get and put for every word; timeLookups calls only get. For each map, about what fraction of the build time is the lookup time? Is that what you predicted? Is one map's lookup advantage bigger than its build advantage?
    • Remove all. Removing every key is much faster than building or looking up. Use the number of words and the number of different words to explain why.
    • The two maps. Which map removes all its keys faster, and by how much? Your BSTMap removes its keys in alphabetical order, and your HashMap halves its table again and again as it empties. Does either fact help explain your result?

Data Structure Analysis

Answer the following questions, using big-O notation where appropriate.

  1. Give the average and worst-case running time of put and get for your BSTMap and for your HashMap, for n keys. What makes the worst case happen in each?
  2. Your HashMap keeps fC/4 ≤ n ≤ fC by doubling and halving its table. Why does every key have to be put again when the table changes size?
  3. buildMap calls get and then put for every word in the text. Use your answers above to explain how the total time of buildMap should grow with the number of words for each map.
  4. timeRemoveAll removes a BSTMap's keys in alphabetical order, so each key removed is the smallest key left in the tree. Which of remove's cases is that, and how much work does each remove do?
  5. As timeRemoveAll empties your HashMap, the table halves every time n drops below fC/4, and each halving puts every remaining key again. Starting from n keys, about how many puts do all the halvings do in total? Why is removing all n keys still O(n) overall?

Extensions

Describe any work you completed beyond the required project. Focus on the design and behavior of the extension: what capability you added, what classes or methods changed, how the new logic works, and how you determined that it worked. If you did not complete an extension, simply state that no extension was completed. Choose one or more of these, or propose your own. Make sure the required parts of your project still run, and put each major extension in its own folder.

Extensions for BSTs

  1. Write out your tree to a word count file in an order that will make it a balanced tree when you read it back in. Demonstrate that it works.
  2. Explore how badly unbalanced your BSTMap gets without self-balancing. First decide on a metric for what it means to be unbalanced. One reasonable choice is to calculate the balance factor of every node in the tree, and count the nodes whose balance factor is greater than 1 or less than -1.
  3. Implement a self-balancing tree, such as an AVL tree or a red-black tree, and demonstrate that it works properly.

Extensions for HashMaps

  1. Implement your own hash function. How does its performance compare to the built-in String hash function?
  2. Implement more than one way of handling collisions. For example, (1) use probing instead of chaining, or (2) use a BSTMap instead of a linked list in each bin. Compare the performance of the methods.
  3. Implement different probing methods, for example linear probing, quadratic probing, and double hashing. Compare the performance of the methods.

Extensions for the application

  1. Use an ArrayList or your own LinkedList instead of the BSTMap or HashMap to implement the map, and compare processing times.
  2. Use additional files to test the time and/or space efficiency of your implementations. Cover a much bigger range of sizes (in a logarithmic sense) so that you can draw an accurate curve. There are several datasets of Wikipedia pages available online that work well.

References/Acknowledgements

List the people and outside resources that contributed to your work. Include people you worked with or received help from, including TAs and instructors, and acknowledge outside references that helped you understand an algorithm, library, or programming technique.

Before You Submit

Project 07 is due on the date listed on the course's project page.

  • Your personal Google Drive Projects/Project07 folder contains your completed Project 07 work.
  • All of your .java files compile together.
  • You have run Lab07Tester and Project07Tester, and every section of both passes.
  • You have run WordCounter with both maps on both data files, and your report has all four tables: build, lookups, remove all, and maxDepth.
  • Your report is a Google Doc named Project07 Report in your Projects/Project07 folder.
  • Your report includes the Abstract, Results (Required analyses 1, 2, and 3), Data Structure Analysis, Extensions, and References/Acknowledgements sections.
  • You have deleted the data files from your Project07 folder.
  • Extensions must be submitted in separate folders inside your Project07 folder using the naming convention Extension1, Extension2, and so on. Each extension folder must contain ALL files necessary to compile and run that extension (except the data files); do not rely on files located elsewhere in your Project07 folder.
← Back to Lab 07