Самый быстрый способ разбить строку с разделителями в Java

Я строю компаратор, который обеспечивает возможность сортировки по нескольким столбцам в строке с разделителями. В настоящее время я использую метод split из класса String в качестве предпочтительного способа разделения необработанной строки на токены.

Это лучший способ преобразования необработанных строк в массив строк? Я буду сортировать миллионы строк, поэтому думаю, что подход имеет значение.

Кажется, что он работает нормально и очень просто, но не уверен, есть ли более быстрый путь в Java.

Вот как работает сортировка в моем компараторе:

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;
}

Поверьте или нет, после сравнения различных подходов, метод split был самым быстрым с использованием последней версии Java. Вы можете скачать мой заполненный компаратор здесь: https://sourceforge.net/projects/multicolumnrowcomparator/

Я написал быстрый и грязный тест для этого. Он сравнивает 7 различных методов, некоторые из которых требуют определенных знаний о данных, которые будут разделены.

Для базового расщепления общего назначения Guava Splitter в 3,5 раза быстрее, чем String # split (), и я бы рекомендовал использовать это. Stringtokenizer немного быстрее, а разделение с помощью indexOf вдвое быстрее, чем снова.

Для получения кода и дополнительной информации см. Http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

Как пишет @Tom, подход типа indexOf быстрее, чем String.split()последний, так как последний имеет дело с регулярными выражениями и имеет много дополнительных накладных расходов для них.

Тем не менее, одно изменение алгоритма может дать вам супер ускорение. Предполагая, что этот компаратор будет использоваться для сортировки ваших ~ 100 000 строк, не пишите Comparator<String>. Потому что в вашем роде одна и та же строка, скорее всего, будет сравниваться несколько раз, поэтому вы будете разбивать ее несколько раз и т. Д.

Разделите все строки один раз на строки [] и получите Comparator<String[]>сортировку строки []. Затем, в конце, вы можете объединить их все вместе.

Кроме того, вы также можете использовать карту для кэширования String -> String [] или наоборот. например (схематично) Также обратите внимание, что вы торгуете памятью на скорость, надеюсь, у вас много оперативной памяти

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
}

Согласно этим тестам , StringTokenizer быстрее разбивает строки, но не возвращает массив, что делает его менее удобным.

Если вам нужно отсортировать миллионы строк, я бы порекомендовал использовать СУБД.

Этот метод я использую для разбора больших (1 ГБ +) файлов с разделителями табуляции. Он имеет гораздо меньше накладных расходов, чем String.split()ограничитель, но ограничен ими char. Если у кого-то есть более быстрый метод, я бы хотел его увидеть. Это также может быть сделано поверх CharSequenceи CharSequence.subSequence, но это требует реализации CharSequence.indexOf(char)(обратитесь к методу пакета, String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)если интересно).

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;
}