I am building a Comparator that provides multi-column sort capability on a delimited String.
I am currently using the split method from String class as my preferred choice for splitting the raw String into tokens.
Is this the best performing way to convert the raw String into a String array? I will be sorting millions of rows so I think approach matters.
It seems to run fine and is very easy, but unsure if there’s a faster way in java.
Here is how the sort works in my Comparator:
public int compare(String a, String b) {
String[] aValues = a.split(_delimiter, _columnComparators.length);
String[] bValues = b.split(_delimiter, _columnComparators.length);
int result = 0;
for( int index : _sortColumnIndices ) {
result = _columnComparators[index].compare(aValues[index], bValues[index]);
if(result != 0){
break;
}
}
return result;
}
After benchmarking the various approaches, believe it or not, the split method was the quickest using the latest version of java. You can download my completed comparator here: https://sourceforge.net/projects/multicolumnrowcomparator/
5
I’ve written a quick and dirty benchmark test for this. It compares 7 different methods, some of which require specific knowledge of the data being split.
For basic general purpose splitting, Guava Splitter is 3.5x faster than String#split() and I’d recommend using that. Stringtokenizer is slightly faster than that and splitting yourself with indexOf is twice as fast as again.
For the code and more info see https://web.archive.org/web/20210613074234/http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance
(original link is dead and corresponding site does not appear to exist anymore)
8
As @Tom writes, an indexOf type approach is faster than String.split(), since the latter deals with regular expressions and has a lot of extra overhead for them.
However, one algorithm change that might give you a super speedup. Assuming that this Comparator is going to be used to sort your ~100,000 Strings, do not write the Comparator<String>. Because, in the course of your sort, the same String will likely be compared multiple times, so you will split it multiple times, etc…
Split all the Strings once into String[]s, and have a Comparator<String[]> sort the String[]. Then, at the end, you can combine them all together.
Alternatively, you could also use a Map to cache the String -> String[] or vice versa. e.g. (sketchy) Also note, you are trading memory for speed, hope you have lotsa RAM
HashMap<String, String[]> cache = new HashMap();
int compare(String s1, String s2) {
String[] cached1 = cache.get(s1);
if (cached1 == null) {
cached1 = mySuperSplitter(s1):
cache.put(s1, cached1);
}
String[] cached2 = cache.get(s2);
if (cached2 == null) {
cached2 = mySuperSplitter(s2):
cache.put(s2, cached2);
}
return compareAsArrays(cached1, cached2); // real comparison done here
}
4
According to this benchmarks, StringTokenizer is faster for splitting strings but it doesn’t return an array which makes it less convenient.
If you need to sort millions of rows I’d recommend using a RDBMS.
1
This is the method I use for parsing large (1GB+) tab-delimited files. It has far less overhead than String.split(), but is limited to char as a delimiter. If anyone has a faster method, I’d like to see it. This can also be done over CharSequence and CharSequence.subSequence, but that requires implementing CharSequence.indexOf(char) (refer to the package method String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) if interested).
public static String[] split(final String line, final char delimiter)
{
CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
int wordCount = 0;
int i = 0;
int j = line.indexOf(delimiter, 0); // first substring
while (j >= 0)
{
temp[wordCount++] = line.substring(i, j);
i = j + 1;
j = line.indexOf(delimiter, i); // rest of substrings
}
temp[wordCount++] = line.substring(i); // last substring
String[] result = new String[wordCount];
System.arraycopy(temp, 0, result, 0, wordCount);
return result;
}
2