ORegex: Достаточно ли быстро для объектов?
Добрый вечер, читатели! Сегодня хочу поделиться небольшими перфоманс оценками ORegex .NET.
Если вы читали мою предыдущую статью здесь [1], то на мой взгляд было не очень убедительно представлять что-то без сравнительной оценки скорости, Вы так не считаете? Если да, то Вам под кат.
Долго думал над тем, что же включить в бенчмарк, чтобы долго себя не мучить. Не хотелось тратить на это много времени/сил, а так как фантаст и писатель из меня ну совсем никудышный, решил взять самое простое сравнение — поиск подстроки в тексте. На мой взгляд для перфоманс теста это самое лучшее решение, ведь символ тоже объект. Стоит заметить, что весь код присутствует в тестовом проекте на гит-хабе [2], можете запустить если Вам ну совсем делать нечего =)
Мы имеем ORegex и Regex движок от Microsoft, все что нужно это описать схожие паттерны для обеих сторон, ну и лямбды на каждый символ для ORegex, и надо не забыть придумать тестовые кейзы. Долго думать не пришлось, было решено посмотреть, как инструменты справятся с тремя задачами:
- Реальность (Распарсить html теги, хорошая практическая проверка на сильно структурированные данные)
- Рандом (Как у них с нахождением вхождений в совершенно случайный набор данных)
- Ошибка (Никто не отменял 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 движки. Если же задача стоит быстро, просто и понятно найти шаблон в последовательности объектов (геном в последовательности генов, простые сущности в словах, объект в дампе памяти и т.д.), то такие различия в скорости на мой взгляд вполне допустимы.
На этом все. Спасибо за внимание и терпение! =)
Автор: eocron
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-2/152912
Ссылки в тексте:
[1] здесь: https://habrahabr.ru/post/278219/
[2] гит-хабе: https://github.com/eocron/ORegex
[3] Источник: https://habrahabr.ru/post/305256/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.