How sort N files

Question

Following this answer -->

How do I sort very large files

I need only the Merge function on N already sorted files on disk , I want to sort them into one Big file my limitation is the memory Not more than K lines in the memory (K < N) so i cannot fetch all them and then sort, preferred with java

so far I Tried as the code below , but I need a good way to iterate over all N of files line by line (not more than K LINES in memory) + store to disk the sorted final file

       public void run() {
            try {
                System.out.println(file1 + " Started Merging " + file2 );
                FileReader fileReader1 = new FileReader(file1);
                FileReader fileReader2 = new FileReader(file2);

                //......TODO with N ?? ......

                FileWriter writer = new FileWriter(file3);
                BufferedReader bufferedReader1 = new BufferedReader(fileReader1);
                BufferedReader bufferedReader2 = new BufferedReader(fileReader2);
                String line1 = bufferedReader1.readLine();
                String line2 = bufferedReader2.readLine();
                //Merge 2 files based on which string is greater.
                while (line1 != null || line2 != null) {
                    if (line1 == null || (line2 != null && line1.compareTo(line2) > 0)) {
                        writer.write(line2 + "\r\n");
                        line2 = bufferedReader2.readLine();
                    } else {
                        writer.write(line1 + "\r\n");
                        line1 = bufferedReader1.readLine();
                    }
                }
                System.out.println(file1 + " Done Merging " + file2 );
                new File(file1).delete();
                new File(file2).delete();
                writer.close();
            } catch (Exception e) {
                System.out.println(e);
            }
        }

regards,

Answer 1

You can use something like this

public static void mergeFiles(String target, String... input) throws IOException {
    String lineBreak = System.getProperty("line.separator");
    PriorityQueue<Map.Entry<String,BufferedReader>> lines
        = new PriorityQueue<>(Map.Entry.comparingByKey());
    try(FileWriter fw = new FileWriter(target)) {
        String header = null;
        for(String file: input) {
            BufferedReader br = new BufferedReader(new FileReader(file));
            String line = br.readLine();
            if(line == null) br.close();
            else {
                if(header == null) fw.append(header = line).write(lineBreak);
                line = br.readLine();
                if(line != null) lines.add(new AbstractMap.SimpleImmutableEntry<>(line, br));
                else br.close();
            }
        }
        for(;;) {
            Map.Entry<String, BufferedReader> next = lines.poll();
            if(next == null) break;
            fw.append(next.getKey()).write(lineBreak);
            final BufferedReader br = next.getValue();
            String line = br.readLine();
            if(line != null) lines.add(new AbstractMap.SimpleImmutableEntry<>(line, br));
            else br.close();
        }
    }
    catch(Throwable t) {
        for(Map.Entry<String,BufferedReader> br: lines) try {
            br.getValue().close();
        } catch(Throwable next) {
            if(t != next) t.addSuppressed(next);
        }
    }
}

Note that this code, unlike the code in your question, handles the header line. Like the original code, it will delete the input lines. If that’s not intended, you can remove the DELETE_ON_CLOSE option and simplify the entire reader construction to
BufferedReader br = new BufferedReader(new FileReader(file));

It has exactly as much lines in memory, as you have files.

While in principle, it is possible to hold less line strings in memory, to re-read them when needed, it would be a performance disaster for a questionable little saving. E.g. you have already N strings in memory when calling this method, due to the fact that you have N file names.

However, when you want to reduce the number of lines held at the same time, at all costs, you can simply use the method shown in your question. Merge the first two files into a temporary file, merge that temporary file with the third to another temporary file, and so on, until merging the temporary file with the last input file to the final result. Then you have at most two line strings in memory (K == 2), saving less memory than the operating system will use for buffering, trying to mitigate the horrible performance of this approach.

Likewise, you can use the method shown above to merge K files into a temporary file, then merge the temporary file with the next K-1 file, and so on, until merging the temporary file with the remaining K-1 or less files to the final result, to have a memory consumption scaling with K < N. This approach allows to tune K to have a reasonable ratio to N, to trade memory for speed. I think, in most practical cases, K == N will work just fine.

Answer 2

@Holger gave a nice answer assuming that K>=N.

You can extend it to the K<N case by using mark(int) and reset() methods of the BufferedInputStream.

The parameter of mark is how many bytes a single line can have.

The idea is as follows:

Instead of putting all the N lines in the TreeMap, you can only have K of them. Whenever you put a new line into the set and it is already 'full' you evict the smallest one from it. Additionally, you reset the stream from which it came. So when you will read it again the same data can pop up.

You have to keep track of the maximum line not kept in the TreeSet, lets call it the lower bound. Once there are no elements in the TreeSet greater than the maintained lower bound, you scan all the files once again and repopulate the set.

I'm not sure if this approach is optimal, but should be ok.

Moreover, you have to be aware that BufferedInputStream has an internal buffer at least the size of a single line, so that will consume a lot of your memory, perhaps it would be better to maintain buffering on your own.