Question

Please change the first algorithm (the one with linked lists) so it runs faster using the List.Iterator() function. The program uses 2 algorithms one is linked lists and the other is arrays. Just need to change the linked list algorithm so that it runs faster, to do that it needs to use list.iterator function instead of get(i). I have highlighted the area that needs to be changed, rest should be fine. The function of the program is to read a text file and see which word is the most frequent and return the time it took to do it using both arrays and linked list algorithms.

import java.io.File;
import java.util.Scanner;
import java.util.Map.Entry;
import java.util.AbstractMap;
import java.util.LinkedList;

public class WordCountLinkedList254 {
  
   public static Entry count_ARRAY(String[] tokens) {
       int CAPACITY = 10000;
       String[] words = new String[CAPACITY];
       int[] counts = new int[CAPACITY];
       for (int j = 0; j < tokens.length; j++) {
           String token = tokens[j];
           for (int i = 0; i < CAPACITY; i++) {
               if (words[i] == null) {
                   words[i] = token;
                   counts[i] = 1;
                   break;
               } else if (words[i].equals(token))
                   counts[i] = counts[i] + 1;
           }
       }

       int maxCount = 0;
       String maxWord = "";
       for (int i = 0; i < CAPACITY & words[i] != null; i++) {
           if (counts[i] > maxCount) {
               maxWord = words[i];
               maxCount = counts[i];
           }
       }
       return new AbstractMap.SimpleEntry(maxWord, maxCount);
   }

   public static Entry count_LINKED_LIST(String[] tokens) {
       LinkedList> list = new LinkedList>();
       for (int j = 0; j < tokens.length; j++) {
           String word = tokens[j];
           boolean found = false;
          
           for (int i = 0; i < list.size(); i++) {
               Entry e = list.get(i);

               if (word.equals(e.getKey())) {
                   e.setValue(e.getValue() + 1);
                   list.set(i, e);
                   found = true;
                   break;
               }
           }
          
           if (!found)
               list.add(new AbstractMap.SimpleEntry(word, 1));
       }

       int maxCount = 0;
       String maxWord = "";
       for (int i = 0; i < list.size(); i++) {
           int count = list.get(i).getValue();
           if (count > maxCount) {
               maxWord = list.get(i).getKey();
               maxCount = count;
           }
       }
       return new AbstractMap.SimpleEntry(maxWord, maxCount);
   }

   static String[] readText(String PATH) throws Exception {
       Scanner doc = new Scanner(new File(PATH)).useDelimiter("[^a-zA-Z]+");
       int length = 0;
       while (doc.hasNext()) {
           doc.next();
           length++;
       }

       String[] tokens = new String[length];
       Scanner s = new Scanner(new File(PATH)).useDelimiter("[^a-zA-Z]+");
       length = 0;
       while (s.hasNext()) {
           tokens[length] = s.next().toLowerCase();
           length++;
       }
       doc.close();

       return tokens;
   }
  
   public static void main(String[] args) throws Exception {
      
       String PATH = "dblp200.txt";
       String[] tokens = readText(PATH);
       long startTime = System.currentTimeMillis();
       Entry entry = count_LINKED_LIST(tokens);
       long endTime = System.currentTimeMillis();
       String time = String.format("%12d", endTime - startTime);
       System.out.println("time\t" + time + "\t" + entry.getKey() + ":" + entry.getValue());
      
       tokens = readText(PATH);
       startTime = System.currentTimeMillis();
       entry = count_ARRAY(tokens);
       endTime = System.currentTimeMillis();
       time = String.format("%12d", endTime - startTime);
       System.out.println("time\t" + time + "\t" + entry.getKey() + ":" + entry.getValue());
   }
}

Answer 1

Here is the completed code for this problem, updated as you requested. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// WordCountLinkedList254.java

import java.io.File;

import java.util.Iterator;

import java.util.Scanner;

import java.util.Map.Entry;

import java.util.AbstractMap;

import java.util.LinkedList;

public class WordCountLinkedList254 {

      public static Entry count_ARRAY(String[] tokens) {

            int CAPACITY = 10000;

            String[] words = new String[CAPACITY];

            int[] counts = new int[CAPACITY];

            for (int j = 0; j < tokens.length; j++) {

                  String token = tokens[j];

                  for (int i = 0; i < CAPACITY; i++) {

                        if (words[i] == null) {

                              words[i] = token;

                              counts[i] = 1;

                              break;

                        } else if (words[i].equals(token))

                              counts[i] = counts[i] + 1;

                  }

            }

            int maxCount = 0;

            String maxWord = "";

            for (int i = 0; i < CAPACITY & words[i] != null; i++) {

                  if (counts[i] > maxCount) {

                        maxWord = words[i];

                        maxCount = counts[i];

                  }

            }

            return new AbstractMap.SimpleEntry(maxWord, maxCount);

      }

      public static Entry count_LINKED_LIST(String[] tokens) {

            LinkedList<Entry<String, Integer>> list = new LinkedList();

            for (int j = 0; j < tokens.length; j++) {

                  String word = tokens[j];

                  boolean found = false;

                  //creating an iterator from the list

                  Iterator<Entry<String, Integer>> iterator = list.iterator();

                  //looping as long as there is an element to iterate

                  while (iterator.hasNext()) {

                        //getting next entry

                        Entry<String, Integer> e = iterator.next();

                        //checking if word is same as key of e

                        if (word.equals(e.getKey())) {

                              //updating count by 1

                              e.setValue(e.getValue() + 1);

                              found = true;

                              break;

                        }

                  }

                  //old code

                  /*for (int i = 0; i < list.size(); i++) {

                     Entry<String, Integer> e = list.get(i);

                     if (word.equals(e.getKey())) {

                         e.setValue(e.getValue() + 1);

                         list.set(i, e);

                         found = true;

                         break;

                     }

                 }*/

                  if (!found)

                        list.add(new AbstractMap.SimpleEntry(word, 1));

            }

            int maxCount = 0;

            String maxWord = "";

            for (int i = 0; i < list.size(); i++) {

                  int count = list.get(i).getValue();

                  if (count > maxCount) {

                        maxWord = list.get(i).getKey();

                        maxCount = count;

                  }

            }

            return new AbstractMap.SimpleEntry(maxWord, maxCount);

      }

      static String[] readText(String PATH) throws Exception {

            Scanner doc = new Scanner(new File(PATH)).useDelimiter("[^a-zA-Z]+");

            int length = 0;

            while (doc.hasNext()) {

                  doc.next();

                  length++;

            }

            String[] tokens = new String[length];

            Scanner s = new Scanner(new File(PATH)).useDelimiter("[^a-zA-Z]+");

            length = 0;

            while (s.hasNext()) {

                  tokens[length] = s.next().toLowerCase();

                  length++;

            }

            doc.close();

            return tokens;

      }

      public static void main(String[] args) throws Exception {

            String PATH = "dblp200.txt";

            String[] tokens = readText(PATH);

            long startTime = System.currentTimeMillis();

            Entry entry = count_LINKED_LIST(tokens);

            long endTime = System.currentTimeMillis();

            String time = String.format("%12d", endTime - startTime);

            System.out.println("time\t" + time + "\t" + entry.getKey() + ":"

                        + entry.getValue());

            tokens = readText(PATH);

            startTime = System.currentTimeMillis();

            entry = count_ARRAY(tokens);

            endTime = System.currentTimeMillis();

            time = String.format("%12d", endTime - startTime);

            System.out.println("time\t" + time + "\t" + entry.getKey() + ":"

                        + entry.getValue());

      }

}