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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

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

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

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

Ответ 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?

Ответ 3

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

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

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

Он возвращает:

Н $$$ $$$ е л о $$$ $$$$$$ Вт $$$ $$$ о г л $$$ $$$ $$$ д! $$$

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

Ответ 4

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

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