title: Java while loop dramatically slows down over time after a large number of iterations
body: <p>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?</p>
  
  <p>Here is the code snippet:</p>
  
  <pre><code>BufferedReader corpus = new BufferedReader(
              new InputStreamReader(
                          new FileInputStream("MyCorpus.txt"),"UTF8"));
  
  Writer outputFile = new BufferedWriter(new OutputStreamWriter(
              new FileOutputStream("output.txt"), "UTF-8"));
  
  List&lt;String&gt; words = new ArrayList();
  //words is being updated with relevant values here   
  
  LinkedHashMap&lt;String,Integer&gt; 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]) &amp;&amp; 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();
  </code></pre>