​Разделение строк и велосипеды

Простой способ разделить строку на части — встроенный метод split:

"123-456-789".split("-") → [123, 456, 789]

Сегодня разберём, насколько оптимально работает метод, и как написать код быстрее, чем JDK.

Исходный код split выглядит как-то так:

public String[] split(String regex) {
  if (разделитель — один символ)
    пройтись по всем символам. Встречаем разделитель - извлекаем подстроку
  } else {
    Pattern.compile(regex).split(this)
}

Разберём обе ветки этого кода

Разделитель — один символ

Сразу видим fast path для разделителей из одного символа. Алгоритм в этом случае не использует регулярку и выполняется быстрее. Но проверка, что строка-разделитель является символом, занимает 10(!) строк.

🚲 Напишем свой split — изменим тип входных данных на char, чтобы проверку делал компилятор:

split(String regex) → split(char delim)

Остальной код остаётся тем же. Мы только убрали лишние условия. Потом проверим, стало ли лучше:)

Разделитель — несколько символов

Также в глаза бросается работа с регуляркой, если разделитель состоит из нескольких символов. Компиляция регулярного выражения выполняется долго, для набора строк кажется разумным выполнить её один раз:

List<String> list = …
❌ list.stream().map(s -> s.split(": "))…
✅ Pattern p = Pattern.compile(": ");
    list.stream().map(s -> splitPattern.split(s))

…

Насколько это поможет — проверим в бенчмарке.

С другой стороны, кажется, что регулярка — это слишком серьёзное решение. Если разделитель — двоеточие с пробелом, то мощь регулярного выражения здесь не нужна.

🚲 Поэтому напишем второй велосипед, который очень похож на первый. Будем искать в исходной строке подстроку-разделитель. По полученным индексам делить строку на части.

Оба велосипеда припаркованы тут: 🚲🚲

Оценим готовые решения

Библиотека Apache Commons предлагает метод split, но работает он чуть по-другому. Метод ищет только первый разделитель и делит строку максимум на две части:

StringUtils.split("1-2-3", "-"); 
// получим 2 строки: "1" и "2-3"

Ставим минус за неспортивное поведение, но включаем метод в наши эксперименты.

Результаты

на картинке внизу. Результаты на разных железках могут отличаться.

🔸 Оба велосипеда в пух и прах разбили стандартный split. String#split слишком универсальный, и как любое универсальное решение, проигрывает кастомизированному. Если деление строк — ваш hot spot, не стесняйтесь написать свой метод.

К слову, это не первый велосипед, который выигрывает у JDK. Такое уже случалось при сравнение строк. Надо бы завести тикет по этим кейсам:)

🔸 Если строка делится только на две части — подойдёт split из Apache Commons

❗️Для нормальной нагрузки и однократного вызова подойдёт стандартный String#split. Оптимизации нужны, когда деление строк происходит очень часто.

Не могу не отметить, что хотя подобные задачи появляются редко, они приносят море удовольствия. Разобрать код в деталях, найти пути улучшения, и в итоге метод выполняется в 2 раза быстрее, красота😊