Get ready to run back: ещё одна проблема регулярных выражений | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
PHP Developer. Professional Алгоритмы и структуры данных Разработчик программных роботов (RPA) на базе UiPath и PIX
-27%
Scala-разработчик PHP Developer. Basic C# Developer. Professional
-23%
Архитектура и шаблоны проектирования iOS Developer. Professional MS SQL Server Developer Golang Developer. Professional Vue.js разработчик NoSQL Highload Architect Node.js Developer Web-разработчик на Python Android Developer. Professional Microservice Architecture Reverse-Engineering. Professional React.js Developer Flutter Mobile Developer Разработчик IoT Подготовка к сертификации Oracle Java Programmer (OCAJP) Java Developer. Basic Программист С Супер-интенсив "Tarantool" Специализация Java-разработчик
Инфраструктура
Разработчик программных роботов (RPA) на базе UiPath и PIX
-27%
Administrator Linux. Professional
-26%
Network engineer Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Administrator Linux. Advanced Специализация Network engineer
-5%
Cloud Solution Architecture NoSQL Инфраструктурная платформа на основе Kubernetes Базы данных Microservice Architecture Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по использованию и настройке GIT Administrator Linux.Basic Экспресс-курс «IaC Ansible» Экспресс-курс по управлению миграциями (DBVC) Экспресс-курс "Версионирование и командная работа с помощью Git" Network engineer. Basic
Корпоративные курсы
Безопасность веб-приложений Разработчик программных роботов (RPA) на базе UiPath и PIX
-27%
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Agile Project Manager Руководитель поддержки пользователей в IT
-10%
Промышленный ML на больших данных Cloud Solution Architecture NoSQL Node.js Developer Reverse-Engineering. Basic Machine Learning. Professional Супер-практикум по работе с протоколом BGP Game QA Engineer Разработчик IoT Экcпресс-курс «ELK» Enterprise Architect Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Экспресс-курс «Введение в непрерывную поставку на базе Docker» Вебинар CERTIPORT
Специализации Курсы в разработке Подготовительные курсы Подписка
+7 499 938-92-02

Get ready to run back: ещё одна проблема регулярных выражений

PythonDeep14.05_Site.png

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

Собственно алгоритм, который лежит в её основе схож у многих популярных языков: Python, Perl, Java, Ruby и т.д. И с ним есть проблема: он может жутко «тупить» на некоторых видах регулярок. В частности, это регулярные выражения, где используется backtracking, т.е. возвращение назад в строке при поиске.

Например, "a?b?c"

Чтобы сматчить такое, сначала будет опробовано “аbc”, потом “bc”, “ac”, “c”. Иными словами, сначала испытывается вариант с наличием символа. Если его нет, то надо возвращаться и начинать поиск опять, перечитывать строку.

Таким образом, для регулярки вида "a?"N + "a"N сложность алгоритма O(2^N). Регулярка действительно непростая, и это легко проверить на примере:

$ time python2.7 -c 'import re;re.match("a?"*25 + "a"*25, "a"*25)'`

real    0m3.368s`
user    0m3.327s`
sys 0m0.025s`

Как же быть?

Не отказываться же теперь от backtracking’а? Выход есть! Нужно сменить машину регулярных выражений на использующую алгоритм Thompson NFA (non-deterministic finite automata или недетерменированный конечный автомат).

Его разработал тот самый Кен Томпсон ещё в середине 60-х. Он используется в таких утилитах, как grep и awk. Попробовать его в Python можно с помощью библиотеки re2: это обвязка вокруг C++ реализации от Google.

$ time python2.7 -c 'import re2;re2.match("a?"*25 + "a"*25, "a"*25)'

real    0m0.064s
user    0m0.023s
sys 0m0.022s

Остались вопросы? Напишите в комментариях!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🔥 Выгодные предложения
Подборка курсов, которые можно приобрести по выгодной цене только до конца июля!