Как стать автором
Обновить

ORegex: Достаточно ли быстро для объектов?

Время на прочтение 3 мин
Количество просмотров 7.8K

image


Добрый вечер, хабражители! Сегодня хочу поделиться небольшими перфоманс оценками ORegex .NET.
Если вы читали мою предыдущую статью здесь, то на мой взгляд было не очень убедительно представлять что-то без сравнительной оценки скорости, Вы так не считаете? Если да, то Вам под кат.


Долго думал над тем, что же включить в бенчмарк, чтобы долго себя не мучить. Не хотелось тратить на это много времени/сил, а так как фантаст и писатель из меня ну совсем никудышный, решил взять самое простое сравнение — поиск подстроки в тексте. На мой взгляд для перфоманс теста это самое лучшее решение, ведь символ тоже объект. Стоит заметить, что весь код присутствует в тестовом проекте на гит-хабе, можете запустить если Вам ну совсем делать нечего =)


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


  1. Реальность (Распарсить html теги, хорошая практическая проверка на сильно структурированные данные)
  2. Рандом (Как у них с нахождением вхождений в совершенно случайный набор данных)
  3. Ошибка (Никто не отменял backtracking, поэтому нужно взглянуть на наборы в которых очень обманчивые данные)

Реальность


Была выбрана страничка с новостного сайта и задана задача найти все p теги на 20 итерациях. Как и следовало ожидать — Regex впереди. Оба инструмента в начальной итерации показали примерно одинаковые результаты холодного старта. После первой итерации разность в скоростях различалась примерно в 10 раз:


ORegex pattern: {b1o}{p}{b1c}.*?{b1o}{slash}{p}{b1c}; Regex pattern: <p>.*?</p>


ORegex Regex Ratio
1 00:00:00.0040204 00:00:00.0058571 1,46
2 00:00:00.0030944 00:00:00.0003172 0,1
3 00:00:00.0032093 00:00:00.0003195 0,1
4 00:00:00.0031040 00:00:00.0003172 0,1
5 00:00:00.0032354 00:00:00.0003149 0,1
6 00:00:00.0031703 00:00:00.0003153 0,1
7 00:00:00.0031220 00:00:00.0003187 0,1
8 00:00:00.0030883 00:00:00.0003187 0,1
9 00:00:00.0036790 00:00:00.0003674 0,1
10 00:00:00.0030902 00:00:00.0003145 0,1
11 00:00:00.0030787 00:00:00.0003130 0,1
12 00:00:00.0030752 00:00:00.0003149 0,1
13 00:00:00.0030975 00:00:00.0003183 0,1
14 00:00:00.0032250 00:00:00.0003777 0,12
15 00:00:00.0031166 00:00:00.0003179 0,1
16 00:00:00.0030852 00:00:00.0003141 0,1
17 00:00:00.0031178 00:00:00.0003160 0,1
18 00:00:00.0030913 00:00:00.0003160 0,1
19 00:00:00.0030787 00:00:00.0003133 0,1
20 00:00:00.0030818 00:00:00.0003118 0,1

Рандом


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


ORegex pattern: {a}({b}{a})+; Regex pattern: a(ba)+


ORegex Regex Ratio
1 00:00:00.1785877 00:00:00.0622146 0,35
2 00:00:00.2141055 00:00:00.0578735 0,27
3 00:00:00.2148457 00:00:00.0539055 0,25
4 00:00:00.1984781 00:00:00.0499280 0,25
5 00:00:00.2073454 00:00:00.0634693 0,31
6 00:00:00.1592644 00:00:00.0842834 0,53
7 00:00:00.2167805 00:00:00.0527719 0,24
8 00:00:00.2012316 00:00:00.0511291 0,25
9 00:00:00.1928555 00:00:00.0504931 0,26
10 00:00:00.1887427 00:00:00.0546691 0,29
11 00:00:00.1663168 00:00:00.0741461 0,45
12 00:00:00.1628335 00:00:00.0742250 0,46
13 00:00:00.2077626 00:00:00.0481913 0,23
14 00:00:00.1709487 00:00:00.0501648 0,29
15 00:00:00.1869102 00:00:00.0477373 0,26
16 00:00:00.2173555 00:00:00.0629728 0,29
17 00:00:00.1897196 00:00:00.0495571 0,26
18 00:00:00.1939370 00:00:00.0494173 0,25
19 00:00:00.2249846 00:00:00.0479044 0,21
20 00:00:00.2037242 00:00:00.0815932 0,4

В данном случае отставание ORegex от Regex лишь примерно в три раза.


Ошибка


Чтож, на данный момент ясно, что ORegex проигрывает в нахождении символьных последовательностей в сильно структурированных данных и случайных наборах, но как насчет ошибочных случаев? Тест простой, насколько два инструменты bactracking-пруфф. Для этого был задан специальный шаблон, а размер строки из одних 'x' постепенно увеличивался на 150 символов, в итоге при третьей итерации, Regex отстал практически в 30 раз:


ORegex pattern: {x}+{x}+{y}+; Regex pattern: x+x+y+


ORegex Regex Ratio
1 00:00:00.0082144 00:00:00.0094231 1,15
2 00:00:00.0005045 00:00:00.0064406 12,76
3 00:00:00.0114383 00:00:00.3322330 29,05

Итоги


Подводя итоги, хочу сказать, что конечно же, использовать для поиска подстроки данный инструмент неразумно и глупо. Для этого есть более быстрые regex движки. Если же задача стоит быстро, просто и понятно найти шаблон в последовательности объектов (геном в последовательности генов, простые сущности в словах, объект в дампе памяти и т.д.), то такие различия в скорости на мой взгляд вполне допустимы.
На этом все. Спасибо за внимание и терпение! =)

Теги:
Хабы:
+9
Комментарии 17
Комментарии Комментарии 17

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн