Подтвердить что ты не робот

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

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

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

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

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

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

  • решение регулярного выражения на уровне новичка для неигровой реальной проблемы, которая выполняет ужасно
  • простое решение без регулярных выражений
  • переписывание регулярного выражения на уровне эксперта, выполняющее сравнимо
4b9b3361

ОТВЕТЫ

Ответ 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 для непревзойденных строк на моем компьютере.)

Ответ 2

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

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

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

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

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

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

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

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

Java regex принимает 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, что в лучшем случае обеспечило бы постоянное улучшение, а скорее patttern принимает 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) хватает.

Ответ 3

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

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

Ответ 4

В моих тестах я нашел следующее:

Использование метода java String.split(использующего регулярное выражение) заняло 2176 мс, равное 1 000 000 итераций. С помощью этого пользовательского метода разделения было выполнено 43 мс при 1000 000 итераций.

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

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 секунды. Таким образом, это зависит от ваших потребностей, я думаю, но я не стал бы слишком беспокоиться о том, что вы будете перенаправлять весь код, который использует регулярное выражение для нереджексных версий, и на самом деле это может быть необходимо в любом случае, если шаблон очень сложный, буквальный раскол вроде этого не будет работать. Однако, если вы раскалываете, скажем, запятые, этот метод будет работать намного лучше, хотя "намного лучше" здесь субъективно.

Ответ 5

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

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

>>> 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
>>>