1
\$\begingroup\$

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);
            }
        }
    }
}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "it is taking almost 10 mins to complete as it is printing due to for loop." printing to console is a quite expensive operation. How long does it take if you redirect the console output to a file like this: java [your.class] > output.txt? \$\endgroup\$ – Timothy Truckle Feb 14 '18 at 11:44
  • \$\begingroup\$ 1,15,000 lines shouldn't there be three digits in every group ticked off? \$\endgroup\$ – greybeard Feb 15 '18 at 21:44
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You should use try-with-resources or properly close your Readers. \$\endgroup\$ – RobAu Feb 14 '18 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.