Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 14.01.2012, 09:38
ProxyGreen вне форума Посмотреть профиль Отправить личное сообщение для ProxyGreen Найти все сообщения от ProxyGreen
  № 1  
Ответить с цитированием
ProxyGreen
 
Аватар для ProxyGreen

Регистрация: Jul 2011
Сообщений: 67
Question Скорость регулярных выражений

iNils: Эта тема выделилась из темы: Округление числа с двумя запятыми

Хммм ну что касается скорости регулярных выражений, то это очень нетривиальная вещь. Во первых бывают разные механизмы регулярок: дка и нка ((не)детерминированный конечный автомат). дка всегда, независимо от написания выражения работает очень быстро, но уступает нка в возможностях. нка же очень зависит о самого выражения, используемых в нём конструкций, например (н|к|а) будет работать в разы медленнее чем [нка] и т.д. , а дка это без разницы, он один раз строит карту символов по которой и бегает. Зато нка легко поддерживает возможности ссылок, сохранения участков совпадения, опережающих и ретроспективных проверок и другие няшечки, без которых некоторые задачи ни как не решить. Сам нка делится ещё на классический нка, который при первом совпадении выдаёт результат. И на POSIX нка, который продолжает перебирать текст пока не найдёт самое длинное совпадение, естественно он работает ещё медленнее чем нка. Так-же кажется существуют гибридные механизмы, которые и рыбку съесть хотят и работать быстро, не знаю насколько успешно. В AS 3.0 используется обычный нка без извращений.
Мораль: если регулярка работает медленно, это вы виноваты, а не регулярка.


Последний раз редактировалось iNils; 16.01.2012 в 18:26.
Старый 14.01.2012, 22:12
maxkar вне форума Посмотреть профиль Отправить личное сообщение для maxkar Найти все сообщения от maxkar
  № 2  
Ответить с цитированием
maxkar

Регистрация: Nov 2010
Сообщений: 497
Цитата:
Сообщение от ProxyGreen Посмотреть сообщение
Во первых бывают разные механизмы регулярок: дка и нка ((не)детерминированный конечный автомат).
И те и другие используются только для автоматных грамматик. Грамматики с back references - это другой класс грамматик и никакими нка не разбираются.
Цитата:
дка всегда, независимо от написания выражения работает очень быстро, но уступает нка в возможностях.
Это неправда. По нка достаточно легко сторится полностью эквивалентный ему дка.
Цитата:
нка же очень зависит о самого выражения, используемых в нём конструкций, например (н|к|а) будет работать в разы медленнее чем [нка] и т.д.
Не будет. Они будут работать одинаково. Эти две грамматики вообще эквивалентны и автоматы для них будут одинаковы. Более того, если проверять строку на совпадение (а не для поиска подстроки), то даже будут совпадать автоматы для нка и дка.
Цитата:
Зато нка легко поддерживает возможности ссылок, сохранения участков совпадения, опережающих и ретроспективных проверок и другие няшечки, без которых некоторые задачи ни как не решить.
И опять не нка. backreferences не обрабатываются НКА (в классическом определении НКА). В большинстве движков регулярных выражений не конечный автомат.
Цитата:
Сам нка делится ещё на классический нка, который при первом совпадении выдаёт результат. И на POSIX нка, который продолжает перебирать текст пока не найдёт самое длинное совпадение, естественно он работает ещё медленнее чем нка.
Не, это не нка делится . Конечный автомат - это вполне определенная штука. Ну и в силу определения нка дольше него грамматику разбирать нельзя. Он и так все возможные разборы строки генерирует стразу. Выбрать самое длинное из его результатов - мелочи.

Старый 15.01.2012, 12:33
ProxyGreen вне форума Посмотреть профиль Отправить личное сообщение для ProxyGreen Найти все сообщения от ProxyGreen
  № 3  
Ответить с цитированием
ProxyGreen
 
Аватар для ProxyGreen

Регистрация: Jul 2011
Сообщений: 67
Хм вы действительно заставили меня усомниться, т.к. я естественно не обладаю исчерпывающими знаниями в этой области, и даже напротив. Ну давайте тогда разбираться в вопросе вместе:

Цитата:
Не будет. Они будут работать одинаково. Эти две грамматики вообще эквивалентны и автоматы для них будут одинаковы. Более того, если проверять строку на совпадение (а не для поиска подстроки), то даже будут совпадать автоматы для нка и дка.
Хм я позволил себе провести некоторые тесты:
Код AS3:
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
Ну совершенно ни какой разницы нет )
Привык думать что конструкция выбора и символьный класс совсем разные вещи.

Цитата:
Конечный автомат - это вполне определенная штука. Ну и в силу определения нка дольше него грамматику разбирать нельзя. Он и так все возможные разборы строки генерирует стразу. Выбрать самое длинное из его результатов - мелочи.
Различия между "обычной" и POSIX реализациями в том, что обычная прекратит разбор при первом совпадении, "POSIX" будет шпарить до конца, в буквальном смысле, даже переберёт все варианты в конструкциях выбора даже если совпадение найдено в первом варианте, ну это мелочи конечно, ни чего существенного.

Цитата:
Это неправда. По нка достаточно легко сторится полностью эквивалентный ему дка.
Вот это я не понял про что вы вообще.

Цитата:
И опять не нка. backreferences не обрабатываются НКА (в классическом определении НКА). В большинстве движков регулярных выражений не конечный автомат.
И опять что это тогда? Что за "движки", что за механизмы? Огласите весь список пожалуйста.

Вообще я просто хотел сказать, что регулярка в AS3 может работать медленно из-за того, что выражение построено не оптимально при верной его (выражения) идее.

Старый 15.01.2012, 18:45
wvxvw вне форума Посмотреть профиль Отправить личное сообщение для wvxvw Найти все сообщения от wvxvw
  № 4  
Ответить с цитированием
wvxvw
Modus ponens
 
Аватар для wvxvw

модератор форума
Регистрация: Jul 2006
Адрес: #1=(list #1#)
Сообщений: 8,049
Записей в блоге: 38
Не проверяя, а что будет если (?:x|y|z) вместо (x|y|z) - во втором случае нужно же еще и ссылку где-то хранить...
__________________
Hell is the possibility of sanity

Старый 15.01.2012, 20:46
maxkar вне форума Посмотреть профиль Отправить личное сообщение для maxkar Найти все сообщения от maxkar
  № 5  
Ответить с цитированием
maxkar

Регистрация: Nov 2010
Сообщений: 497
Цитата:
Сообщение от ProxyGreen Посмотреть сообщение
Хм я позволил себе провести некоторые тесты:
И что эти тесты покажут? Они тестируют реализацию регулярных выражений, которая не использует ни нка, ни дка. Поэтому эти тесты про дка и нка ничего не скажут. Постройте автоматы руками и все сразу станет видно.

Цитата:
Различия между "обычной" и POSIX реализациями в том, что обычная прекратит разбор при первом совпадении, "POSIX" будет шпарить до конца, в буквальном смысле, даже переберёт все варианты в конструкциях выбора даже если совпадение найдено в первом варианте, ну это мелочи конечно, ни чего существенного.
Да, это особенности реализации регулярных выражений. Тех самых, которые в языках программирования. И к нка/дка они имеют слабое отношение. Нка/дка строятся для "регулярных выражений" из computer science, но так регулярные выражения как раз ограничены в своих возможностях.

Цитата:
Вот это я не понял про что вы вообще.
Ну как о чем? О конечных автоматах. Это ведь то, что описывается
  • Набором состояний
  • Алфавитом
  • Начальным состоянием
  • Функциями перехода
  • Множеством конечных состояний
нка и дка отличаются только ограничениями на функции перехода и легко преобразуются друг в друга.

Цитата:
И опять что это тогда? Что за "движки", что за механизмы? Огласите весь список пожалуйста.
А я откуда знаю, какие вообще библиотеки есть для regex'ов? Вообще, есть pcre (и вроде бы даже в виде библиоетки). Есть конечные автоматы для классических регулярных выражений из Computer Science. Ну и практически в каждом языке есть реализация своих вариантов регулярных выражений, отличающихся по разным параметрам.

Цитата:
Вообще я просто хотел сказать, что регулярка в AS3 может работать медленно из-за того, что выражение построено не оптимально при верной его (выражения) идее.
Ну да, правильно. Поэтому и говорят, что регулярные выражения медленные. А то, что они в каком-то случае быстрые ничего не говорит. Может, в следующей версии регулярные выражения расширят (или оптимизируют некоторые случаи) и то, что работало быстро, станет работать медленно.

Старый 15.01.2012, 23:58
ProxyGreen вне форума Посмотреть профиль Отправить личное сообщение для ProxyGreen Найти все сообщения от ProxyGreen
  № 6  
Ответить с цитированием
ProxyGreen
 
Аватар для ProxyGreen

Регистрация: Jul 2011
Сообщений: 67
Цитата:
Не проверяя, а что будет если (?:x|y|z) вместо (x|y|z) - во втором случае нужно же еще и ссылку где-то хранить...
А ну да без скобок, так получается:
test_1 16241
test_2 9531

Цитата:
И что эти тесты покажут?
||
\/
Цитата:
нка же очень зависит о самого выражения, используемых в нём конструкций, например (н|к|а) будет работать в разы медленнее чем [нка] и т.д.
Цитата:
которая не использует ни нка, ни дка
Успешно использует нка и имеет уважение.

Цитата:
Да, это особенности реализации регулярных выражений.
Чёрт возьми да. Да это про особенности. Они то нам и важны. Каждый день мы сталкиваемся именно с особенностями, самой конкретной, самой материальной реализации, а не со схемкой в википедии.

Цитата:
А я откуда знаю, какие вообще библиотеки есть для regex'ов?
Как вы тогда определили что:
Цитата:
. В большинстве движков регулярных выражений не конечный автомат.
Как вы это определили интересно знать?

Цитата:
и то, что работало быстро, станет работать медленно.
Шутку понял. Смешно.

Старый 16.01.2012, 00:40
maxkar вне форума Посмотреть профиль Отправить личное сообщение для maxkar Найти все сообщения от maxkar
  № 7  
Ответить с цитированием
maxkar

Регистрация: Nov 2010
Сообщений: 497
Цитата:
Успешно использует нка и имеет уважение.
Дайте, пожалуйста, ваше определение нка. И расскажите, как именно разбор регулярных выражений ими пользуется. Особенно с учетом того, что нка должны быть одинаковы для грамматик.

Цитата:
Чёрт возьми да. Да это про особенности. Они то нам и важны. Каждый день мы сталкиваемся именно с особенностями, самой конкретной, самой материальной реализации, а не со схемкой в википедии.
Да. Но почему вы считаете, что при разборе реуглярных выражений используются нка или дка?

Цитата:
Как вы это определили интересно знать?
Ну... backreferences не могут обрабатываться конечными автоматами. Никогда. Доказательство элементартное. Регэксп (.*)b\1. Будем кормить конечному автомату строки вида a....ab, где количество a варьируется. И будем смотреть, в каком состоянии находится автомат после прохождения этой строки. Так как количество состояний автомата конечно, на какие-то две строки мы получим одно и то же состояние (если состояний N, рассмотрим N+1 строку). Пусть это m и n букв a. Тогда рассмотрим строки "m штук a, b, m штук a" и "m штук a, b, n штук a". Так как после символа b автомат находится в одном и том же состоянии, дальнейший "разбор" будет одинаков и автомат придет в одно и то же конечное состояние. Но в одном случае результате неверный (одно из них подходит под regexp, второе - нет - ответы разные, а автомат дает один ответ).

Это было доказательство для дка. нка нужно предварительно перевести в дка. Вроде бы по сссылке (которую я давал в wiki) было написано, как это делается. В крайнем случае там должна была быть ссылка на литературу.

Вывод - если что-то успешно обрабатывает регулярные выражения и корректно работает с backreferences, оно не является конечным автоматом. Ну а использовать нка при разборе регулярного выражения смысла нет. Как минимум, некоторые вещи в автомате не представимы. А все остальное, что остается от нка, нормально представляется "позициями" в регулярном выражении + состоянием разбора. И, кстати, это как раз и может давать разницу в производительности для двух эквивалентных грамматик . А использование нка его давать не должно.

Цитата:
Шутку понял. Смешно.
Это не шутка. Это суровая правда жизни. При проектировании систем приходится учитывать области, в которых используемые библиотеки не дают требуемых гарантий. В этом случае наблюдаемое поведение может быть "случайным". И я сам на code review в некоторых случая настоятельно рекомендовал в документации писать, что "наблюдаемое поведение не является гарантируемым и может измениться в следующих версиях" (там это касалось отсортированности массива-результата).

Старый 16.01.2012, 17:03
ProxyGreen вне форума Посмотреть профиль Отправить личное сообщение для ProxyGreen Найти все сообщения от ProxyGreen
  № 8  
Ответить с цитированием
ProxyGreen
 
Аватар для ProxyGreen

Регистрация: Jul 2011
Сообщений: 67
Цитата:
Дайте, пожалуйста, ваше определение нка. И расскажите, как именно разбор регулярных выражений ими пользуется. Особенно с учетом того, что нка должны быть одинаковы для грамматик.
Цитата:
Да. Но почему вы считаете, что при разборе реуглярных выражений используются нка или дка?
Пффф... Всё что я утверждаю здесь касательно регулярок я преимущественно прочёл в книге Джеффри Фридла "Регулярные выражения" от O'Reilly.
Вот страничка от туда например:
Нажмите на изображение для увеличения
Название: b8462338a241.png
Просмотров: 113
Размер:	392.7 Кб
ID:	29156
(надеюсь не нарушаю ни каких правил здешних)
Меня обманули получается? Ох уж эти орейли, а я им так верил, так верил.

Цитата:
Ну а использовать нка при разборе регулярного выражения смысла нет.
Так-же цитатка из вики:

Цитата:
В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.
Там написано, что применяются, а вы говорите что не применяются. Хотя на эту статейку ссылаетесь, которая на мой взгляд весьма поверхностна, сомнительна и объективно ни чего не разъясняет.

Цитата:
Это было доказательство для дка.
Это набор слов, который мне ни чего не доказывает, и чего вы хотите доказать вообще тайна природы.


Последний раз редактировалось iNils; 21.02.2013 в 20:25.
Старый 16.01.2012, 17:51
maxkar вне форума Посмотреть профиль Отправить личное сообщение для maxkar Найти все сообщения от maxkar
  № 9  
Ответить с цитированием
maxkar

Регистрация: Nov 2010
Сообщений: 497
Я от вас так и не получил ответа о том, что вы понимаете под нка/дка.

Цитата:
Сообщение от ProxyGreen Посмотреть сообщение
Меня обманули получается? Ох уж эти орейли, а я им так верил, так верил.
Вполне могли. Я в технической литературе периодически встречаю ошибки и заблуждения авторов. А в русских переводах - так вообще эпические ляпы встречаются. Вот автор в книге не говорит, что настоящий НКА даст обе строки после применения регулярного выражения. А если бы вы ознакомились с тем, что такое НКА - вам бы это было очевидно. Ну и искать "кратчайшее" вхождение на ДКА точно так же можно. Тогда поиск завершается в "первом" конечном состоянии, а не после разбора всей строки. Только вот почему-то автор книги этого не говорит. Возможно, правда, где-то раньше устанавливался контекст, в котором используются термины. Тогда нужно смотреть, что же он имел в виду в этом контексте. Кстати, там потом описываются "в деталях" эти механизмы? Или только НКА/ДКА?

Цитата:
Там написано, что применяются, а вы говорите что не применяются. Хотя на эту статейку ссылаетесь, которая на мой взгляд весьма поверхностна, сомнительна и объективно ни чего не разъясняет.
"Статейка" дает определение конечного автомата. Это общепринятое определение. Возможно, вы что-то другое понимаете под нка/дка, но в этом случае вы должны дать ваше определение.

Теперь по применимости. Да. И, кстати, правильно пишут. Большая часть причин - технические причины, которые делают очень невыгодной детерминизацию нка. А последняя причина - это совершенно отдельный класс автоматов - "нка с выходом". Это совсем не то же, что подразумевается под "обычным нка" (опять же, без контекста).

Цитата:
Это набор слов, который мне ни чего не доказывает, и чего вы хотите доказать вообще тайна природы.
Т.е. вы либо используете какие-то свои определения нка/дка, либо просто не разбираетесь в том, что же такое нка/дка. См. выше два замечания про отсутствие определения НКА/ДКА от вас. Доказательство доказывает, что "грамматики с backreferences не являются автоматными (и регулярными по Хомскому), следовательно не могут разбираться нка/дка".

Старый 16.01.2012, 19:44
ProxyGreen вне форума Посмотреть профиль Отправить личное сообщение для ProxyGreen Найти все сообщения от ProxyGreen
  № 10  
Ответить с цитированием
ProxyGreen
 
Аватар для ProxyGreen

Регистрация: Jul 2011
Сообщений: 67
Ок. Тесты вам ни чего не показывают. Книга врёт. Замечательно. Ни нка ни дка ни где не используются, их судя по всему вообще не существует. Что используется тогда? Как называется механизм, который используется в регулярных выражениях?

Вот вам ещё ссылка:
http://lipetsk.lug.ru/projects/re/re...l#theorysearch
Но она тоже наверное врёт, там-же цитируют Фридла.


Последний раз редактировалось ProxyGreen; 16.01.2012 в 20:27.
Создать новую тему Ответ Часовой пояс GMT +4, время: 19:45.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 19:45.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.