String.replaceAll значительно медленнее, чем делать работу самостоятельно

Question

У меня есть старый фрагмент кода, который выполняет поиск и замену токенов в строке.

Он получает карту из пар from и to, выполняет итерации по ним и для каждой из этих пар, перебирает целевую строку, ищет from, используя indexOf(), и заменяет его значением to.Он выполняет всю работу над StringBuffer и в конечном итоге возвращает String.

Я заменил этот код на следующую строку: replaceAll("[,. ]*", "");
И я провел несколько сравнительных тестов производительности.
Когдасравнивая для 1,000,000 итераций, я получил это:

Старый код: 1287 мс
Новый код: 4605 мс

в 3 раза дольше!

Затем я попытался заменить его 3 вызовами на replace:
replace(",", "");
replace(".", "");
replace(" ", "");

Это привело к следующим результатам:

Старый код: 1295
Новый код: 3524

В 2 раза дольше!

Есть идеи, почему replace и replaceAll так неэффективны?Могу ли я сделать что-нибудь, чтобы сделать это быстрее?

---

Редактировать: Спасибо за все ответы - главная проблема была в том, что [,. ]* не сделал то, что я хотел, чтобы он делал,Изменение его на [,. ]+ почти равнялось производительности решения, не основанного на Regex.Использование предварительно скомпилированного регулярного выражения помогло, но оказалось незначительным.(Это решение очень применимо для моей проблемы.

Тестовый код:
Заменить строку на регулярное выражение: [,.] *
Заменить строку на регулярное выражение:[,.] +
Заменить строку на регулярное выражение: [,.] + И предварительно скомпилированный шаблон

Answer 1

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

Обратите внимание, что использование String.replaceAll() скомпилирует регулярное выражение каждый раз вы называете это.

Вы можете избежать этого, явно используя Pattern объект:

Pattern p = Pattern.compile("[,. ]+");

// repeat only the following part:
String output = p.matcher(input).replaceAll("");

Обратите внимание также на использование + вместо * избегает замены пустых строк и, следовательно, может также ускорить процесс.

Answer 2

replace и replaceAll использует регулярное выражение для внутреннего использования, что в большинстве случаев дает серьезное влияние на производительность по сравнению, например, с StringUtils.replace(..).

String.replaceAll():

public String replaceAll(String regex, String replacement) {
        return Pattern.compile(regex).matcher(this ).replaceAll(
             replacement);
}

String.replace() использует внизу Pattern.compile.

public String replace(CharSequence target, CharSequence replacement) {
  return Pattern.compile(target.toString(), Pattern.LITERAL)
         .matcher(this ).replaceAll(
           Matcher.quoteReplacement(replacement.toString()));
}

Такжесм. Заменить все вхождения подстроки в строке - что более эффективно в Java?

Answer 3

Как я положил в комментарии [,.] * соответствует пустой строке "".Итак, каждый «пробел» между символами соответствует шаблону.Это отмечено только в производительности, потому что вы заменяете много "" на "".

Попробуйте сделать это:

Pattern p = Pattern.compile("[,. ]*");
System.out.println(p.matcher("Hello World").replaceAll("$$$");

Возвращает:

H $$$ e $$$ l $$$ o $$$$$$ W $$$ o $$$ r $$$ l $$$ d $$$! $$$

Неудивительно, что этомедленнее, чем делать это "вручную"!Вы должны попробовать с [,.] +

Answer 4

Когда дело доходит до replaceAll("[,. ]*", ""), это не так уж удивительно, поскольку оно опирается на регулярные выражения.Движок регулярных выражений создает автомат, который запускает вход.Ожидаются некоторые накладные расходы.

Второй подход (replace(",", "")...) также использует регулярные выражения внутри.Здесь данный шаблон, однако, скомпилирован с использованием Pattern.LITERAL, поэтому накладные расходы регулярного выражения должны быть пренебрежимо малы.) В этом случае это, вероятно, связано с тем, что Strings являются неизменяемыми (как бы мало вы ни изменяли, вы создадите новую строку) и, следовательно, не так эффективен, как StringBuffers, который манипулирует строкой на месте.