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

Question

Я видел, что здесь люди делали комментарии типа "регулярное выражение слишком медленное!" Или "зачем вам делать что-то настолько простое, используя регулярное выражение!" (а затем вместо этого представьте альтернативу в 10 и более строк) и т. д.

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

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

То, что считается простым, конечно, субъективно, но я думаю, что разумным стандартом является то, что если он использует только String, StringBuilder и т. Д., То это, вероятно, просто.

---

Примечание : Я был бы очень признателен за ответы, которые демонстрируют следующее:

1. решение регулярного выражения начального уровня для не-игрушечной реальной проблемы, которая ужасно работает
2. простое решение без регулярных выражений
3. regex экспертного уровня, который выполняет сравнительно

Answer 1

Я помню пример из учебника.Имейте в виду, что ни один из следующих подходов не рекомендуется для производственного использования!Вместо этого используйте правильный синтаксический анализ CSV.

Ошибка, сделанная в этом примере, довольно распространена: использование точки, где более узкий класс символов подходит лучше.

В файле CSV, содержащем в каждой строке точно12 целых чисел, разделенных запятыми, найдите строки с 13 в 6-й позиции (независимо от того, где еще может быть 13).

1, 2, 3, 4, 5, 6, 7, 8 ,9 ,10,11,12 -- don't match
42,12,13,12,32,13,14,43,56,31,78,10 -- match
42,12,13,12,32,14,13,43,56,31,78,10 -- don't match

Мы используем регулярное выражение, содержащее ровно 11 запятых:

".*,.*,.*,.*,.*,13,.*,.*,.*,.*,.*,.*"

Таким образом, каждое ". *" Ограничивается одним числом.Это регулярное выражение решает задачу, но имеет очень плохую производительность.(Примерно 600 микросекунд на строку на моем компьютере, с небольшой разницей между согласованными и несопоставленными строками.)

Простое решение без регулярных выражений состояло бы в split() каждой строке и сравнении 6-го элемента.(Гораздо быстрее: 9 микросекунд на строку.)

Причина, по которой регулярное выражение является таким медленным, заключается в том, что квантор "*" по умолчанию жадный, и поэтому первый ". *" Пытается соответствовать всей строке,и после этого начинается откат к персонажу.Время выполнения является экспоненциальным в количестве чисел в строке.

Таким образом, мы заменим жадный квантификатор на неохотный:

".*?,.*?,.*?,.*?,.*?,13,.*?,.*?,.*?,.*?,.*?,.*?"

Это работает намного лучше для согласованной строки (коэффициент 100), но имеет почти неизменную производительность для несопоставленной строки.

Регулярное выражение-исполнитель заменяет точку классом символов "[^,]":

"[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,13,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*,[^,]*"

(Для этого нужно 3,7 микросекунды на строку для согласованной строки и 2,4 для несопоставленной строки на моем компьютере.)

Answer 2

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

Java регулярное выражение принимает O(N) для соответствия "(?s)^.*+$"

Это очень обидно. Для ".*" понятно, что он принимает O(N), но с оптимизационными «подсказками» в виде якорей (^ и $) и однострочного режима Pattern.DOTALL/(?s), даже делая повторение притяжательным (т.е. нет откат), движок регулярных выражений все еще не мог видеть, что это будет соответствовать каждой строке, и все равно должен совпадать в O(N).

Этот шаблон, конечно, не очень полезен, но рассмотрим следующую проблему.

Java регулярное выражение принимает O(N) для соответствия "(?s)^A.*Z$"

Опять же, я надеялся, что механизм регулярных выражений сможет увидеть, что благодаря якорям и однострочному режиму это, по сути, то же самое, что и O(1) non-regex:

 s.startsWith("A") && s.endsWith("Z")

К сожалению, нет, это все еще O(N). Очень разочаровывает. Тем не менее, не очень убедительно, потому что существует хорошая и простая альтернатива без регулярных выражений.

Java регулярное выражение занимает O(N) для соответствия "(?s)^.*[aeiou]{3}$"

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

Я также попытался "(?s)^.*$(?<=[aeiou]{3})", пытаясь заставить механизм регулярных выражений просто игнорировать все остальное и просто проверить последние 3 символа, но, конечно, это все равно O(N) (что следует из первого раздела выше) .

В этом конкретном сценарии, однако, регулярное выражение можно сделать полезным, комбинируя его с substring. То есть вместо того, чтобы видеть, соответствует ли вся строка шаблону, вы можете вручную ограничить шаблон, чтобы попытаться сопоставить только последние 3 символа substring. В общем, если вы знаете заранее, что шаблон имеет максимальное соответствие конечной длины, вы можете substring необходимое количество символов в конце очень длинной строки и выполнить регулярное выражение только для этой части.

---

Испытательный жгут

static void testAnchors() {
    String pattern = "(?s)^.*[aeiou]{3}$";
    for (int N = 1; N < 20; N++) {
        String needle = stringLength(1 << N) + "ooo";
        System.out.println(N);
        boolean b = true;
        for (int REPS = 10000; REPS --> 0; ) {
            b &= 
              needle
              //.substring(needle.length() - 3) // try with this
              .matches(pattern);
        }
        System.out.println(b);
    }
}

Длина строки в этом тесте растет в геометрической прогрессии. Если вы запустите этот тест, вы обнаружите, что он начинает действительно замедляться после 10 (то есть длина строки 1024). Однако, если вы раскомментируете строку substring, весь тест завершится в кратчайшие сроки (что также подтверждает, что проблема не в том, что я не использовал Pattern.compile, что в лучшем случае дало бы постоянное улучшение, а скорее потому, что шаблон соответствует O(N), что проблематично, когда асимптотический рост N экспоненциальный).

---

Заключение

Кажется, что регулярное выражение Java мало что делает для оптимизации на основе шаблона. В частности, сопоставление суффиксов особенно дорого, поскольку регулярное выражение все еще должно проходить по всей длине строки.

К счастью, выполнение регулярного выражения для нарезанного суффикса с использованием substring (если вы знаете максимальную длину совпадения) все еще может позволить вам использовать регулярное выражение для сопоставления суффиксов во времени, не зависящем от длины входной строки.

// update: На самом деле я только что понял, что это относится и к сопоставлению префиксов. Java regex соответствует шаблону префикса длины O(1) в O(N). То есть "(?s)^[aeiou]{3}.*$" проверяет, начинается ли строка с 3 строчных букв в O(N), когда ее следует оптимизировать до O(1).

Я думал, что сопоставление префиксов будет более дружественным к регулярным выражениям, но я не думаю, что можно придумать шаблон O(1) -runtime, чтобы соответствовать вышеуказанному (если кто-то не докажет, что я не прав).

Очевидно, что вы можете выполнить "трюк" s.substring(0, 3).matches("(?s)^[aeiou]{3}.*$"), но сам шаблон все еще O(N); Вы только что вручную уменьшили N до постоянной, используя substring.

Таким образом, для любого вида соответствия префикса / суффикса конечной длины действительно длинной строки, вы должны предварительно обработать, используя substring перед использованием regex; в противном случае это O(N), где O(1) достаточно.

Answer 3

Является ли регулярное выражение слишком медленным?

Регулярное выражение не по сути медленное. базовое сопоставление с образцом - O (n), его трудно улучшить, конечно, для нетривиальных образцов.

Answer 4

В своих тестах я обнаружил следующее:

Использование метода Java String.split (который использует регулярные выражения) занял 2176 мс при 1 000 000 итераций. Использование этого пользовательского метода разделения заняло 43 мсек при 1000000 итерациях.

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

List<String> array = new ArrayList<String>();
String split = "ab";
String string = "aaabaaabaa";
int sp = 0;
for(int i = 0; i < string.length() - split.length(); i++){              
    if(string.substring(i, i + split.length()).equals(split)){
        //Split point found
        array.add(string.substring(sp, i));
        sp = i + split.length();
        i += split.length();
    }
}
if(sp != 0){
    array.add(string.substring(sp, string.length()));
}
return array;

Итак, чтобы ответить на ваш вопрос, это теоретически быстрее? Да, конечно, мой алгоритм O (n), где n - длина строки для разделения. (Я не уверен, что регулярное выражение будет). Это практически быстрее? Что ж, за 1 миллион итераций я сэкономил в основном 2 секунды. Так что это зависит от ваших потребностей, я думаю, но я бы не стал слишком беспокоиться о переносе всего кода, использующего регулярное выражение в версии без регулярного выражения, и на самом деле это может понадобиться в любом случае, если шаблон очень сложный, буквальный разделить, как это не будет работать. Однако, если вы разделяете, скажем, запятые, этот метод будет работать намного лучше, хотя «намного лучше» здесь субъективно.

Answer 5

Ну, не всегда, но иногда медленно, зависит от шаблонов и реализаций.

Быстрый пример, в 2 раза медленнее, чем обычно, заменить, но я не думаю, что он такой медленный.

>>> import time,re
>>>
>>> x="abbbcdexfbeczexczczkef111anncdehbzzdezf" * 500000
>>>
>>> start=time.time()
>>> y=x.replace("bc","TEST")
>>> print time.time()-start,"s"
0.350999832153 s
>>>
>>> start=time.time()
>>> y=re.sub("bc","TEST",x)
>>> print time.time()-start,"s"
0.751000165939 s
>>>