25

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

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

9
  • 2
    думаю, стоит начать с чтения этого perldoc.perl.org/re.html#'debug'-mode
    – KoVadim
    26 июн 2016 в 14:17
  • 9
    regex101.com -> regex debugger. 27 июн 2016 в 21:53
  • А чем-нибудь замерить время не получится?
    – Qwertiy
    28 июн 2016 в 17:22
  • @Qwerty, время прямо пропорционально количеству проделанных шагов. Количество шагов, в свою очередь, можно получить с помощью отладчика (@wiktor-stribiżew, к примеру, уже дал ссылку на такой). 28 июн 2016 в 18:40
  • 1
    @WiktorStribiżew я не раз видел, как на страницах SO сравнивается два регулярных выражения и предпочтение отдается тому, который берет меньше шагов, что логично и правильно. Хотелось бы понять, как это делается практически. Решение принимается в любом виде: сайт, утилита, алгоритм. Все то, чем вы пользуетесь на практике для решения этой задачи.
    – cheops
    28 июн 2016 в 19:21

4 ответа 4

30
+100

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

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

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

  1. [a-z] - 33 шага https://regex101.com/r/vC5lG7/1
  2. ^[^a-z]*[a-z] - 4 шага https://regex101.com/r/vC5lG7/2
  3. ^[^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)."<br/>";
};

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

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

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

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

18

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

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

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

введите сюда описание изображения

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

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

The PCRE library supports an auto-callout option through its PCRE_AUTO_CALLOUT 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) Вычислите среднее время, затраченное на каждую итерацию.

0
4

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

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

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

9
  • 6
    А Вы знаете, что очень часто в транслируемых языках регулярные выражения быстрее ручного алгоритма?
    – ReinRaus
    30 июн 2016 в 4:05
  • @ReinRaus а как так получается?
    – gecube
    30 июн 2016 в 14:20
  • Логично - выполнение ф-ии поиска по регулярке, это скомпилированный код. А он как правило чуток быстрее интерпретируемого. Только из пушки по воробьям бить зачем, зачем нужно шуруповёртом гвозди забивать? Вот назовите мне практический пример, где надо юзать регулярки на большом тексте, да получается так - что они тормозят? 30 июн 2016 в 14:31
  • 1) Было бы интересно посмотреть статистику использования транслируемых и компилируемых языков. Есть подозрение, что на транслируемых языках пишется большая часть кода, ибо это php, js, python, а значит неверно делать антирекомендацию регексам утверждая, что они медленные.
    – ReinRaus
    30 июн 2016 в 17:38
  • 1
    Кроме очень больших текстов есть другая грань вопроса: небольшие тексты. Именно обработка небольших текстов чаще всего используется в программах. И тут регулярные выражения значительно обгонят «чистые» реализации по скорости. Для примера: обгоните text.replace( /[^a-z0-9а-я]+/i, "" ) чистой реализацией в js. Очень частая задача- санация строки. Заодно сравните разницу в объеме кода и его простоте его понимания.
    – ReinRaus
    30 июн 2016 в 17:51
-6

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

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

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

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

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

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

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

P.S.

2
  • 2
    Если правильно понял вопрос, то там не совсем про ту скорость, что Вы описали в ответе-комментарии (так как он ответом не является), а про "Есть ли возможность/инструмент вычисления количества операций, которые потребуются регулярному выражению для поиска ответа в заданной строке?"
    – edem
    28 июн 2016 в 21:32
  • 1
    @edem Ну, это какой-то "академический" вопрос тогда получается :) Количество операций просчитывается заранее, по самому регекспу, ну и с учётом входных данных. А вот что это значит, с учётом реализации, и практической эффективности - совсем другой вопрос :-)
    – PinkTux
    28 июн 2016 в 21:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.