20
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I'm not quite sure what the int shortestLongLength code section is used for, have I missed something here? It seems to me like it should be enough with one while loop instead of two, shouldn't it? \$\endgroup\$ Jan 11, 2016 at 20:11
  • \$\begingroup\$ @SimonForsberg The shortestLongLength is used as an early exit for any line that will not affect the result. With two loops I avoid repeatedly calculating it before I have found my initial n lines. \$\endgroup\$
    – Emily L.
    Jan 11, 2016 at 20:13
  • \$\begingroup\$ Ah, okay. You are first only reading N lines, and then you're continously removing the shortest line and adding a longer one. Instead of storing all of the results and then only fetching the N longest ones. \$\endgroup\$ Jan 11, 2016 at 20:15
  • \$\begingroup\$ @SimonForsberg Exactly, I try to keep my result list as short as possible and just ignore any line shorter than the shortest string in the current result list. \$\endgroup\$
    – Emily L.
    Jan 11, 2016 at 20:16
  • \$\begingroup\$ This is very easy with Unix. Just stick the following in a shell script: awk '{ print length, $0 }' "$1" | sort -n -r -s | cut -d" " -f2- ;) \$\endgroup\$
    – Wildcard
    Jan 12, 2016 at 9:07

5 Answers 5

12
\$\begingroup\$

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 :(

\$\endgroup\$
4
  • \$\begingroup\$ That is so true, I'm only here for the score and the quick fix ;) Sing with me "It's aaaall about the algo, all about the bam bam badibum bam". Ooh I didn't know about the Java8 comparator thing, but I targeted Java 7 which I apparently forgot to mention (because that's what it said in the editor box I uploaded the code in). \$\endgroup\$
    – Emily L.
    Jan 11, 2016 at 20:47
  • \$\begingroup\$ This is the closest I could find to the video I had in mind: codeproject.com/Articles/340797/… I have performed the exact same benchmark. Which is why I opted for O(n) over O(1) insertion time. \$\endgroup\$
    – Emily L.
    Jan 11, 2016 at 21:08
  • \$\begingroup\$ If the "Top X" is less than 1% of the total count, then nothing with any of the lists really makes a difference. All you do is one comparison with the first list member and forget about it. My insert/remove is probably slow in that regard. \$\endgroup\$
    – rolfl
    Jan 11, 2016 at 23:37
  • 1
    \$\begingroup\$ I benchmarked your idea with using a linked list, as you said, when top X is very small, then it is quite fast to use a linked list. However as this is a programming challenge, you can bet your tushie that top x won't be small :) I attached benchmark graphs and source in OP. Let me know if I did something wrong. And nice job on µbench! \$\endgroup\$
    – Emily L.
    Jan 12, 2016 at 21:30
20
\$\begingroup\$

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)\$

\$\endgroup\$
6
  • \$\begingroup\$ I debated whether to use a tree or a list (well array, not linked list). But I eventually opted for the list because of better locality of access. Shifting pointers in an array that is hot in cache is quite fast. But I will try your suggestion and get back. \$\endgroup\$
    – Emily L.
    Jan 11, 2016 at 20:11
  • \$\begingroup\$ @EmilyL. I don't know how you benchmark, but may I suggest a good benchmarking library? \$\endgroup\$ Jan 11, 2016 at 20:22
  • \$\begingroup\$ Note that in Java 8, the comparator can be written as Comparator.comparingInt(String::length).thenComparing(java.util.function.Function.identity()). \$\endgroup\$ Jan 11, 2016 at 22:12
  • \$\begingroup\$ @SimonForsberg in this case, the size of the list is constrained to N, which is a known constant. (unless it is considered a variable of the problem, bound by n as well) \$\endgroup\$
    – njzk2
    Jan 11, 2016 at 22:44
  • \$\begingroup\$ @SimonForsberg I have fixed the implementation now, unfortunately the results stayed the same. The ArrayList is faster than TreeSet in the tests I did, by quite some margin. If you find anything wrong with the implementation please let me know. \$\endgroup\$
    – Emily L.
    Jan 13, 2016 at 19:14
13
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Not that there is anything wrong with this, but there is one extra step left at the end: sort the heap's contents, as a heap is not completely sorted. \$\endgroup\$
    – mleyfman
    Jan 11, 2016 at 20:39
  • \$\begingroup\$ @EmilyL. Your solution is actually O(L log N), as you process each line by adding/remove from a sorted data structure. You can match this performance with a heap by having the heap store the strings by length. The shortest string will always be at the top. Every time you add an element to a heap, you poll the top to remove it. The approach is similar to my answer. As to which is faster...that is a question for benchmarks. \$\endgroup\$
    – mleyfman
    Jan 11, 2016 at 21:04
  • \$\begingroup\$ @EmilyL. No need to sort. Use a min-heap. It will always contain the N longest. It has the same time and space complexity as yours. \$\endgroup\$
    – janos
    Jan 11, 2016 at 21:07
  • \$\begingroup\$ @EmilyL. You let the min-heap grow to N elements, just like your list, and then every time you add an element, you poll to remove the lowest. The size of the heap stays at N, so you get O(L log N) time and O(N) space, just like your implementation. \$\endgroup\$
    – janos
    Jan 11, 2016 at 21:22
  • \$\begingroup\$ I tried the PriorityQueue myself, pruning the queue after every insert to prevent it from growing beyond N elements. However, it turns out that the TreeSet solution is still nicer, because if you use a min-heap to facilitate pruning, then you end up with a data structure that lets you extract N results in O(N log N) time in order of increasing length, so you still have to reverse a list of length N. \$\endgroup\$ Jan 11, 2016 at 22:00
7
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ @EmilyL., it's O(L + L log N), not O(L + N log N), you do L inserts, each of which takes log N time. As to your debate, figuring out the constants in the asymptotic complexity is a job for benchmarking. \$\endgroup\$
    – mleyfman
    Jan 11, 2016 at 21:06
  • 2
    \$\begingroup\$ Don't use myTreeSet.remove(myTreeSet.first()) — that's O(log |S|) time to find an entry, then O(log |S|) time to find it again and remove it. Instead, use myTreeSet.pollFirst(). \$\endgroup\$ Jan 11, 2016 at 22:06
  • 2
    \$\begingroup\$ @200_success while it is indeed better to use 1 method instead of 2, the complexity is the same. A TreeSet is Red-Black tree under the hood, so maintaining the structure takes O(log|S|) time in any case. I did edit my answer to switch to that though. \$\endgroup\$
    – mleyfman
    Jan 12, 2016 at 0:33
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ A solution based on TreeSet shouldn't require more memory than one based on PriorityQueue, if you ignore the overhead of the tree entries and the tree pointers. \$\endgroup\$ Jan 11, 2016 at 23:38
  • \$\begingroup\$ @200_success: Right--it's usually not going to be drastically more, but it will typically be at least somewhat more. \$\endgroup\$ Jan 11, 2016 at 23:41
  • \$\begingroup\$ As this is a programming challenge type site, we are restricted to the standard library in Java unfortunately. \$\endgroup\$
    – Emily L.
    Jan 12, 2016 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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