Project by Matheus and Katya.
- Create a program that takes in a file of words and sort them through Linked Lists.
- Create a new file with the sorted list.
- Take in arguments and return the words corresponding to argument.
- Make it clean and faster.
- Get a good grade from the project. (waiting for Chelu)
This is supposed to be done as soon as you read the word, it is identified where to be stored and put into the dict automatically. We approached it with coming up with a linked list of linked lists with different letters of the alphabet so that it would faster the program, since it would only compare with words of the same first letter. Therefore we create the linked lists, sort it, write the new file and talk to console. All with showing the time it took to take each method.
static String alphabet = "abcdefghijklmnopqrstuvwxyzé";
static String path = "C:\\Users\\Matheus\\IdeaProjects\\Linked-Dictionary\\src\\com\\company\\unsorteddict.txt";
static String path_sorted = "C:\\Users\\Matheus\\IdeaProjects\\Linked-Dictionary\\src\\com\\company\\sortedDictTest.txt";
static LinkedList<LinkedList> dict = new LinkedList<>();
static String[] toPrint = new String[99171];
public static void main(String args[])
{
long startingTime = System.currentTimeMillis();
createLinkedLists();
long elapsedTime = (System.currentTimeMillis() - startingTime);
System.out.println("Time to create Linked Lists: " + elapsedTime + "ms");
try {
startingTime = System.currentTimeMillis();
sortLinkedLists();
elapsedTime = (System.currentTimeMillis() - startingTime);
System.out.println("Time to sort Linked List: " + elapsedTime + "ms");
startingTime = System.currentTimeMillis();
writeNewFile();
elapsedTime = (System.currentTimeMillis() - startingTime);
System.out.println("Filled new file in: " + elapsedTime+ "ms");
talkToConsole();
}
catch (FileNotFoundException | UnsupportedEncodingException e) {
e.printStackTrace();
}
}Now we have 27 different linked lists for each starter letter in the alphabet.
In order to read the file we need to create an object File with the path of the file and a Scanner with the file as argument, after this using scan.nextLine() will return the word on the specific line.
public static void sortLinkedLists() throws FileNotFoundException {
File file = new File(path);
Scanner sc = new Scanner(file);
while (sc.hasNextLine()) {
String word = sc.nextLine().toLowerCase();
int indicator = alphabet.indexOf(word.charAt(0));
int position = getPosition(word, indicator);
if(position != -1) {
dict.get(indicator).add(position, word);
}
else {
dict.get(indicator).add(word);
}
}
sc.close();
}Since we could not use the sorting algorithm for the array we came up with our own known as getPosition(), this goes through the word and checks the first letter. After knowing the letter we need to send it to the correct linked list through our int Indicator, which is in int value the representation of which letter it starts. After that we check within the linked list and compare to all words that are smaller than the real word. If thelist is empty it will return -1 and be added randomly.
public static int getPosition(String word, int indicator) {
ListIterator list_Iter = dict.get(indicator).listIterator(0);
int result =0;
while(list_Iter.hasNext()){
String word_2 = list_Iter.next().toString();
if (word.compareTo(word_2) < 0){
return result;
}
result++;
}
return -1;
}To create a new file we will be using the PrintWriter class. This allows us to create a new file and iterate through the list adding one by one the sorted list into the new file. This is the method we came up with:
public static void writeNewFile() throws FileNotFoundException, UnsupportedEncodingException {
PrintWriter writer = new PrintWriter("sorteddict.txt","UTF-8");
int i =0;
for(LinkedList<String> element : dict){
for(String word: element){
toPrint[i] = word;
i++;
writer.println(word);
}
}
writer.close();
}We had to create a new array of Strings to substitute the list of lists or else it would be too slow to check for the correct word on the console requirement.
For the console to accept both number and words as arguments the following function was created:
public static void talkToConsole() throws FileNotFoundException {
Scanner scan = new Scanner(System.in);
boolean flag = true;
boolean number = true;
int argument;
while (flag){
String arg = scan.nextLine();
try{
argument = Integer.parseInt(arg);
switch(argument) {
case -1:
checkIfCorrect();
break;
default:
if(argument<-1){
System.out.println("That number is too tiny");
break;
}else if (argument > toPrint.length){
System.out.println("Number too big");
}else {
System.out.println(toPrint[argument]);
}
}
} catch (Exception e) {
switch(arg) {
case "test":
checkIfCorrect();
break;
case "":
System.out.println("This is not an input");
break;
case ":q":
Runtime.getRuntime().exit(0);
break;
default:
char add = arg.toLowerCase().charAt(0);
LinkedList list = dict.get(alphabet.indexOf(add));
if(list.contains(arg)){
System.out.println("This word is in the following position: " + getWord(arg));
}
else{
System.out.println("word doesn't exist, try again");
}
}
}
}
scan.close();
}
private static void checkIfCorrect() throws FileNotFoundException {
int errors = 0;
int i =0;
long startingTime = System.currentTimeMillis();
File sorted = new File(path_sorted);
Scanner access = new Scanner(sorted);
while(access.hasNextLine()){
if(access.nextLine() !=toPrint[i]){
errors++;
}
i++;
}
long elapsedTime = (System.currentTimeMillis() - startingTime);
System.out.println("Time to check the Linked List's accuracy: " + elapsedTime + "ms");
System.out.println("The sorted Arraylist is "+(errors/i*100)+"% accurate.");
access.close();
}
private static int getWord(String arg) {
for (int i = 0;i<toPrint.length;i++){
if (arg.toLowerCase().equals(toPrint[i].toLowerCase())){
return i;
}
}
return -1;
}
At first we were working with a single linked list with 99 thousand values that would be checked before adding the last values since this was so slow that we didn't even end the program once.
Secondly we managed to make the whole system faster by before the list starts to be populated we add all the letters from the alphabet so that it removes unecesary comparasions aout of the way. But the program was still slow at a whopping 38 mins to correctly sort all of the values. We thought that it was due to the structure of how the nodes store their value and the fact that each value records every single value before itself in the linked list. Therefore we came up with a way of reducing that.
This is the best method we were able to come up with which was to create a linked list to every single letter that a word starts with. therefore everytime a word is sorted it not only bypasses being compared to every other word that doenst start with the same letter but the size of the linked list becomes smaller allowing for faster storing of data.
By simply creating an iterator to locate the correct position for new words the program works extremely faster and is able to do the same as before in only 5 seconds.
Finally it was achieved with only 5 seconds.
| One Linked List | 60 mins+ |
|---|---|
| Linked list separated by alphabet | 38 mins |
| Linked list for each letter | 26 mins |
| Linked list for each letter + iterator | 5.5 seconds |
In order to make sure that the code is concise, understandable and scalable we have adopted 7 coding principles. Since our code from the beggining already complied with some of the coding principles, I will explain what we developed in each principle.
We from the beggining resorted to meaningful names for functions and variables, these include methods such as: createLinkedLists(), sortLinkedLists(), writeNewFile(), talkToConsole() and getPosition(). This made the code readible to anyone so that they know what the code is doing.
We made sure that every function in our program was only for one action. This is because if we would like to time it and optimize it would be done individually. This is why instead of having a funcion that would read the unsorted document and the one that would write and sort are completely different functions that are only called when needed.
We decided to use comments as a form of keeping out old code in the back of our head when writing the newer vesion. Therefore we would comment the previous results that were derived from that specific function. For instance: //1075ms;--- with list iterator = 180ms This gave us insights of how the method performed before and after, therefore insteade of using the comments for description, it would gives us other insights.
All of our methods are only called when its supposed to be and it closes itself when its job is done. Every single part of the process is trackable since they are compartamentalized into their own methods: createLinkedLists(), sortLinkedLists(), writeNewFile(), talkToConsole() and getPosition().
The function getPosition() shows this principle into action it will be called multiple times with each sorting. But since it is its own method it is called only when is needed and doesnt have to be repeated multiple times.
The simplicity of the code comes to the principle of how you can see the flow of the program. This is why we chose the main to be a caller whilst all of the functions are under it. For each function that the main calls, you can clearly see how it works by scrolling to the function.
As for YAGNI, the only time we had to scrap code was when using the List iterator, we had to change the variables used and the for loops that we were preciously using, they got replaced by better and faster code.