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

Курсы

Программирование
Flutter Mobile Developer Подготовка к сертификации Oracle Java Programmer (OCAJP)
-8%
Супер-интенсив «СУБД в высоконагруженных системах»
-18%
Алгоритмы и структуры данных
-12%
Web-разработчик на Python
-11%
Архитектура и шаблоны проектирования
-14%
Team Lead
-15%
iOS-разработчик. Базовый курс
-23%
Разработчик на Spring Framework Python Developer. Basic
-16%
C# ASP.NET Core разработчик
-18%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Android-разработчик. Базовый курс
-10%
C++ Developer. Professional Разработчик C# AWS для разработчиков Software Architect Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов Backend-разработка на Kotlin React.js Developer Разработчик Node.js Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Advanced Fullstack JavaScript developer
Инфраструктура
Супер-интенсив «СУБД в высоконагруженных системах»
-18%
PostgreSQL
-10%
IoT-разработчик
-12%
Administrator Linux. Professional
-11%
Базы данных
-19%
Administrator Linux.Basic
-18%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Сетевой инженер AWS для разработчиков Software Architect Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться