CODEWITHSUNDEEP
java
fanbondi
fanbondi

Reputation: 1047

Reading and matching contents of two big files

I have two files each having the same format with approximately 100,000 lines. For each line in file one I am extracting the second component or column and if I find a match in the second column of second file, I extract their third components and combine them, store or output it.

Though my implementation works but the programs runs extremely slow, it takes more than an hour to iterate over the files, compare and output all the results.

I am reading and storing the data of both files in ArrayList then iterate over those list and do the comparison. Below is my code, is there any performance related glitch or its just normal for such an operation.

Note : I was using String.split() but I understand form other post that StringTokenizer is faster. 

public ArrayList<String> match(String file1, String file2) throws IOException{
        ArrayList<String> finalOut = new ArrayList<>();
        try {
            ArrayList<String> data = readGenreDataIntoMemory(file1);
            ArrayList<String> data1 = readGenreDataIntoMemory(file2);
            StringTokenizer st = null;

            for(String line : data){
                HashSet<String> genres = new HashSet<>();
                boolean sameMovie = false;
                String movie2 = "";
                st = new StringTokenizer(line, "|");
                //String line[] = fline.split("\\|");
                String ratingInfo = st.nextToken();
                String movie1 = st.nextToken();
                String genreInfo = st.nextToken();
                if(!genreInfo.equals("null")){
                    for(String s : genreInfo.split(",")){
                        genres.add(s);
                    }
                }


                StringTokenizer st1 = null;
                for(String line1 : data1){
                    st1 = new StringTokenizer(line1, "|");
                    st1.nextToken();
                    movie2 = st1.nextToken();
                    String genreInfo2= st1.nextToken();
                    //If the movie name are similar then they should have the same genre
                    //Update their genres to be the same
                    if(!genreInfo2.equals("null") && movie1.equals(movie2)){
                        for(String s : genreInfo2.split(",")){
                            genres.add(s);
                        }
                        sameMovie = true;
                        break;
                    }
                }
                if(sameMovie){
                    finalOut.add(ratingInfo+""+movieName+""+genres.toString()+"\n");
                }else if(sameMovie ==  false){
                    finalOut.add(line);
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return finalOut;
    }

Upvotes: 1

Views: 61

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533680

I would use the Streams API

String file1 = "files1.txt";
String file2 = "files2.txt";
// get all the lines by movie name for each file.
Map<String, List<String[]>> map = Stream.of(Files.lines(Paths.get(file1)),
                                            Files.lines(Paths.get(file2)))
        .flatMap(p -> p)
        .parallel()
        .map(s -> s.split("[|]", 3))
        .collect(Collectors.groupingByConcurrent(sa -> sa[1], Collectors.toList()));

// merge all the genres for each movie.
map.forEach((movie, lines) -> {
    Set<String> genres = lines.stream()
            .flatMap(l -> Stream.of(l[2].split(",")))
            .collect(Collectors.toSet());
    System.out.println("movie: " + movie + " genres: " + genres);
});

This has the advantage of being O(n) instead of O(n^2) and it's multi-threaded.

Upvotes: 1

aoa
aoa

Reputation: 46

Do a hash join.

As of now you are doing an outer loop join which is O(n^2), the hash join will be amortized O(n)

Put the contents of each file in a hash map, with key the field you want (second field). 

Map<String,String> map1 = new HashMap<>();
// build the map from file1

Then do the hash join

   for(String key1 : map1.keySet()){
        if(map2.containsKey(key1)){
        // do your thing you found the match
        }
    }

Upvotes: 0

Related Questions