Перейти до основного вмісту

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

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

Що це таке?

Рано чи піздно майже кожному програмісту в своєму житті доводиться стикатись з регулярними виразами.
Термін "Регулярні вирази" є перекладом з англійської словосполучення "Regular expressions" і не є зовсім точним, а для тих, хто перший раз почув цей термін, мабуть, навіть спантеличуючим (я, наприклад, коли вперше почув, ніяк не міг собі второпати по назві, хоча б приблизно, що це, і для чого використовується).
Літературний і більш осмислений переклад звучав би, мабуть, як "шаблонні вирази". Але назва вже прижилась, а скажете "шаблонні вирази" - вас просто не зрозуміють :).

Звідси:
Регулярний вираз - це рядок, що задає шаблон пошуку під-рядків в рядку.

Регулярні вирази використовуються для аналізу текстів на предмет відповідності текстової інформації деякому шаблону. Наприклад, шаблон, що задає слово, яке містить букву "к".

Де застосовуються регулярні вирази?

Регулярні вирази мають два основних напрямки застосування:
  • аналіз і пошук в текстових масивах
  • перевірка даних на відповідність шаблону
Сфера застосування регулярних виразів дуже широка. Ось декілька прикладів:
  • аналіз логів додатків
  • пошук і вибірка інформації з баз даних, організованих як прості текстові файли
  • 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 times faster code if we add about 340 lines of code
Задача: Знайти всі тризначні числа в тексті, які починаються на цифру 3 і закінчуються на 0.

Теорія:

Для того, щоб вказати, що в рядку може знаходитись будь-який символ (кріме символу нового рядка) потрібно використати крапку - . . Щоб враховувася і символ нового рядка необхідно встановити прапорець (але про це пізніше).

Розв'язок:
string = 'We can get 300 to 540 times 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, на довгих рядках можна отримати набільш неочікувані результати, а оптимізація в багатьох випадках дозволить прискорити виконання від декількох годин до мікросекунд.

Коментарі

  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. Для превого ознакомления с модулем статья — верх ожидай, спасибо

    ВідповістиВидалити

Дописати коментар

Популярні дописи з цього блогу

Python: як програмно перемкнути розкладку клавіатури в Windows

Дослідивши дане питання, я побачив, що Python не має засобів "з коробки" для вирішення цієї задачі. Відвоідно, задача повинна вирішуватись для каждої ОС своїм шляхом. Дане рішення було знайдено мною для ОС Windows XP +. Панацея - Win API Для того, щоб виконати завдання необхідно встановити додатково бібліотеку pywin32 , яка надає доступ до функцій Windows API з Python. З цієї бібліотеки нам знадобиться модуль win32api . >>> import win32api Дослідивши його вміст, можна побачити, що для роботы з розкладкою клавіатури є декілька функцій і одне системне повідомлення Windows - WM_INPUTLANGCHANGE : GetKeyboardLayout GetKeyboardLayoutList LoadKeyboardLayout В даному випадку для нас важлива саме остання функція - LoadKeyboardLayout . Дана функція завантажує нову розкладку (якщо вона ще не завантажена) і виконує після цього ще якісь дії; приймає в якості аргументів два: рядок з ідентифікатором розкладки. дію. Більш детально про їхні можливі значення можна почитати в MSDN . О

Python: PEP-8 чи не PEP-8

Пост - не технічний, кому не цікаво - можете далі не читати... PEP-8, хоча й фактично є пропозицією по розширенню Python під номером 8, серед Python програмістів уже став терміном, що позначає правила стилю оформлення коду. Ні, я не збираюсь зараз описувати його тут - про нього можна почитати в першоджерелі . Питання в тому, слідувати цьому стандарту, чи не слідувати? Ітак, стандарт це в більшості випадків добре, оскільки вносить порядок. Наприклад, стандарт USB 2.0 - просто прекрасний стандарт, уявіть собі, якби флешки були не USB, а кожна мала б свій вихід :)... Жахливо, так, були б у нас USB-порти як card-reader'и - 62 в 1.. Реально 62 в 1 Інша справа з PEP-8. Тут все по іншому, адже програма не змінює свою поведінку, якщо ми будемр робити відступ не в 4 пробіла, а 2 (добре, що більшість, все-таки, робить 4), або будемо ставити пробіл перед другою дужкою, чи не будемо і т.д..  Отже, кожен програміст може редагувати свій код як йому хочеться. Мені, наприклад, подобається