Пётр - Опять регулярные выражения

Пётр - Опять регулярные выражения

Пётр

[	website	\|	My Website	]
[	userinfo	\|	ljr userinfo	]
[	archive	\|	journal archive	]

Опять регулярные выражения	[Feb. 6th, 2009\|09:23 pm]
Поразбирался с регулярными выражениями и решил попользоваться. Вскоре выскочила ошибка про превышение количества скобок, но это не беда, благо, движок был с исходниками, так что переправить 15 на 50 не проблема. На изучение исходников времени тратить не хотелось, но проснулось тщательно замордовываемое (во избежание разочарований) любопытство. Захотелось выяснить тип движка. Читать документацию в поисках ответа или придумывать способ проверки самостоятельно я тоже не хотел, так что воспользовался рецептами из книги Jeffrey E. F. Friedl, "Mastering Regular Expressions". Конечно, оказалось, что жизнь, как обычно, полное дерьмо: и "`nfa\|nfa not`" к "`nfa`" выдало печальный диагноз "`nfa`" (по стандарту POSIX должно возвращаться самое длинное из возможных значений, так что это не просто движок на недетерминированных конечных автоматах, но и один из многих, которые не удовлетворяют разработанному стандарту). На это, конечно, легко забить человеку, который, когда приходится писать функцию сортировки, выбирает QuickSort (я не из таких, но таких было очень много вокруг меня; сейчас, наверное, более популярна должна быть сортировка пузырьковая, ибо в современных языках писать функцию сортировки приходится редко). Но я совершил контрольный выстрел в голову: применил (из той же книги) "`X(.+)+X`" к чему-то типа "`=XX===================================================================`" (программа висит, так что уточнить, сколько именно знаков равенства я поставил, мне сложновато)… Теперь у меня есть выбор: остановить программу или умереть от старости, дожидаясь результата… Ну почему опять оказалось, что словосочетание "регулярные выражения" в современном программировании не более осмысленно, чем "демократия" в современном обществе! PS. С сайта, осмелившегося назваться regular-expressions.info: "There are two kinds of regular expression engines: text-directed engines, and regex-directed engines. Jeffrey Friedl calls them DFA and NFA engines, respectively." Действительно: зачем по сути писать, если можно сослаться на авторитета. Блин: "В школе вас будут учить рисовать маленькие значки, Бритни Спирс называет их цифрами и буквами." Регулярные выражения воспринимают просто как язык шаблонов, как будто лучше названия не нашлось… PPS. Я, на самом деле, не такой уж …, например, я ещё довольно давно читал цитату автора Перла: "This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here,"— просто хочется же хорошего чего-то, а муть, хоть и популярна, как-то не радует. (Напомнила мне её английская Википедия, и ссылку напомнила, http://dev.perl.org/perl6/doc/design/apo/A05.html , а читал я это ещё до того как стал программистом, когда подумывал о том, чтобы стать программистом на Perl-е [это было не так давно].)
Link	Оставить комментарий

Comments:

From:	a_karpov
Date:	February 6th, 2009 - 09:53 pm

(Link)

а чем плох квиксорт?

(Reply to this) (Thread)

From:	ppkk
Date:	February 7th, 2009 - 12:11 am

(Link)

"Пузырьковым" возможным временем работы в некоторых случаях, вероятность которых при равномерном распределении всех порядков незначительна (а значит на среднее быстродействие не влияют особо), но которые вполне типичны (считать незначительной вероятность того, что список уже будет упорядочен или даже состоять из одинаковых элементов нелепо, а если всё это предусматривать, уже несколько другой алгоритм получается).

В моём школьном кругу общения, включавшем и преподавателей информатики, и крутых олимпиадников я практически не слышал о сортировке кроме "быстрой". (А к концу университетских лет олимпиадникам мои ровесники преподавали уже другие алгоритмы. А сейчас это неважно, потому что на олимпиадах STL или Ява. Кстати, в STL по Страуструпу худшее время сортировки "пузырьковое", что меня тоже изрядно смущает. Про Яву или До-диез [C#] не интересовался.)

(Reply to this) (Parent) (Thread)

From:	a_karpov
Date:	February 7th, 2009 - 02:57 am

(Link)

по-моему, правильные квиксорты используют median of medians, что убивает возможную пузырьковость, нет?

(Reply to this) (Parent) (Thread)

From:	ppkk
Date:	February 9th, 2009 - 02:51 pm

(Link)

1. По-моему, это существенно другой алгоритм.
2. У меня, кажется, не убил (текст из Википедии английской).

Например, в английской Википедии текст (с пробелами и пр.) псевдокода базовой быстрой сортировки — 339 байт, псевдокода быстрой сортировки, не требующей много дополнительной памяти — 749 байт, а для "Median of Medians" приведён текст (не компилирующийся в MS VS 2008 без исправлений) на Си уже 2334 байта (как я понимаю, любители псевдокода его, значит, не переварили; удаление комментариев длину уменьшает не сильно).

Даже если в очевидных плохих примерах он работает хорошо, то что у него с худшим временем работы? Если оно-таки квадратичное, то (в силу отсутствия случайности) более тонкое и редкое возражение о всяких там DOS-атаках с посыланием специально сделанного списка ещё возможно.

Текст из Википедии не одолел списка из одинаковых элементов за разумное время…

Повторюсь, что Страуструп явно пишет о возможности "пузырькового времени" в стандартной сортировке контейнеров STL. А вот в (в Википедии же прочитал) STL от SGI в 2000-м использовали, например, introsort (переключающийся на сортировку кучей, значит ни в каком случае не имеющий "пузырькового времени"; в случае переключения он работает дольше, чем просто сортировка кучей).

(Reply to this) (Parent)