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

> SELECT avg(amount) FROM transfer;
65.125965782378
generated in 3850 seconds

А теперь представим, что показатель должен быть свежайшим, а записи в таблицу делаются каждую секунду, и за месяц их набираются миллионы. Или другие требования, но суть та же — агрегировать те же данные каждый раз очень затратно. Обычные базы данных не предлагают таких оптимизаций. Как быть?

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

Jeffrey Friedl

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

Отсюда:

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

это cтрока, задающая шаблон поиска подстрок в тексте.

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

Регулярные выражения имеют два основных направления применения:

• анализ и поиск в текстовых массивах
• проверка данных на соответствие шаблону

Область применения регулярных выражений очень широка. Вот несколько примеров:

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

Модуль re

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

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

• обычных символов (буквы, цифры)
• управляющих символов: ^ $ * + ? { } [ ] | ( )

Средства модуля 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.

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

Задача №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
Теория:

Для того, чтобы обозначить конец строки используется символ $, а для обозначения начала строки - ^. Для решения третьей подзадачи пример 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
Теория:

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

Решение:

---

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']

---

Задача №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: Поиск с повторениями

Задача: Найти все числа в тексте
Теория:

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

* - предшествующее выражение может повторяться 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]+ - заканчивается искомая строка числом

Задача № 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]* - идет любое количество цифер или цифер нет.
3. 3{2,4} - последовательность цифер 3 длиной от 2-х до 4-х символов
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.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)'

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

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

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

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

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

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

Об этом уже говорилось, но для порядка сформулируем в отдельную подсказку:

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

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

Иногда бывает так, что более очевидным вариантом решения задачи кажется создания

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

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

Поиск ведется следующим образом:

1. Поиск ведется до нахождения начала слова. Фиксируется.
2. Дальше ищем единички.
3. Ищем знак доллара.
4. Если знак доллара не найден, возвращаемся на шаг 2 и опять ищем единички.

Следующая подсказка:

Избегайте вложенных циклов в регулярных выражениях.

В связи с этим еще одна подсказка:

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

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

Ищите только то, что нужно, и удаляйте лишнее из регулярных выражений.

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

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

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

Пример:

"(123|456)" - медленно
"123|456"- быстро

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

Заключение

Пролог

Ускоряем Python-код

1. Цикл по числам от 100 до 999.
2. Внутренний цикл по числам от 100 до 999.
3. Если произведение переменных итерации внешнего и внутреннего цикла - палиндром и он больше предыдущего найденного - запоминаем его.
4. Получаем резульат.

Мой перевод статьи Гвидо ван Россума:

Меня тут в шутку спросили: смогу ли я отсортировать миллион 32-битных int'ов в 2 мегабайтах памяти на Питоне. Во время размышления, мне пришло в голову задействовать механизм ввода-вывода с использованием буферной памяти.

Вообще, это именно шуточный вопрос — одни только данные займут 4 мегабайта, при условии бинарного представления! Правда, можно пойти на хитрость — взять файл, содержащий миллион 32-битных int'ов. Как же отсортировать их, используя минимальное количество памяти? Это должна быть какая-то разновидность сортировки слиянием, в которой небольшие куски данных сортируются и записываются во временный файл, после чего происходит слияние временных файлов для получения окончательного результата.

Вот мое решение: