|
|
|||||
Регистрация: Jul 2011
Сообщений: 67
|
Скорость регулярных выражений
iNils: Эта тема выделилась из темы: Округление числа с двумя запятыми
Хммм ну что касается скорости регулярных выражений, то это очень нетривиальная вещь. Во первых бывают разные механизмы регулярок: дка и нка ((не)детерминированный конечный автомат). дка всегда, независимо от написания выражения работает очень быстро, но уступает нка в возможностях. нка же очень зависит о самого выражения, используемых в нём конструкций, например (н|к|а) будет работать в разы медленнее чем [нка] и т.д. , а дка это без разницы, он один раз строит карту символов по которой и бегает. Зато нка легко поддерживает возможности ссылок, сохранения участков совпадения, опережающих и ретроспективных проверок и другие няшечки, без которых некоторые задачи ни как не решить. Сам нка делится ещё на классический нка, который при первом совпадении выдаёт результат. И на POSIX нка, который продолжает перебирать текст пока не найдёт самое длинное совпадение, естественно он работает ещё медленнее чем нка. Так-же кажется существуют гибридные механизмы, которые и рыбку съесть хотят и работать быстро, не знаю насколько успешно. В AS 3.0 используется обычный нка без извращений. Мораль: если регулярка работает медленно, это вы виноваты, а не регулярка. Последний раз редактировалось iNils; 16.01.2012 в 18:26. |
|
||||||
Регистрация: Nov 2010
Сообщений: 497
|
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
|
|
|||||
Регистрация: Jul 2011
Сообщений: 67
|
Хм вы действительно заставили меня усомниться, т.к. я естественно не обладаю исчерпывающими знаниями в этой области, и даже напротив. Ну давайте тогда разбираться в вопросе вместе:
Цитата:
var str:String = 'zzznkankankankanka'; var i:int = 0; var t:Number; var len:int = 1000000; t = new Date().getTime(); for(i = 0; i<len; i++) test_1(str); trace("test_1", new Date().getTime() - t); t = new Date().getTime(); for(i = 0; i<len; i++) test_2(str); trace("test_2", new Date().getTime() - t); private function test_1(str:String):void { str.replace(/(n|k|a)/g,''); } private function test_2(str:String):void { str.replace(/[nka]/g,''); } //test_1 21000 //test_2 10645 Привык думать что конструкция выбора и символьный класс совсем разные вещи. Цитата:
Цитата:
Цитата:
Вообще я просто хотел сказать, что регулярка в AS3 может работать медленно из-за того, что выражение построено не оптимально при верной его (выражения) идее. |
|
|||||
Регистрация: Nov 2010
Сообщений: 497
|
И что эти тесты покажут? Они тестируют реализацию регулярных выражений, которая не использует ни нка, ни дка. Поэтому эти тесты про дка и нка ничего не скажут. Постройте автоматы руками и все сразу станет видно.
Цитата:
Цитата:
Цитата:
Цитата:
|
|
|||||||||
Регистрация: Jul 2011
Сообщений: 67
|
Цитата:
test_1 16241 test_2 9531 Цитата:
\/ Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
|
|
|||||
Регистрация: Nov 2010
Сообщений: 497
|
Цитата:
Цитата:
Цитата:
Это было доказательство для дка. нка нужно предварительно перевести в дка. Вроде бы по сссылке (которую я давал в wiki) было написано, как это делается. В крайнем случае там должна была быть ссылка на литературу. Вывод - если что-то успешно обрабатывает регулярные выражения и корректно работает с backreferences, оно не является конечным автоматом. Ну а использовать нка при разборе регулярного выражения смысла нет. Как минимум, некоторые вещи в автомате не представимы. А все остальное, что остается от нка, нормально представляется "позициями" в регулярном выражении + состоянием разбора. И, кстати, это как раз и может давать разницу в производительности для двух эквивалентных грамматик . А использование нка его давать не должно. Цитата:
|
|
||||||
Регистрация: Jul 2011
Сообщений: 67
|
Цитата:
Цитата:
Вот страничка от туда например: (надеюсь не нарушаю ни каких правил здешних) Меня обманули получается? Ох уж эти орейли, а я им так верил, так верил. Цитата:
Цитата:
Цитата:
Последний раз редактировалось iNils; 21.02.2013 в 20:25. |
|
|||||
Регистрация: Nov 2010
Сообщений: 497
|
Я от вас так и не получил ответа о том, что вы понимаете под нка/дка.
Цитата:
Цитата:
Теперь по применимости. Да. И, кстати, правильно пишут. Большая часть причин - технические причины, которые делают очень невыгодной детерминизацию нка. А последняя причина - это совершенно отдельный класс автоматов - "нка с выходом". Это совсем не то же, что подразумевается под "обычным нка" (опять же, без контекста). Цитата:
|
|
|||||
Регистрация: Jul 2011
Сообщений: 67
|
Ок. Тесты вам ни чего не показывают. Книга врёт. Замечательно. Ни нка ни дка ни где не используются, их судя по всему вообще не существует. Что используется тогда? Как называется механизм, который используется в регулярных выражениях?
Вот вам ещё ссылка: http://lipetsk.lug.ru/projects/re/re...l#theorysearch Но она тоже наверное врёт, там-же цитируют Фридла. Последний раз редактировалось ProxyGreen; 16.01.2012 в 20:27. |
Часовой пояс GMT +4, время: 19:45. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|