среда, 23 марта 2011 г.

Регулярные выражения в Python: изучение и оптимизация


Writing a regular expression is more than a skill -- it's an art.

Jeffrey Friedl


Что это такое?

Рано или поздно практически каждому программисту в своей жизни приходится сталкиваться с регулярными выражениями.
Термин "Регулярные выражения" является переводом с английского словосочетания "Regular expressions" и есть не совсем точным, а для тех, кто первый раз услышал этот термин, наверное, даже сбивающем с толку (я, например, когда впервые услышал, никак не мог себе вообразить по названию, хотя бы даже примерно, что это, и для чего используется).
Литературный и более осмысленный перевод звучал бы, пожалуй, как "шаблонные выражения". Но название прижилось, а за "шаблонные выражения" вас попросту побьют :).
Отсюда:
Регулярное выражение
это cтрока, задающая шаблон поиска подстрок в тексте.
Регулярные выражения используются для анализа текстов на предмет соответствия находящейся в них текстовой информации некоему шаблону. Например, шаблон задающий слово, содержащее букву "к".


Где применяются регулярные выражения

Регулярные выражения имеют два основных направления применения:
  • анализ и поиск в текстовых массивах
  • проверка данных на соответствие шаблону
Область применения регулярных выражений очень широка. Вот несколько примеров:
  • анализ логов приложений
  • поиск и выборка информации из баз данных, организованных как простые текстовые файлы
  • URL Mapper'ы в веб-фреймворках (например, Django)
  • в приложениях для проверки правильности вводимой информации (например, телефона или адреса электронной почты).


Модуль re

В Python для работы с регулярными выражениями используется модуль re, который входит в стандартную библиотеку Python, начиная с версии Python 1.5. Его предшественник - модуль regex умер, а на Python 1.x сейчас уже, наверное, никто не пишет, так что про него забудьте.


Использование регулярных выражений

Использовать регулярные выражения следует с умом и осторожностью, и только там, где они действительно приносят пользу, а не вред.
Машина регулярных выражений в Python довольно медленная, поэтому может сильно затормозить работу ваших приложений. Поэтому, там, где это возможно, следует пользоваться другими, более подходящими под задачу, средствами. Например, для обработки html использовать регулярные выражения - не очень хорошая идея. Лучше воспользоваться html5lib или BeautifulSoup.
Вторым подводным камнем регулярных выражений есть сложность их прочтения для разработчиков с малым практическим опытом их применения, да и с большим тоже. Разрабатывая регулярное выражение, особенно очень длинное и сложное, следует очень тщательно его тестировать, чтобы не получить неверные результаты в самых неожиданных местах.
Третьей особенностью регулярных выражений является их слабая способность адаптироваться под задачу. То есть при очень небольшом изменении в задании нужное регулярное выражение может вкорне изменить свой вид. Так что при решении задачи с регулярными выражениями следует очень четко определить требования к результатам выполнения задачи.


Правила построения регулярных выражений

Итак, регулярные выражения представляют собой не что иное, как обычные строки. Эти строки могут состоять из:
  • обычных символов (буквы, цифры)
  • управляющих символов: ^ $ * + ? { } [ ] | ( )
Обычные символы значат именно то, что они значат в обычном понимании. Например, регулярное выражение "test" найдет в тексте все слова "test".
Управляющие символы предназначены для создания условий соответствия строки шаблону (ествественно, обычных символов тут недостаточно), и об этом чуть-чуть дальше.
Правило конкатенации: Если A - регулярное выражение и B - регулярное выражение, то AB также регулярное выражение.
Для того, чтобы проще было понимать регулярные выражения при их чтении, советую читать регулярное выражения, преобразуя его про себя в человечески понятный текст. Например, '^test[0-9]*' читать, как "найти текст, начиная с начала строки, который начинается словом test, после которого идет любое количество цифр". Такая интерпретация выражений очень помогает в понимании. Таким способом пользуюсь не только я, но его также рекомендует заслуженный деятель регулярных выражений Джефри Фридл, автор книги "Mastering Regular Expressions".


Средства модуля re для работы с регулярными выражениями

re.match(pattern, string)
Проверяет, соответствует ли начало строки "string" регулярному выражению "pattern". Например, выражению 'test' соответствует строка 'test1', но не соответствует строка '1test'. Возращает объект MatchObject, если строка найдена, или None, если не найдена. Обратите внимание, что также может быть найдена пустая строка, если она соответствует регулярному выражению.
re.search(pattern, string)
Работает аналогично re.match, но проверяет не только с начала строки, а сканирует строку на совпадения полностью. То есть, выражению 'test' будет соответствовать строка '1test', в отличии от предыдущей функции. Зачем две функции? Очевидно, что если вас интересует только начало строки или строка в целом, нужно воспользоваться match, так как скорость его работы будет выше и она не будет делать лишнего сканирования
re.compile(pattern)
"Компилирует" регулярное выражение, заданное в качестве строки в объект для последующей работы. Используется для ускорения работы программы, если одно и то же регулярное выражение используется несколько раз. Например,
compiled_re = re.compile('test')

compiled_re.match('test1')

compiled_re.search('1test')
Соответственно, все поисковые функции дублируются для скомпилированного объекта регулярного выражения, и выступают в качестве методов этого класса, которому стоит передавать единственным параметром анализируемую строку (флаги устанавливаются на этапе компиляции, но об этом немножко позже).
re.findall(pattern, string)
Выполняет поиск всех подстрок в строке, соответствующих регулярному выражению. Возвращает список найденных подстрок, строки не перекрываются.
re.finditer(pattern, string)
Работает так же, как и предыдущая функция, но возвращает итератор, состоящий из объектов MatchingObject.
Кажой из вышеописанных функций также можно передавать флаги, комбинируя их соответствующим образом для того, чтобы подкорректировать выдачу результата. Об этом чуть-чуть позже. В случае компиляции регулярного выражения, флаги передаются на этапе компиляции.


Регулярные выражения на примерах

Итак, перейдем к объяснениям функций механизма регулярных выражений на примерах. Как показывает мой опыт, на примерах регулярные выражения усваиваются гораздо быстрее. Вместе с примерами буду, где это требуется подавать объяснения и "теоретический материал".
Для простоты разбора примеров будем рассматривать только строки, не содержащие символи перевода строки '\n'.
Данные примеры я составил так, чтобы каждый из них демонстрировал некоторую способность механизма регулярных выражений, и это отражается в их названиях. Соответственно в процессе объяснения функций регулярных выражений я буду отталкиваться от задачи, а не от самих функций.


Задача №1: Поиск слова

Дано текст: This is a simple test message for test
Задача: Подсчитать количество слов test в строке.
Решение:

pattern = 'test'
string = 'This is a simple test message for test'
found = re.findall(pattern, string)
len(found) == string.count('test')


Задача №2: Поиск в начале и конце строки

Дано текст: This is a simple test message for test
Задача: Определить, заканчивается ли строка на слово test, и начинается ли на test. Определить является ли строка просто строкой test.
Теория:
Для того, чтобы обозначить конец строки используется символ $, а для обозначения начала строки - ^. Для решения третьей подзадачи пример 1 не подойдет, поскольку поиск ведется по всей строке, поэтому придется использовать оба управляющих символа вместе.
Внимание! Символ ^ обозначает начало строки только тогда, когда он стоит в начале выражения, если нет - он является оператором отрицания, но об этом позже.
Решение:

string = 'This is a simple test message for test'
string2 = 'test'

pattern1 = 'test$'
pattern2 = '^test'
pattern3 = '^test$'

re.search(pattern1, string) is None      
False                                #Строка заканчивается на 'test'

re.match(pattern2, string) is None
True                                 #Строка не начинается на 'test'

re.match(pattern3, string) is None
True                                 #Строка не является строкой 'test'

re.match(pattern3, string2) is None
False                                #Строка является строкой 'test'


Задача №3: Поиск любого символа

Дано текст: We can get 300 to 540 time faster code if we add about 340 lines of code
Задача: Найти все трехзначные числа в тексте, которые начинаются на цифру 3 и заканчиваются на 0.
Теория:
Для того, чтобы указать, что в искомой строке может находится любой символ (кроме символа новой строки) нужно использовать точку - . . Чтобы учитывался и символ новой строки необходимо установить флаг (но об этом позже).
Решение:

string = 'We can get 300 to 540 time faster code if we add about 340 lines of code'
pattern = '3.0'
found = re.findall(pattern, string)
['300', '340']

Данное регулярное выражение ищет трехзначное число (на самом деле, не трехзначное число, а последовательность из трех символов, даже если они внутри более разрядного числа, первый из которых 3, последний - 0, а между ними - любой символ), но для данной строки и задачи пока достаточно.
Как видим, точка обозначает любой символ. Чтобы заставить регулярное выражение искать строчку '3.0' достаточно поставить перед точкой обратный слеш - '3\.0'.


Задача №4: Поиск по группе символов

Дано текст: If 300 spartans were so brave, so 500 spartans could destroy more than 10k warriors of Darius, but 15k and even 20k.
Задача: Найти все цифры в тексте
Теория:
Для того, чтобы указать механизму искать конкретные символы, используются квадратные скобки - [ и ]. Например, [0-9] - все цифры, [a-z] - все буквы нижнего регистра, [123abc] - любой символ из этих шести символов.
Решение:

pattern = '[0-9]'
string = 'If 300 spartans were so brave, so 500 spartans could destroy more than 10k warriors of Darius, but 15k and even 20k'
set(re.findall(pattern, string))
set(['1', '0', '3', '2', '5'])


Задача №5: Поиск с повторениями

Дано текст: If 300 spartans were so brave, so 500 spartans could destroy more than 10k warriors of Darius, but 15k and even 20k.
Задача: Найти все числа в тексте
Теория:
Механизму регулярных выражений можно указывать, что некоторая последовательность может повторятся. Например, в предыдущей задачи мы искали отдельные цифры, представляющие собой единичные символы. Для того, чтобы искать числа нужно указать, что эти символы могут повторятся. Для этого существуют следующие управляющие символы:
* - предшествующее выражение может повторяться 0 или больше раз (то есть пустую строку также найдем)
+ - предшествующее выражение может повторяться 1 или больше раз (пустую стркоу не найдем)
? - предшествующее выражение может повторяться 0 или 1 раз (пустую строку найдем). Соответственно, если вопросительный отсутствует, выражение должно повториться 1 раз.
Решение:

pattern = '[0-9]+'
string = 'If 300 spartans were so brave, so 500 spartans could destroy more than 10k warriors of Darius, byt 15k and even 20k'
set(re.findall(pattern, string))
set(['300', '10', '15', '500', '20'])


Задача №6: Сокращенная запись последовательностей

Дано тексты:
The temperature can be in range 10-15C next week though it was lesser last week(4-9C). It was -5 some time ago.
The temperature can be in range 10- 15C next week though it was lesser last week(4 - 9C). It was even -5 some time ago.
Задача: Найти все диапазоны чисел в строке
Теория:
Для того, чтобы выделить диапазон нам потребуется указать символ дефиса - '-'. Так как это управляющий символ, нам необходимо его экранировать, то есть использовать обратный слеш - '\'. Для часто используемых групп символов удобнее использовать сокращения для групп. Для цифр - это \d. Другие можно найти в документации.
Решение:

pattern1 = '[\d\-]+'
string1 = 'The temperature can be in range 10-15C next week though it was lesser last week(4-9C).'
re.findall(pattern1, string1)
['10-15', '4-9']

pattern2 = '[\d]+ *- *[\d]+'
string2 = 'The temperature can be in range 10- 15C next week though it was lesser last week(4 - 9C). It was even -5 some time ago'
re.findall(pattern2, string2)
['10- 15', '4 - 9']

Разберем решение второй подзадачи детальнее. Строится регулярное выражение так:
  1. [\d]+ - сначала идет число
  2. |пробел|* - дальше может быть любое количество пробелов, а может и не быть
  3. - - дефис
  4. |пробел|* - дальше может быть любое количество пробелов, а может и не быть
  5. [\d]+ - заканчивается искомая строка числом
Данная задача уже более практическая и приносящая пользу. Но, опять-таки, данное регулярное выражение имеет недостаток. Оно не учитывает отрицательные числа.
Примечание! Сокращенные записи для всех последовательностей можно узнать в документации к модулю re.


Задача № 7: Группировка результатов поиска на примере анализа лога

Дано: строки результата логирования команды ping в Ubuntu Linux.
log=[
'64 bytes from localhost.localdomain (127.0.0.1): icmp_req=1 ttl=64 time=0.033 ms',
'64 bytes from localhost.localdomain (127.0.0.1): icmp_req=2 ttl=64 time=0.034 ms',
'64 bytes from localhost.localdomain (127.0.0.1): icmp_req=3 ttl=64 time=0.031 ms',
'64 bytes from localhost.localdomain (127.0.0.1): icmp_req=4 ttl=64 time=0.031 ms']
Задача: найти пары "номер запроса" -> "время ответа"
Теория
Такой "сырой" лог трудно анализировать. Гораздо лучше то, что мы пытаемся получить в результате выполнения задачи. Естественно сырой лог будет одной строкой, но все же представим, что мы разбили его на отдельные строки. Для того, чтобы получить сгруппированные результаты можно воспользоваться круглыми скобками: ( и ). До этого мы пользовались findall, но MatchingObject имеет параметры group и groups, которые возвращают найденные результаты. groups возвращает кортеж групп результатов, group(number) возвращает результат для группы за номером number.
Если в строке есть несколько групп, которые соответствуют одному и тому же шаблону, не стоит его копировать в выражении несколько раз, достаточно сократить запись к номеру группы. То есть ([abc])([abc]) равнозначно ([abc])(\1). Кто знаком с конфигурацией mod_rewrite, например, в сервере Apache2, точно сталкивался с такой записью, так как там она применяется сплошь и рядом.
Решение:

import pprint
pattern = re.compile('(icmp_req=[\d]+).*(time=[\d\.]+ ms)')
result = []
for line in log:
    result.append(pattern.search(line).groups())
pprint.pprint(result)
[('icmp_req=1', 'time=0.033 ms'),
 ('icmp_req=2', 'time=0.034 ms'),
 ('icmp_req=3', 'time=0.031 ms'),
 ('icmp_req=4', 'time=0.031 ms')]

С такими данными работать уже гораздо проще и приятнее. Итак, разберем выражение:
  1. (icmp_req=[\d]+) - находим число, перед которым идет текст 'icmp_req=' и делаем из него группу символов
  2. .* - дальше идет любой набор символов
  3. (time=[\d\.]+|пробел|ms) - находим число, перед которым идет текст 'time=', и после которого идет пробел и текст 'ms'.


Задача №8: Исключение из поиска

Дано html-код: <p style="margin-left:10px;">text<b class="super-bold">bold text</b>.</p>
Задача: Найти все теги в участке html-кода
Теория:
Как уже упоминалось ранее, символ ^ используется для указанния начала строки, но это только в том случае, если он находится в начале выражения. Если он находится всередине выражения, он действует как оператор исключения из поиска.
Решение:

pattern = '<[^>]+>'
string = '<p style="margin-left:10px;">text<b class="super-bold">bold text</b>.<p>'
re.findall(pattern,string)
['<p style="margin-left:10px;">', '<b class="super-bold">', '</b>', '</p>']


Задача №9: Ограничение выдачи по длине или жадность регулярных выражений

Дано: список изделий, заданных строками в следующем виде
things = ['"Table" "1" "200$"',
          '"Stool" "2" "100$"',
          '"Mirror" "3" "400$"']
Задача: извлечь из списка параметры изделий
Теория:
Регулярные выражения обладают такой особенностью, как "жадность". Это значит, что в результат поиска попадет как можно более длинное совпадение. Механизм регулярных выражений имеет средство минимизации поисковой выдачи. Для этого следует добавлять после символа повторения восклицательный знак.
Решение:

import pprint
pattern = re.compile('".*?"')
result = []
for line in things:
    result.append(pattern.findall(line))
pprint.pprint(result)
[['"Table"', '"1"', '"200$"'],
 ['"Stool"', '"2"', '"100$"'],
 ['"Mirror"', '"3"', '"400$"']]

Также данную задачу можно решить способом, описанным в предыдущем примере, применив следующее регулярное выражение: '"[^"]*"'


Задача №10: Корекция выдачи по количеству повторений

Дано текст: 333334 333 123 2334 33345 54443 2195433333332 123333333 44444
Задача: Найти все последовательности цифер 3 в строке, длиной от 2 до 4-х символов.
Теория:
Для того, чтобы указать количество повторений последовательности в регулярных выражениях используются фигурные скобки - { и }. При этот можно задавать как диапазон повторений, так и фиксированное количество. Например, выражение 'a{3}' найдет все последовательности по 3 буквы 'a' подряд, а выражение 'a{3,5}' найдет все последовательности литер 'a' длиной от 3 до 5.
Решение:

pattern = '3{2,4}'
string = '333334 333 123 2334 33345 54443 2195433333332 123333333 44444'
re.findall(pattern, string)
['3333', '333', '33', '333', '3333', '333', '3333', '333']

Не очень-то практическая задачка, но, тем не менее демонстрирует контроль за количеством повторений последовательности символов.


Задача №11: Префиксные и постфиксные проверки

Дано текст: 333334 333 123 2334 33345 54443 2195433333332 123333333 44444
Задача: Найти все числа, в которых встречаются последовательности цифер 3 длиной от 2 до 4-х символов.
Теория:
С тем, что было сказано в предыдущих примерах, вряд ли удастся решить данную задачу, а если и удастся, то получится очень большое, некрасивое и трудночитаемое выражение. Для того, чтобы решить данную задачу регулярные выражения предоставляют постфиксные и префиксные проверки, то есть проверки того, следует ли интересующая нас последовательность символов после некоего шаблона или перед неким шаблоном. Вот несколько вариантов применения
(?<=<условие>)<выражение> - <выражение> будет соответствовать шаблону только тогда, когда оно идет после выражения, которое соответствует шаблону <условие>.
(?<!<условие>)<выражение> - аналогично предыдущему, только будет совпадать, если <условие> НЕ будет совпадать.
(?=<условие>)<выражение> - постфиксное условие, <выражение> будет соответстовать, если после него идет выражение, которое соответствует шаблону <условие>
(?!<условие>)<выражение> - постфиксное условие с отрицанием
Решение:

pattern = '[\d]*(?<!3)3{2,4}(?!3)[\d]*'
string = '333334 333 123 2334 33345 54443 2195433333332 123333333 44444'
re.findall(pattern, string)
['333', '2334', '33345']

Разберем составленное выражение:
  1. [d]* - идет любое количество цифер или цифер нет.
  2. (?<!3) - последующее выражение будет соответствовать только если оно не идет после цифры 3.
  3. 3{2,4} - последовательность цифер 3 длиной от 2-х до 4-х символов
  4. (?!3) - предыдущее выражение будет соответствовать только, когда после него не идет цифра 3.
  5. [d]* - идет любое количество цифер или цифер нет.


Задача №12: Операция "ИЛИ"

Дано текст: ruby python 456 java 789 j2not clash2win
Задача: Найти все упоминания языков программирования в строке.
Теория:
Для того, чтобы указать возможные последовательности символов в конкретном месте строки, в регулярных выражениях используется операция "ИЛИ", обозначается символом |.
Решение:

pattern = 'ruby|java|python|c#|fortran|c\+\+'
string = 'ruby python 456 java 789 j2not clash2win'
re.findall(pattern, string)
['ruby', 'python', 'java']


О примерах

Данные практические примеры помогут решать большинство задач, в которых применяются регулярные выражения. Многую иформацию по регулярным выражениям, как сокращения последовательностей, я не приводил, так как это справочный материал, не нуждающийся в пояснениях. Эту информацию можно с легкостью получить из официальной документации по модулю re.


Флаги

Я уже упоминал о флагах в начале статьи. Флаги используются для модификации поведения механизма поиска. Передаются третим параметром поисковой функции или вторым параметром при компиляции регулярного выражения. Есть следующие флаги:
  • re.DOTALL - символ "." также учитывает переводы строки "\n", если этот флаг не установлен, то перевод строки не будет воспринят как "любой символ"
  • re.IGNORECASE - ищет строки без учета регистра символов, то есть символ 'f' и 'F' будут восприняты как одинаковые
  • re.LOCALE - корректирует поиск под установленную в системе локаль. От этого зависят значения сокращенных записей последовательностей, как \w, \W, \b, \B, которые содержат литеры алфавита.
  • re.MULTILINE - указывает на то, что данная строка "многострочная", то есть содержит символы перевода строки. Это значит, что символы '^' будут '$' учитывать только конец и начало строки, и не будут срабатывать на каждый перевод строки.
  • re.VERBOSE - включает игнорирование пробелов и переводов строки (кроме как при указании набора символов или если пробел указан с обратным слэшом) при создании регулярных выражений. Это позволяет делать регулярные выражения многострочными и добавлять комментарии после символа '#'.
  • re.UNICODE - делает сокращенные записи символьных последовательностей юникодовыми.


Оптимизация регулярных виражений

Оптимизация регулярных выражений как и любая задача оптимизации программного кода является очень веселой. Ниже я предоставлю некие подсказки, которые можно использовать при оптимизации регулярных выражений.
Внимание! Очевидная вещь - основой регулярных выражений являются сравнения строк. Соответственно, чем меньше сравнений производит машина, тем быстрее выполнится поиск. Назовем это "золотым правилом" регулярным выражений.


1. Вам это нужно?

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


2. Операция "ИЛИ"

Эту операцию я не упоминал в примерах. Данная операция позволяет задавать условие соответствия. Задается символом |. Последовательность символов будет соответствовать шаблону если она соответствует или одной или другой части шаблона. Примеры:
pattern1 = 'word1|word2|word3|word4'
pattern2 = '[abc|cde]'
pattern3 = '(VeryLongcase|shortcase)'
Сейчас нас больше всего интересует шаблон pattern3. С точки зрения оптимизации скорости выполнения он записан неправильно. Обработка регулярных выражений в Python ведется слева направо, а условия работают в сокращенной форме, то есть если первое выполняется - второе просто не будет проверятся. Итак, мы вычислили первую подсказку:
При использовании операции | располагать части регулярного выражения слева направо следует в порядке возрастания времени проверки каждого из них.


3. Неопределенные повторения

Рассмотрим повторения. Чем больше повторений - тем больше сравнений. Еще одна проблема машины регулярных выражений Python - рекурсивный бектрекинг. Рекурсивный бектрекинг - это алгоритм определения совпадений. Недостатком его является то, что он попробует как можно больше вариантов поиска перед тем как сдаться, но он прост в реализации, поэтому довольно популярен. Поэтому:
Нужно избегать неопределенных повторений - *, +, лучше пользоваться фиксированными ограничителями: {from, to}.


4. Ограничение области поиска

Ограничение области видимости заключается в том, чтобы как можно более сузить область строки, в которой ведется поиска, то есть заставить поиск провалиться как можно раньше, и не делать лишних проверок. Поэтому, следует пользоваться операциями, которые ограничивают область поиска:
Всегда, где этого возможно, нужно как можно сильнее сузить область поиска. Для этого следует использовать индикаторы начала и конца строки ^, $, а также префиксные и постфиксные ограничители.
Также сузить область поиска поможет предварительная обработка текста. Зачастую текст можно урезать в несколько раз, таким образом искать по гораздо меньшей стоке.


5. Компиляция

Об этом уже говорилось, но для порядка сформулируем в отдельную подсказку:
Если вы используете одно и то же регулярное выражения в программе несколько раз - скомпилируйте его с помощью re.compile и используйте скомпилированный вариант для поиска.


6. Множественные выражения

Иногда бывает так, что более очевидным вариантом решения задачи кажется создания
нескольких, 2-х и больше выражений вместо одного. В этом случае следует помнить, что будет выполняться столько же поисковых проходов по тексту. Поэтому:

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


7. Избегайте вложенных выражений

Изнутри машина регулярных выражений работает следующим образом: разбирает регулярное выражение на части и углубляется при сравнении. Данный пример абсолютно оторван от жизни, просто показывает, что нужно уменьшать количество вложенных циклов.
Пример: Есть строка с ценой товара, в которой нужно произвести поиск. Такое регулярное выражение работает правильно: '\b.11.$'.
Поиск ведется следующим образом:
  1. Поиск ведется до нахождения начала слова. Фиксируется.
  2. Дальше ищем единички.
  3. Ищем знак доллара.
  4. Если знак доллара не найден, возвращаемся на шаг 2 и опять ищем единички.
Даже если нет такого, слова, которое заканчивается на $, поиск будет вестить до потери пульса, пока не будет выполнен перебор всех вариантов. Соответственно время выполнения будет вычисляться как длина строки, в которой ищем, умножить на количество двойных единичек, умножить на количество слов.
Вывод: если убрать \b, который толком ничего не делает, и заменить это все дело на '^\S*11\S$' получим поиск с начала строки по символам, не содержащим пробел.
Следующая подсказка:
Избегайте вложенных циклов в регулярных выражениях.
В связи с этим еще одна подсказка:
Никогда не используйте неопределенно длинные повторения символов в начале строки, так как время выполнения будет расти экспоненциально от длины регулярного выражения.


8. Ищите только то, что вам нужно

Пример с тем ще злощасным \b. Нужно найти все слова в тексте. Можно написать так: '[\b\w]+', но достаточно '[\w]+'.
Ищите только то, что нужно, и удаляйте лишнее из регулярных выражений.


9. Группируйте с умом

Механизм группировки очень медленная часть машины регулярных выражений. Поэтому:
следует использовать их только там, где это действительно помогает и нужно в последующей обработке результатов поиска.
Пример:
"(123|456)" - медленно
"123|456"- быстро


Регулярные выражения в Python 3

Регулярные выражения в Python 3 работают точно так же, как и в 2.х. Единственное отличие в том, что отсутствует флаг re.UNICODE, а вместо него добавлен флаг re.ASCII, чтобы производить ascii-only matching. Ну, Python 3 у нас ведь весь такой юникодовый из себя, так что почему так сделали, думаю, пояснения не требуются.


Заключение

При отладке медленных регулярных выражений сильно помогает профилирование. Так что когда соврешенно неочевидно, что можно сделать, - следует запустить профайлер, и посмотреть все узкие места в коде. Особенно это важно при тестировании регулярных выражений. Старайтесь запускать профилирование на как можно больших строках, которые теоретически могут встретится в приложении. Из-за рекурсивной природы машины регулярных выражений в Python, на длинных строках можно получить самые неожиданные результаты, а оптимизация во многих случаях позволяет ускорить выполнение от нескольких часов до микросекунд.

16 комментариев:

  1. regex помер, но есть занятный модуль в PYPI: http://pypi.python.org/pypi/regex

    Это - продвинутая версия стандартного re.
    Насколько я знаю, опробованные там решения понемногу переносятся в стандарт.

    ОтветитьУдалить
  2. Да, у этого модуля есть ряд преимуществ (мультипоточность, расширенные возможности группировки, перекрывающиеся строки,и т.д.), вот только в неподготовленных руках может стать сущей катастрофой.

    Например, звездочки и плюсики в префиксных и постфиксных условиях могут заставить повесится даже Cray XTM =). Тут уж, как говорится, кто ищет, тот найдет.

    В подавляющем большинстве случаев стандартного re будет хватать с головой.

    ОтветитьУдалить
  3. Что-то на последнем pycon summit собирались с регулярками мутить. Посмотрим, что выйдет.

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

    А еще мне очень нравится boost::xperssive
    http://www.boost.org/doc/libs/1_46_1/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.introduction

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

    ОтветитьУдалить
  4. Интересная библиотечка. Правда к этой затее ставлюсь пока довольно пессимистично.

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

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

    Тут как и в любой оптимизации надо сначала грешить на себя, а потом уже на реализацию библиотеки.

    ОтветитьУдалить
  5. Я не о скорости. Как мне кажется, такая форма записи более удобна.

    ОтветитьУдалить
  6. > Как мне кажется, такая форма записи более удобна.

    С этим согласен. Их вариант гораздо более читабельный, чем нашенский.

    ОтветитьУдалить
  7. Очень добротно описано. особенно понравилось то, что все с примерами.
    Эту стать бы мне год назад прочесть =)

    ОтветитьУдалить
  8. Статья интересная, даже тем, кто уже знаком с предметом, а конкретно - секция про оптимизацию. Спасибо.

    Вот нашел опечатку:
    "Как видим, точка обозначает любой символ. Чтобы заставить регулярное выражение искать строчку '3.0' достаточно поставить перед точкой обратный слеш - '3.\0'."

    Если пишите, что надо ставить слеш перед точкой, то может его туда лучше поставить, а не перед 0?

    ОтветитьУдалить
  9. @kodx, спасибо, а опечатку подправлю.

    ОтветитьУдалить
  10. В задаче 7, в коде опечатка
    "result.append(pattern.search(line)).groups()"

    а должно быть

    "result.append(pattern.search(line).groups())"

    ОтветитьУдалить
  11. Опечатка:

    > Для этого следует добавлять после символа повторения ВОСКЛИЦАТЕЛЬНЫЙ знак.
    > Решение:
    ...
    > pattern = re.compile('".*?"')

    ОтветитьУдалить
  12. Спасибо, очень полезная статья.

    ОтветитьУдалить
  13. Спасибо, хорошо изложено, утянула в закладки.

    ОтветитьУдалить
  14. Уважаемый автор!
    Спасибо! Примеры подобраны и разжеваны здорово! Для людей которые только знакомятся с re(таким как я), очень полезно. Спасибо вам за проделанную работу!
    P.S. Лежит в закладках.

    ОтветитьУдалить
  15. Для превого ознакомления с модулем статья — верх ожидай, спасибо

    ОтветитьУдалить

В этом гаджете обнаружена ошибка