Вычисление ресурсоемкости регулярного выражения

Регулярные выражения довольно ресурсоемки по сравнению с обычными строковыми операциями
Более того, их сложность скрыта за компактным синтаксисом - на глаз, почти невозможно оценить, какой из нескольких возможных вариантов будет быстрее. Проблема осложняется различными диалектами (POSIX, Perl) и реализациями (NFA, DFA) регулярных выражений.

Есть ли возможность/инструмент вычисления количества операций, которые потребуютс
регулярному выражению для поиска ответа в заданной строке? В первую очередь интересуют PCRE-регулярные выражения?
    

Ответы

Ответ 1

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

Количество шагов которое показывает regex101 имеет смысл (мое субъективное мнение
только при построении рекурсивных регулярных выражений- в них оно позволит более менее оценить эффективность рекурсии.  

Сравним три регулярных выражения:  


[a-z] - 33 шага https://regex101.com/r/vC5lG7/1  
^[^a-z]*[a-z] - 4 шага https://regex101.com/r/vC5lG7/2  
^[^a-z]*?[a-z] - 4 шага https://regex101.com/r/vC5lG7/3


Выполним простой замер времени выполнения этих выражений:  

function test( $re, $text, $iters ) {
    $t1 = microtime( true );
    for ( $i=0; $i<$iters; $i++ ) {
        $res = preg_match( $re, $text );
    };
    $t2 = microtime( true );
    echo ($t2-$t1)."
";
};

$re1 = "/[a-z]/";
$re2 = "/^[^a-z]*[a-z]/";
$re3 = "/^[^a-z]*?[a-z]/";
$text = "                               a";
$iters = 50000000;

test( $re1, $text, $iters );
test( $re2, $text, $iters );
test( $re3, $text, $iters );


Результат:  

9.5385589599609
9.1712720394135
9.6358540058136


Первое регулярное выражение всего на 4% медленнее второго, хотя количество шаго
было 33 против 4.
Первое регулярное выражение на 1% быстрее третьего, хотя количество шагов было 33 против 4.  

Выводы делайте сами.  



P.S.  


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


Кратко поясню.  

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


Ответ 2

Есть ли возможность/инструмент вычисления количества операций, которые потребуются регулярному выражению для поиска ответа в заданной строке?


Посетите  regex101.com.

Введите \d{4} в окно регулярного выражения, и увидите:



Вычисление заняло 13 шагов, т.е. кол-во операций обращения к функции обратного вызова библиотеки PCRE, скомпилированной при включенном параметре PCRE_AUTO_CALLOUT.

Вот что пишет Люкас Тшещневски:


  The PCRE library supports an auto-callout option through its PCRE_AUTO_CALLOU
flag, which invokes a callback function at every step of matching. I'm 99.99% sure that's how regex101's debugger works. Each callout invocation registers as a step in the debugger.


Чтобы увидеть подробную картину того, что происходит при поиске совпадений в строке с помощью данного регулярного выражения, щелкните regex debugger:



Производительность регулярного выражения и "кол-во шагов"

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

Для реального тестирования производительности регулярного выражения, используйт
простой метод:

1) Приготовьте цикл (100-200 тыс. итераций), входные строки, шаблон
 2) Считайте время до начала поиска совпадений до конца
 3) Вычислите среднее время, затраченное на каждую итерацию.


Ответ 3

Лучше, мне кажется, помнить что регулярки - это утилита, и существует она не чтоб
искать быстро, а искать компактными универсальными шаблонами, не тратя время на разработку алгоритмов анализа. 

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

Если надо парсить специализированные форматы - вроде HTML надо помнить, что для и
парсинга есть гораздо более удобные библиотеки, позволяющие сделать парсер читаемее и быстрее.


Ответ 4

Регулярные выражения довольно ресурсоемки по сравнению с обычными
  строковыми операциями


А уж насколько они ресурсоёмки по сравнению с дисковыми операциями, или запросами к БД, или с гонянием данных по сокетам... 

Но давайте представим, что:


У нас сферический конь в вакууме
Задающий вопрос ещё не разучил слово "профайлер"


Как можно оценить "эффективность" того или иного подхода? Очевидно, с определения этой самой эффективности. Классически считается, что либо память, либо скорость. 

OK, как можно измерить скорость? Представляете, неожиданно: отметить время до, после
и посчитать разницу! Это настольо банально, что примеров приводить не буду, дабы не оскорблять собеседников.

Как оценить затраты памяти? Вот тут уже сложней, всё зависит от среды исполнения. Поэтому - "вопрос требует уточнения" :-)

P.S.