17
правок
Изменения
м
[[ https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez ]] реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
fix
==== Позиция внутри строки ====
Следующие символы позволяют спозиционировать регулярное выражение относительно элементов текста: начала и конца строки, границ слова.
{| class="wikitable"
! Представление
! Позиция
|-
| ^
| Начало текста
|-
| $
| Конец текста
|-
| \b
| Граница слова
|-
| \G
| Предыдущий успешный поиск
|}
==== Жадная и ленивая квантификация ====
| {n,}
| {n,}?
|}
Эту проблему можно решить двумя способами.
Учитывать символы, не соответствующие желаемому образцу (<[^>]*> для вышеописанного случая).
Определить квантификатор как нежадный (ленивый, англ. lazy) — большинство реализаций позволяют это сделать, добавив после него знак вопроса.
==== Ревнивая квантификация (Сверхжадная) ====
В отличие от обычной (жадной) квантификации, ревнивая (possessive) квантификация не только старается найти максимально длинный вариант, но ещё и не позволяет алгоритму возвращаться к предыдущим шагам поиска для того, чтобы найти возможные соответствия для оставшейся части регулярного выражения.
Использование квантификаторов увеличивает скорость поиска, особенно в тех случаях, когда строка не соответствует регулярному выражению. Кроме того, ревнивые квантификаторы могут быть использованы для исключения нежелательных совпадений.
{| class="wikitable"
! Жадный
! Ревнивый
|-
| *
| *+
|-
| ?
| ?+
|-
| +
| ++
|-
| {n,}
| {n,}+
|}
== Несколько полезных оптимизаций на примере Haskell ==
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
* использовал Word вместо Integer, ещё в 8 раз быстрее
