Print the N longest lines in a file

Question

I have implemented the "Find the N longest lines in a file" problem from CodeEval quoted below.

I got a full 100 score and 182ms execution time of their data set on the site so I consider the code to be working and effective. What I'm wondering is, is there something I can do to make this faster than it already is? Did I miss anything? Any other comments?

Write a program which reads a file and prints to stdout the specified number of the longest lines that are sorted based on their length in descending order. Input sample:

Your program should accept a path to a file as its first argument. The file contains multiple lines. The first line indicates the number of lines you should output, the other lines are of different length and are presented randomly. You may assume that the input file is formatted correctly and the number in the first line is a valid positive integer.

For Example:

2
Hello World
CodeEval
Quick Fox
A
San Francisco

Output sample:

Print out the longest lines limited by specified number and sorted by their length in descending order.

For example:

San Francisco
Hello World

The code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class NLongestLines {

    private final static Comparator<String> CMP = new Comparator<String>() {
        @Override
        public int compare(String arg0, String arg1) {
            return arg1.length() - arg0.length();
        }
    };

    private static void insertSorted(List<String> list, String string) {
        int max = list.size();
        int min = 0;
        int pivot = min + (max - min) / 2;

        // Binary search for insertion point.
        while (min < max) {
            int c = CMP.compare(string, list.get(pivot));
            if (c <= 0) {
                max = pivot;
            } else {
                min = pivot + 1;
            }
            pivot = min + (max - min) / 2;
        }

        list.add(min, string);
    }

    public static void main(String[] args) throws Exception {
        try (FileReader fr = new FileReader(args[0]); 
             BufferedReader reader = new BufferedReader(fr)) {
            List<String> longestLines = new ArrayList<>();

            String line = reader.readLine();
            {
                int numLongestLines = Integer.parseInt(line);
                while (numLongestLines > 0 && (line = reader.readLine()) != null) {
                    numLongestLines--;
                    line = line.trim();
                    insertSorted(longestLines, line);
                }
            }

            int shortestLongLength = findShortestLongLine(longestLines);
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.length() > shortestLongLength) {
                    insertSorted(longestLines, line);
                    longestLines.remove(longestLines.size() - 1);
                    shortestLongLength = findShortestLongLine(longestLines);
                }
            }

            for (String longLine : longestLines) {
                System.out.println(longLine);
            }
        }
    }

    private static int findShortestLongLine(List<String> longestLines) {
        return longestLines.get(longestLines.size() - 1).length();
    }
}

Edit/Addendum:

I have implemented and benchmarked the proposed solutions by Simon Forsberg (TreeSet) and RolfL (LinkedList).

The results can be seen here. The executive summary is that the original algorithm is significantly faster than the proposals in just about all test cases.

The source used for testing can be found here. Needs µbench from here.

Answer 1

I believe you've fallen in to the hacker-rank mentality of do-it-quick... and all in the main method ;-)

Your implementation should have a LongestX class, that is a container that tracks only the longest X number of lines. It should have a constructor along the lines of:

public LongestX<T>(int size, Comparator<T> longer) {
    ....
}

and a method like:

public void evaluate(T content) {
    ....
}

and finally a result method that returns the longest items at that point:

public List<T> longest() {
    ....
}

Then, your code would be simplified logically to something you can stream, even....

... but, before you get there, have a look at the new Java8 comparator constructors:

Comparator<String> longer = Comparator.comparingInt(String::length)

That should sort long strings last .... ;-)

Finally, I recommend using a LinkedList inside your LongestX to store values.... and a simple "walker" on the list that looks something like:

private final LinkedList<T> items = new LinkedList<>()
private final Comparator<T> comp = .....
private final int topx = ....

public void evaluate(T item) {
    for (ListIterator<T> it = items.listIterator(); it.hasNext(); ) {
        if (comp.compare(it.next(), item) >= 0) {
            it.previous()
            it.add(item)
            break;
        }
    }
    if (items.size() > topx) {
        items.removeFirst()
    }
}

The use of ListIterator is a great solution for manipulating linked lists, and because the operations are O(1), it's quick (of course, the linear scan is slower, but we hope that the topx is much smaller than the total number of lines, so we hope that most of the records are smaller than the first record. Of course, if each string is longer than the previous string, then all items will be scanned each time :(

Answer 2

the other lines are of different length and are presented randomly

I understand this as that all lines have different length. As such, I would make a different choice of data structure. Namely, a TreeSet<String>.

A TreeSet can be constructed with a Comparator, so I would use your existing comparator as the constructor for this TreeSet. Then I would use the descendingIterator() method to iterate x times over your elements in descending order.

Note: Even if there would be lines of the same length, you could still use a TreeSet but then you'd need to compare on both the length and the String itself, to avoid ignoring the insertion of an element that has the same length as a previous existing element. (If elements can be exactly identical, then TreeSet will not work well)

This will allow us to get rid of your insertSorted method and get rid of the potentially slow ArrayList.add(index, object) call which is \$O(n - index)\$

Answer 3

Instead of a FileReader + BufferedReader combo, the input processing would be simpler using a Scanner, though probably slower.

You could simplify the implementation by using a min-heap (by way of PriorityQueue), following the same pattern as @Simon suggested with a TreeSet (or more generally a SortedSet). A heap would not require distinct elements, it could naturally handle duplicate elements too, and have similar performance. (Remember that, as usual with a heap, to extract the elements in sorted order, you have to poll() them one by one, rather than simply iterating, as the storage is generally not sorted.)

That being said, the problem description clearly states that the lines have different lengths, so the min-heap solution will not bring extra benefits, and as @200_success pointed out, also have the extra hurdle of reversing the elements after extracting, to make them decreasing order by length. But I think the approach is still noteworthy, because I find the problem statement unrealistically rigged to allow solutions with a SortedSet, perhaps for the sake of simplicity. I can easily imagine realistic problems where you need to find the K largest things, on unconstrained input with possible duplicates.

Answer 4

Expanding on Simon Forsberg's solution:

• It would be wise to keep adding lines to the TreeSet until you have N (the required number for output) lines.
• After N lines, remove the shortest one each time you add one. This can be done with myTreeSet.pollFirst().
• The reason this is useful is that instead of a O(L log(L)) asymptotic performance (where L is the total number of lines per input), you get O(L + L log(N)). The difference is minute, but if N ≪ L (much smaller than), the time savings add up.

Answer 5

Unless I were restricted to what comes with Java "out of the box", I'd at least consider using Guava. Guava's Ordering class supports what you want fairly directly, with a greatestOf and onResultOf, making it fairly easy to choose the N largest by length.

Beyond that, I think a great deal depends on your intent--particularly, whether you're interesting primarily in minimizing development time, execution time, memory usage, etc.

In the real world, you might have some secondary considerations that you really don't know about here, such as how large you expect N to be compared to the total input size, and whether you need to support interactive processing (provide N largest read so far at any time) or only batch processing (always read all the data before providing any output).

So let's consider how these factors would affect the code.

If you care primarily about development time, Simon Forsberg's solution of reading the data into an ordered set, then writing out the N "largest" of them (based on a comparison of line length) is probably the best. It's almost trivially simple, and although it's probably not the fastest, it's still probably plenty fast for most purposes under most circumstances (e.g., the bottleneck will probably be the I/O on almost any reasonable machine).

If you care primarily about minimizing memory usage, jano's solution of using a heap is almost certainly better, especially if we expect the N lines to be a small percentage of the input file. In particular, it stores at most N+1 lines of input at any given time (and the +1 part doesn't last very long either). At least in theory, this probably improves execution speed at least a little, because it's O(L log N) instead of O(L log L) (where L is the number of input lines, and N is the number of output lines). If the input file were large enough that it wouldn't fit in physical RAM, but N+1 lines would, the reduced memory usage might help this gain a much larger advantage (over solutions that involved reading the whole file, then sorting, or anything similar).

As far as interactive vs. batch goes, if you're doing only batch processing (and don't care about memory usage) you'll probably be better off reading and storing all the lines, disregarding order, then doing a (partial) sort to get the lines you care about. Interactive use is more likely to benefit from a data structure that maintains the data as it's being read, so the N longest so far are always available without any extra work.

My own take personally: using only what Java provides out of the box, I'd probably use the priority queue (heap), then copy lines from the heap to a stack, and finally from there to the output. But, I'm much more of a C++ programmer than a Java programmer, so I tend to work on an assumption that both speed and memory usage are likely to matter. If I didn't care about memory usage, choice in C++ would probably be to use std::partial_sort with a comparator doing descending order by length. I'm guessing Java probably provides an equivalent to that, but I don't use Java enough to be sure.