Производительность регулярных выражений в Java - лучше несколько сложных или много простых?

Question

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

Matcher m = Pattern.compile("some pattern").matcher(text);
StringBuilder b = new StringBuilder();
int prevMatchIx = 0;
while (m.find()) {
 b.append(text.substring(prevMatchIx, m.start()));
 String matchingText = m.group(); //sometimes group(n)
 //manipulate the matching text
 b.append(matchingText);
 prevMatchIx = m.end();
}
text = b.toString()+text.substring(prevMatchIx);

Мой вопрос заключается в том, какая из двух альтернатив более эффективна (в основном время, но в некоторой степени пространство):

1) Сохраните много существующих блоков, как указано выше (при условии, что нет лучшего способа обработки таких блоков - я не могу использовать простой replaceAll(), потому что группы должны работать).

2)Объедините блоки в один большой блок.Используйте "some pattern", который является комбинацией всех шаблонов старых блоков с использованием оператора | / alternation.Затем используйте if / else if внутри цикла для обработки каждого из подходящих шаблонов.

Спасибо за помощь!

Answer 1

Если порядок, в котором производятся замены, имеет значение, вам следует быть осторожным при использовании техники № 1. Позвольте мне привести пример: если я хочу отформатировать строку так, чтобы она подходила для включения в XML, я должен сначала заменить все & на & и , затем сделать другие замены (например, от < до <). Используя технику №2, вам не придется об этом беспокоиться, потому что вы делаете все замены за один проход.

С точки зрения производительности, я думаю, # 2 будет быстрее, потому что вы будете делать меньше конкатенаций строк. Как всегда, вы можете реализовать оба метода и записать их скорость и потребление памяти, чтобы узнать наверняка. :)

Answer 2

Я бы предложил кешировать шаблоны и использовать метод, который использует кеш.

Шаблоны являются дорогостоящими для компиляции, поэтому, по крайней мере, вы будете компилировать их только один раз, и есть повторное использование кода при использовании одного и того же метода для каждого экземпляра. Позор из-за отсутствия затворов, хотя это сделало бы вещи чище.

   private static Map<String, Pattern> patterns = new HashMap<String, Pattern>();

   static Pattern findPattern(String patStr) {
      if (! patterns.containsKey(patStr))
         patterns.put(patStr, Pattern.compile(patStr));
      return patterns.get(patStr);
   }

   public interface MatchProcessor {
      public void process(String field);
   }

   public static void processMatches(String text, String pat, MatchProcessor processor) {
      Matcher m = findPattern(pat).matcher(text);

      int startInd = 0;
      while (m.find(startInd)) {
         processor.process(m.group());
         startInd = m.end();
      }
   }

Answer 3

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

Регулярное выражение Java не предоставляет традиционных гарантий производительности O (N log M) для настоящих механизмов регулярных выражений(для входных строк длины N и шаблонов длины M).Вместо этого он наследует от своих perl корней экспоненциальное время для некоторых шаблонов.К сожалению, эти патологические паттерны, хотя и редки при нормальном использовании, слишком часто встречаются при объединении регулярных выражений, как вы предлагаете (я могу засвидетельствовать это из личного опыта).

Следовательно, мой совет:

a) предварительно скомпилируйте ваши шаблоны как константы "static final Pattern", чтобы они были инициализированы один раз во время [cinit];или

b) переключиться на пакет лексеров, такой как jflex , который обеспечит более декларативный и гораздо более читаемый синтаксис для подхода к такого рода каскадной / последовательной обработке регулярных выражений;и

c) серьезно рассмотреть возможность использования пакета генератора синтаксического анализатора.Мой текущий фаворит Бобр , но CUP также является хорошим вариантом.Оба из них являются отличными инструментами, и я настоятельно рекомендую оба из них, и, поскольку они оба находятся на вершине jflex, вы можете добавлять их по мере необходимости.

Это, как говорится, если вы не использовалипарсер-генератор до и вы спешите, вам будет легче набрать скорость с JavaCC .Не такой мощный, как Beaver / CUP, но его модель разбора легче понять.

Что бы вы ни делали, пожалуйста, не используйте Antlr.Это очень модно, и у него есть отличные чирлидеры, но его онлайн-документация отстой, его синтаксис неудобен, его производительность плохая, а дизайн без сканера делает несколько простых простых случаев болезненными для обработки.Вам было бы лучше использовать мерзость, такую ​​как sablecc (v1).

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

Answer 4

Вариант № 2 почти наверняка является лучшим путем, если предположить, что объединить регулярные выражения не так уж сложно. И вам не нужно реализовывать это с нуля; API более низкого уровня, на котором построен replaceAll() (т. е. appendReplacement() и appendTail()), также доступен для вашего использования.

Используя пример, который использовал @mangst, вот как вы можете обработать некоторый текст для вставки в документ XML:

import java.util.regex.*;

public class Test
{
  public static void main(String[] args)
  {
    String test_in = "One < two & four > three.";

    Pattern p = Pattern.compile("(&)|(<)|(>)");
    Matcher m = p.matcher(test_in);
    StringBuffer sb = new StringBuffer();  // (1)
    while (m.find())
    {
      String repl = m.start(1) != -1 ? "&amp;" :
                    m.start(2) != -1 ? "&lt;" :
                    m.start(3) != -1 ? "&gt;" : "";

      m.appendReplacement(sb, "");   // (2)
      sb.append(repl);
    }
    m.appendTail(sb);
    System.out.println(sb.toString());
  }
}

В этом очень простом примере все, что мне нужно знать о каждом матче, - это какая группа захвата участвовала в нем, что я узнаю с помощью метода start(n). Но вы можете использовать метод group() или group(n) для проверки сопоставленного текста, как вы упомянули в вопросе.

Примечание (1) Начиная с JDK 1.6, здесь мы должны использовать StringBuffer, потому что StringBuilder еще не существовал, когда был написан класс Matcher. JDK 1.7 добавит поддержку StringBuilder, а также некоторые другие улучшения.

Примечание (2) appendReplacement(StringBuffer, String) обрабатывает аргумент String для замены любой последовательности $n содержимым n -ой группы захвата. Мы не хотим, чтобы это произошло, поэтому передаем пустую строку, а затем append() замещающую строку.

Answer 5

Во-первых, нужно ли это быть эффективным? Если нет, не беспокойтесь - усложнение не поможет в поддержке кода.

Предполагая, что делать это по отдельности, как правило, наиболее эффективно. Это особенно верно, если в выражениях присутствуют большие блоки текста: без чередования это можно использовать для ускорения сопоставления, но это никак не поможет.

Если производительность действительно критична, вы можете кодировать ее несколькими способами и тестировать с примерами данных.