Java while loop dramatically slows down over time after a large number of iterations

Question

My program reads a text file line by line in a while loop. It then processes each line and extracts some information to be written in the output. Everything it does inside the while loop is O(1) except two ArrayList indexOf() method calls which I suppose are O(N). The program runs at a reasonable pace (1M lines per 100 seconds) in the beginning but over time it slows down dramatically. I have 70 M lines in the input file so the loop iterates 70 million times. In theory this should take about 2 hours but in practice it takes 13 hours. Where is the problem?

Here is the code snippet:

BufferedReader corpus = new BufferedReader(
            new InputStreamReader(
                        new FileInputStream("MyCorpus.txt"),"UTF8"));

Writer outputFile = new BufferedWriter(new OutputStreamWriter(
            new FileOutputStream("output.txt"), "UTF-8"));

List<String> words = new ArrayList();
//words is being updated with relevant values here   

LinkedHashMap<String,Integer> DIC = new LinkedHashMap();
//DIC is being updated with relevant key-value pairs here    

String line = ""; 
while ((line = corpus.readLine()) != null)
    String[] parts = line.split(" ");
    if (DIC.containsKey(parts[0]) && DIC.containsKey(parts[1])) {

        int firstIndexPlusOne = words.indexOf(parts[0])+ 1;
        int secondIndexPlusOne = words.indexOf(parts[1]) +1;

        outputFile.write(firstIndexPlusOne +" "+secondIndexPlusOne+" "+parts[2]+"\n");
        } else { 
            notFound++;
            outputFile.write("NULL\n");
        }
    }
outputFile.close();

Answer 1

I am assuming you add words to your words ArrayList as you go.

You correctly state that words.indexOf is O(N) and that is the cause of your issue. As N increases (you add words to the list) these operations take longer and longer.

To avoid this keep your list sorted and use binarySearch.

To keep it sorted use binarySearch on each word to work out where to insert it. This takes your complexity from O(n) to O(log(N)).