Get ready to run back: ещё одна проблема регулярных выражений | OTUS
🔥 Успейте получить скидку!
Только до 27.01 можно приобрести курсы со скидкой 25%. Торопитесь!
Выбрать курс

Курсы

Программирование
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Разработчик C#
-25%
Алгоритмы и структуры данных
-25%
Backend-разработчик на PHP
-25%
JavaScript Developer. Professional
-25%
Team Lead
-25%
Golang Developer. Professional
-25%
Agile Project Manager
-25%
Flutter Mobile Developer
-25%
Android Developer. Professional
-11%
MS SQL Server Developer
-8%
Java Developer. Professional Web-разработчик на Python Cloud Solution Architecture Highload Architect Reverse-Engineering. Professional Kotlin Backend Developer React.js Developer VOIP инженер Нереляционные базы данных Scala-разработчик Супер-практикум по использованию и настройке GIT IoT-разработчик JavaScript Developer. Basic Advanced Fullstack JavaScript developer Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Супер-интенсив "Версионирование и командная работа с помощью Git"
-30%
Administrator Linux. Professional
-25%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Administrator Linux. Advanced
-25%
Infrastructure as a code in Ansible
-25%
Administrator Linux.Basic
-25%
Инфраструктурная платформа на основе Kubernetes
-6%
PostgreSQL Software Architect Reverse-Engineering. Professional Внедрение и работа в DevSecOps VOIP инженер Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool"
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться
Только до 27 января!
🔥 СКИДКА 25% на курсы OTUS!