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

в 20:31, , рубрики: .net, C#, data mining, ORegex, pattern matching, regex, метки:

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 движки. Если же задача стоит быстро, просто и понятно найти шаблон в последовательности объектов (геном в последовательности генов, простые сущности в словах, объект в дампе памяти и т.д.), то такие различия в скорости на мой взгляд вполне допустимы.
На этом все. Спасибо за внимание и терпение! =)

Автор: eocron

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js