lab 6 (Exam) Counting compares.
In this lab you will compare the efficiency of two
different solutions to the following problem. Given two text files called
file1 and file2, count how many of the words on file2 are contained in file1.
You will compare efficiency by counting how many times the compareTo() method or
the equals() method were invoked to compare words in each of the two solutions.
The MyString class:
You can count how many times compareTo() or equals() are
invoked by creating a specialized String class called MyString that implements
Comparable<MyString>. The MyString class will have a static int field
called count that will be incremented each time compareTo() or equals() is
invoked on a MyString object. It will also have a String field and a
constructor with a single String parameter. The other methods in the
MyString class follow.
The compareTo() method which increments count and returns the
int obtained by invoking the String compareTo() method.
The equals() method which also will increment the static
count field and then return the boolean by invoking the String equals() method.
The header for this method must be exactly
public boolean equals(Object other)
You will need to caste other to a MyString type before accessing its String
field.
The static method called reset() that sets the count field to
zero.
The static method getCount() that returns the current value
of the static count field.
To facilitate coding, the text files each have exactly one
word per line so there is no need for split().
The Algorithms:
There are of course many solutions to this problem. The
two solutions you will investigate are identical in every respect except one
uses an ArrayList data structure, the other a SortedArrayList data structure.
Your main() method will read each string from file1 into a MyString variable and
then add it to a list (either an ArrayList<MyString> or a SortedArrayList<MyString>).
Then in a loop read a word from the second file and use the contains() method to
determine if the word is in the list. Finally, your program will print out
how many words from file2 were in file1 and how many times compareTo() or
equals() were invoked on MyString objects. The SortedArrayList class that
I provide uses a fairly efficient contains() method, namely a binary search with
complexity log n, where n is the size of the list. So building a sorted
array list is slower than building a normal array list but finding something is
the sorted list is much faster. So there is the trade off. See which
appoach wins for the sample files provided.
I suggest you get your program working using an
ArrayList first. Then copy your code and change the ArrayList to a
SortedArrayList.
The repository for lab6 contains the two files and a
SortedArrayList generic class that you may use for this lab. Create a directory
called lab6 in your 223_wc subdirectory. Then copy of the files from
223_wc/teterwa/lab6 into your lab6.