Posted by Eyal Schneider on May 21, 2009 Пакет java.util.regex додано до Java у версії 1.4. Це дуже потужний інструмент і потрібно стати майстром, щоб використовувати його правильно. Навіть коли
регулярний вираз вірний, він може працювати дуже повільно, якщо написано нерозумно. Продовжуйте читання, якщо хочете розібратися в проблемах або перегортайте сторінку до кінця, де знайдете 10 корисних рекомендацій щодо підвищення продуктивності регулярних виразів у Java.
Невже так повільно?
Припустимо, що ми хочемо вибрати тільки рядки, що містять послідовність символів "a" та "b". Вірне рішення може бути таким:
(a*b*)* Однак, якщо ви запустите вираз, наприклад, з рядком "aaaaaaaaaaaaaaaaaaaaaaaaaaaaax", то пройде кілька хвабон до завершення та рапорту про відсутність збігів! Звичайно, найкращим регулюванням в даному випадку буде:
(a|b)* Це витрачає менше мілісекунди на моїй машині при тому ж рядку. Очевидно, що тут є проблема з продуктивністю.
Чому так відбувається?
Як і більшість движків регекспів, Java використовує НКА (Недетерміновані Кінцеві Автомати) підхід. Двигун сканує компоненти регулювання один за одним і просувається по вхідному рядку відповідним чином. І він може повернутися назад на початок, щоб знайти відповідні альтернативи якщо зайде в "глухий кут". Альтернативні результати виходять при використанні регулярних структур, таких як квантифікатори (
*, +, ? ) і чергування (наприклад
a | b | c | d ). Така техніка дослідження називається поверненням (backtracking). У страшному прикладі вище двигун насправді буде переглядати ВСІ розкладання серії символу "a" на менші серії поки не зрозуміє, що збігів немає. Цей приклад показує, як алгоритм повернення може призвести до експоненційної оцінки часу (залежно від довжини вхідного рядка). Це також показує важливу властивість НКА: завжди будуть гірші випадки, які майже відповідають шаблону. Якщо знайдено відповідність пошук зупиняється. Інший основний підхід для використання у регулярках це ДКА (Детермінований Кінцевий Автомат). У цьому підході регулярний вираз фактично будує автомат, який використовується для проходження вхідними рядками символ за символом без повернення. Це дає лінійний час весь вхід, незалежно від складності регулярного висловлювання. Замість послідовного дослідження рядка у пошуках збігів (як у НКА), ДКА симулює паралельне сканування. Так чому ж Java (і .NET, Perl, Python, Ruby, PHP та ін) використовують НКА а не ДКА у якого набагато краща поведінка? Причина в тому, що НКА має низку істотних переваг:
- Компілюється швидше і вимагає набагато меншої кількості пам'яті
- Дозволяє використовувати деякі корисні функції (докладніше дивіться у Sun's tutorial ):
- Захоплення групи та зворотні посилання
- Позиційна перевірка
- Розширені квантифікатори (Жадібний і Лінивий)
Важливо, що популярні терміни НКА та ДКА при використанні в контексті регулярок є неточними. Теоретично ці дві моделі мають однакову потужність обчислень. Це означає, що не можна написати таке регулярне вираження в одній моделі автоматів, яке було б неможливо виразити в іншій. На практиці існує необхідність у більшій кількості можливостей так, що два типи реалізації розійшлися у семантиці. НКА двигуни дають більше гнучкості роблячи їх переважаючими перед ДКА обчислювальної потужності. Завдяки швидкості ДКА та унікальним особливостям НКА є ще 2 "збірні" способи реалізації регулярних виразів. Деякі реалізації використовують обидва типи (наприклад GNU egrep, який вибирає конкретний двигун під час виконання), а деяким вдалося реалізувати дійсно гібридну версію (наприклад, регекспи в Tcl) з усіма перевагами.
Поради
Наступні кілька порад про те, як уникнути проблем з ефективністю регулярок Java. Багато хто з них спрямований на зниження повернень.
1) Попередня компіляція
Банально, але варто згадати. Якщо ви використовуєте регекс не раз не забудьте скомпілювати його заздалегідь:
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2) Ліниві квантифікатори проти Жадібних квантифікаторів
За замовчуванням квантифікатори (
* + ? ) жадібні. Це означає, що вони починають зіставлення з найбільш довгою можливою послідовністю і потім поступово повертаються, якщо необхідно. Якщо ви заздалегідь знаєте, що збіги будуть, як правило, короткі, ви повинні використовувати ліниві квантифікатори. Вони починають з найменшого збігу і рухаються далі, якщо треба. Припустимо ми хочемо знайти лише рядки відповідні послідовності "hello". Регулярка
.*hello.* зробить все правильно, але якщо ми знаємо, що "hello" зазвичай з'являється ближче до початку тексту, тоді
.*?hello.* у середньому працюватиме швидше.
3) Використовуйте наджадібні квантифікатори де можливо
На відміну від лінивих квантифікаторів, які впливають на продуктивність, але не впливають на регулярну поведінку, над жадібні квантифікатори можуть дійсно змінити сенс регулярного вираження. Коли використовується
*+ замість
* , то перший збіг буде жадібним (тобто найбільше можливе так, ніби це просто *), але не буде відкату у разі невдачі , навіть якщо це викличе невідповідність всього пошуку. Коли це може бути корисним? Припустимо, нам потрібно знайти текст у лапках. Регулярка
\"[^\"]*\" відпрацює нормально. Проте вона буде робити непотрібний відступ у негативних випадках (наприклад. “bla bla bla” )
. сенс висловлювання. Незалежне угруповання (Independent grouping) дозволяє досягти того самого ефекту, і дає ще більше контролю (див.
Sun's tutorial ).
4) Уникайте захоплення групи
Будь-який вираз у дужках за замовчуванням вважається групою. Це має невеликий вплив на продуктивність. Робіть ваші групи "незахоплюваними", коли можливо, починаючи їх з
(?: замість
( ) .
5) Розумне використання чергування
Коли використовується чергування (наприклад
Paul|Jane|Chris ), порядок в якому двигун намагається зіставити варіанти такий самий як і в порядку перерахування, в якому вони з'являються. Ви можете скористатися цією особливістю та розташувати найбільш поширені варіанти ближче до початку. Це покращить середній час позитивних спрацьовувань.
6) Уникайте багатозначності
Пишіть регекспи таким чином, щоб мінімізувати кількість різних відповідностей у вхідному рядку. Для прикладу: регулярка
(a*b*)* дана на початку статті, дозволяє інтерпретувати рядок "aabb" дуже багатьма способами:
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Регексп
(a|b)* з іншого боку позитивно інтерпретує лише унікальні комбінації. Це дуже важливо для зменшення повернень у випадках
майже збігу.
7) Передпрогляд
Попередній перегляд дозволяє додати обмеження на послідовності зліва/праворуч від поточної позиції. Зокрема з негативним переглядом можна шукати рядки, які не містять певної послідовності (що б ми без цього робабо!). Як це допоможе збільшити продуктивність? Припустимо ми хочемо взяти URL-адресау з тега посилання. Розглянемо наступний регекс:
a .* href=(\S*).*/ Для звичайних тегів цей вираз знайде адресау тільки якщо в тексті буде атрибут "href" (\S використовується для всіх символів крім роздільників) . Але на деяких незвичайних тегах, наприклад, відбудеться відкат. Наприклад: “a href= href=href=…. href = something”. Наступний регекс запобіжить це при заміні “.*” у виразі на щось, що не відповідає "href":
a ((?!href).)* href=(\S*)((?!href).)*/
8) Вкажіть довжину
Java містить регексп оптимізатор, який перевіряє довжину вхідного рядка проти мінімального та максимальних довжин отриманих з регулярного виразу. Це дозволяє припиняти пошук одразу в деяких випадках. Для того, щоб допомогти цьому механізму, слід по можливості вказувати число повторень (наприклад
[01]{6} , відповідає всім двійковим рядкам довжиною в шість символів).
9) Виділіть однакові рядки
Іноді рядки, які є однаковими приховані всередині груп або альтернатив:
(hello|hell|heel) Цей вираз може бути спрощено до:
he(llo|ll|el) Роблячи так ми даємо регекс оптимізатор більше інформації.
10) Тестуйте ваш регексп
Напевно, це буде мудрим, спочатку тестувати регулярне вираження, коли воно буде використовуватися в критично важливому до продуктивності додатку. Напишіть мікро-бенчмарк який протестує ваше вираження на різних вхідних даних. Не забудьте перевірити дані різної довжини, а також дані, які майже відповідають вашому зразку.
Посилання:
http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Expression-Processing/
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ