Compare large text File in java line by line

Question

Dear fellow developers I am doing a java program which compare two text files line by line, first text file has 99,000 lines and the other file has 1,15,000 lines. I want to read the files and compare in such a way so that if any line matches between the first file and the second file it should print the match.

I have written the code but it is taking almost 10 mins to complete, as it is printing due to the for loop. How can it be made fast, efficient and efficient in terms of memory allocation? How can it be optimized for performance? Please guide me.

public class Main {

static final String file1 = "file1.txt";
static final String file2 = "file2.txt";

static BufferedReader b1 = null;
static BufferedReader b2 = null;

static List<String> list_file1 = null;
static List<String> list_file2 = null;

public static void main(String[] args) {

    list_file1 = new ArrayList<String>();
    list_file2 = new ArrayList<String>();

    String lineText = null;

    try {
        b1 = new BufferedReader(new FileReader(file1));
        while ((lineText = b1.readLine()) != null) {
            list_file1.add(lineText);
        }
        b2 = new BufferedReader(new FileReader(file2));
        while ((lineText = b2.readLine()) != null) {
            list_file2.add(lineText);
        }
        compareFile(list_file1,list_file2);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }

}

private static void compareFile(List<String> list_file1, List<String> list_file2) {
    for(String content1:list_file1){
        for(String content2:list_file2){
            if(content1.equals(content2)){
                System.out.println("Match Found:-"+content1);
            }
        }
    }
}
}

Answer 1

Your program's time complexity is \$O(n*m)\$ and space complexity is \$O(n + m)\$ where 'n' is no. of lines in the first file and 'm' is no. of lines in second file.

Here is an optimised version of the above program, with time complexity \$O(n + m)\$ and space complexity \$O( min(m,n) )\$. I have not tested this program, but it should be able to present output on the screen within few seconds :)

import java.io.*;
import java.util.*;

class Main{
   public static void main(String args[]){
      try ( BufferedReader reader1 = new BufferedReader(new FileReader("file1.txt"));
            BufferedReader reader2 = new BufferedReader(new FileReader("file2.txt")) ){

            //assuming file1.txt is smaller than file2.txt in terms of no. of lines
            HashSet<String> file1 = new HashSet<String>();

            String s = null;
            while( ( s = reader1.readLine()) != null){
               file1.add(s);
            }

            while( (s = reader2.readLine()) != null ){
               if(file1.contains(s))
                  System.out.println(s);
            }
      }
      catch(IOException e){
         System.out.println(e);
      }

   }
}

Note: Only one file is in memory at a time and HashSet<> instead of nested loops for comparison.