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.
int shortestLongLength
code section is used for, have I missed something here? It seems to me like it should be enough with onewhile
loop instead of two, shouldn't it? \$\endgroup\$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 initialn
lines. \$\endgroup\$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 theN
longest ones. \$\endgroup\$awk '{ print length, $0 }' "$1" | sort -n -r -s | cut -d" " -f2-
;) \$\endgroup\$