Linux.by

[to kirya85]

Во первых, простите, если показалось, что я имею что-то против вас. Просто, согласитесь, код был не очень оптимальным.

Новый код получше. Но все равно библиотечные функции при каждой итерации while делают по проходу строки, которая правда уменьшается, т. к. строка обрезается спереди. Да и теперь мой код выглядит проще (и не использует библиотечных функций) , а также хорошо ляжет на асм IA32, в то время, как библиотечные функции выльются в нечто большое (опять же - эти функции универсальны, а я написал узко специализированную функцию, где вся их мощь ни к чему).

Совет: надо читать че-нить по построению эффективных алгоритмов. Ведь зачем придумывать то, что уже придумано, тем более, что очень (ну очень) большое количество алгоритмов самому придумать очень (ну очень) сложно ))

P. S. На счет b[strlen(a)] в GCC - удивлен. По стандарту там константное выражение. Но наверное он пропускает это потому, что размер a фиксирован и известен на этапе компиляции...

P. P. S. На счет "ляжет на асм":

// NASM
Не намного больше, чем на С (я просто показал этим кодом то, что имел в виду. Мне кажется, что в любом случае будет быстрее, так что подумайте на счет эффективных алгоритмов.

satanic_mechanic писал(а): PS. Извините за грубость, но на этом форуме я вообще часто вижу, как на новичков начинают гнать так, что у них во всю отпадает охота что-либо спрашивать. И это линукс-сообщество. Сообщество людей, которые считают, что они круче всех и при каждой возможности пытаются показать это ;(((
// это касается не всех, да и большинства не касается ... но это правда

А это везеде так. Отличительная черта некрасноглазого линуксоида - наличие навыков самостоятельного поиска, чтения и применения документации и, как следствие, наличие собственного мнения. А имея собственное мнение - почему бы не погнать на ближнего своего, тем более всегда можно сказать man 1 knuth А с красноглазыми все еще хуже.
Наличие примеров на python etc в трэде - ессно оффтопик, хотя какой-то смысл в нем есть наверное - любители re лишены счастья узнать про методы реализаци конечных автоматов на практике
А что касается новичков - то тут война будет до последнего пингвина. Если 1 из 10 поймет что читать документацию - это вобщем-то эффективнее чем каждый раз задавть вопросы - то это есть хорошо. Да, один, два, 10 раз это пройдет, но ведь бывают случаи, когда ответ ПРИДЕТСЯ искать самому. и тогда 9 из 10 просто уходят

[to Llama]

Согласен полностью.

Но мне кажется, что здесь часто поступают невежливо. Да и собственное мнение - хорошо, но надо уважать чужое (и пытаться ВЕЖЛИВО доказать, что оно неверно ).

P. S. Вас, Llama, уважаю

satanic_mechanic писал(а):[to Llama]

Согласен полностью.

Но мне кажется, что здесь часто поступают невежливо. Да и собственное мнение - хорошо, но надо уважать чужое (и пытаться ВЕЖЛИВО доказать, что оно неверно ).

P. S. Вас, Llama, уважаю

Согласен. Но какие люди есть такие и есть и переделка людей в нашу компетенцию не входит к счастью

тогда написание чего либо на ассме без резкой на то необходимости - тяжелая форма щизофринии ИМХО

satanic_mechanic писал(а):[to leikind]

А зачем думать? Сравнивать надо. Возьми большое-большое регулярное выражение, напиши аналог на C, и сравни c grep или awk на большом массиве текстов. Результаты тебя сильно-сильно удивят.

Я вроде говорил: все зависит от ситуации. Сравни по скорости прогу на С, специально написанную под данную задачу, и ту же прогу на перле с регулярными выражениями (при условии, что прога не криво написана).

Я уже предлагал тебе самостоятельно разобраться с производительностью регекспов в различных инструментах. Конечно, очень часто компилируемые языки быстрее, но прямой зависимости нет - слишком многое зависит от большого количества факторов. Как пример приведу http://www.bagley.org/~doug/shootout/bench/regexmatch/ - в этом тесте Perl и mawk обогнали gcc и g++.

Это по поводу компилируемый vs интерпретируемый

satanic_mechanic писал(а): И дело не только в том, что Перл - интерпретатор. Регулярные выражения универсальны и очень удобны. А за это мы платим скоростью.

Мы платим за регулярные выражения скоростью? Не хочешь ли ты сказать. что регулярные выражения по определению медленны? Я правильно понял? Если да, то это очевидная ересь. Если бы ты знал, что такое конечные автоматы, DFA, NFA, ты бы так не говорил. Все гораздо сложнее.

satanic_mechanic писал(а): Но дело даже не в этом. Я никоим образом не умаляю роль регулярных выражений. Просто когда задается вопрос о проге на С, а кому-то надо показать как он крут:

ruby -p -e '$_.gsub!(/ +/," ")'
perl -p -e 's/ +/ /'
awk '{gsub(/ +/," "); print}'

Это всего лишь демонстрация решения простой задачи простым способом.

satanic_mechanic писал(а):

Бред какой-то. А как ты думаешь, на чем реализованы regex engines в высокоуровневых языках? На них самих что-ли? Нет конечно. На C, как и сами языки. Тогда в чем разница использования регулярных выражений из высокоуровневых языков и С? Только в том, что реализация регулярных выражений в библиотеке pcre заставляет многих работавших с ней не очень хорошо о ней отзываться.

Опять извечное стремление кого-то обламать.


Я не идиот и прекрасно понимаю, на чем реализован Perl, Python, PHP и т. п. языки. Я говорил о написании библиотеки на С и там же ее использования в свое удовольствие (говорил просто к слову). Реализация такая, какая тебе нравится (под себя), что бы о ней хотя бы сам программист (который ее напишет) хорошо отзывался. Я не выражал мнения, что регекспы реализованы на х.. знает чем. Не правда ли. А вы в желании меня обламать, занимаетесь искажением моих мыслей.

Расслабся, никто тебя не хочет обидеть. Тебе что надо, обсудить тему или поругаться с кем-то? Если поругаться, то это не ко мне.

По поводу обработки текста на C и вообще по поводу выбора инструментария. Кроме процессорного времени есть еще одно время, гораздо более дорогое - это время разработчика. Разрыв между этими двумя ресурсами увеличивается - процессорные мощности дешевеют, а мозги - нет. Вот ради уменьшения затрат на это дорогое время все время и возникают все новые технологии.

Если операция удаления пробела выполняется в программе несколько раз, и ее кто-то хочет реализовать вручную на С или на ассемблере, чтобы выиграть какие-то жалкие сотые доли миллисекунды, то это просто неоправданная затрата человеческого ресурса. Можно и грубее сказать. Другое дело, если программа обрабатывает огромные массивы информации, тогда микроскопический выигрыш на одной операции даст на выходе серъезный прирост. Тут нужно думать об оптимизации.

leikind писал(а): оН ОНБНДС НАПЮАНРЙХ РЕЙЯРЮ МЮ C Х БННАЫЕ ОН ОНБНДС БШАНПЮ ХМЯРПСЛЕМРЮПХЪ. йПНЛЕ ОПНЖЕЯЯНПМНЦН БПЕЛЕМХ ЕЯРЭ ЕЫЕ НДМН БПЕЛЪ, ЦНПЮГДН АНКЕЕ ДНПНЦНЕ - ЩРН БПЕЛЪ ПЮГПЮАНРВХЙЮ. пЮГПШБ ЛЕФДС ЩРХЛХ ДБСЛЪ ПЕЯСПЯЮЛХ СБЕКХВХБЮЕРЯЪ - ОПНЖЕЯЯНПМШЕ ЛНЫМНЯРХ ДЕЬЕБЕЧР, Ю ЛНГЦХ - МЕР. бНР ПЮДХ СЛЕМЭЬЕМХЪ ГЮРПЮР МЮ ЩРН ДНПНЦНЕ БПЕЛЪ БЯЕ БПЕЛЪ Х БНГМХЙЮЧР БЯЕ МНБШЕ РЕУМНКНЦХХ.

еЯКХ НОЕПЮЖХЪ СДЮКЕМХЪ ОПНАЕКЮ БШОНКМЪЕРЯЪ Б ОПНЦПЮЛЛЕ МЕЯЙНКЭЙН ПЮГ, Х ЕЕ ЙРН-РН УНВЕР ПЕЮКХГНБЮРЭ БПСВМСЧ МЮ я ХКХ МЮ ЮЯЯЕЛАКЕПЕ, ВРНАШ БШХЦПЮРЭ ЙЮЙХЕ-РН ФЮКЙХЕ ЯНРШЕ ДНКХ ЛХККХЯЕЙСМДШ, РН ЩРН ОПНЯРН МЕНОПЮБДЮММЮЪ ГЮРПЮРЮ ВЕКНБЕВЕЯЙНЦН ПЕЯСПЯЮ. лНФМН Х ЦПСАЕЕ ЯЙЮГЮРЭ. дПСЦНЕ ДЕКН, ЕЯКХ ОПНЦПЮЛЛЮ НАПЮАЮРШБЮЕР НЦПНЛМШЕ ЛЮЯЯХБШ ХМТНПЛЮЖХХ, РНЦДЮ ЛХЙПНЯЙНОХВЕЯЙХИ БШХЦПШЬ МЮ НДМНИ НОЕПЮЖХХ ДЮЯР МЮ БШУНДЕ ЯЕПЗЕГМШИ ОПХПНЯР. рСР МСФМН ДСЛЮРЭ НА НОРХЛХГЮЖХХ.

мЕ ЛНЦС ЯНЦКЮЯХРЭЯЪ...

дЮФЕ ЕЯКХ ОПНЦПЮЛЛЮ МЕ НАПЮАЮРШБЮЕР РЕЯРНБСЧ ХМТНПЛЮЖХЧ, ДЮФЕ ЕЯКХ ДЮММЮЪ НОЕПЮЖХЪ БШОНКМЪЕРЯЪ БЯЕЦН НДХМ ПЮГ, МН БЯT ЩРН ОПНХЯУНДХР БМСРПХ ОПНЕЙРЮ, МЮОХЯЮММНЦН РНКЭЙН МЮ C, РН БЯT ПЮБМН ЙЮЙНИ ЯЛШЯК ОПХОКЕРЮРЭ ЯЧДЮ ЪГШЙХ БЕПУМЕЦН СПНБМЪ? пЮДХ НДМНИ ОПНЯРЕМЭЙНИ НОЕПЮЖХХ?! бНР ЩРН СФ РНВМН МЕНОПЮБДЮММШЕ ГЮРПЮРШ... ОПХВTЛ, БНГЛНФМН, Х ВЕКНБЕВЕЯЙНЦН ПЕЯСПЮЯЮ РНФЕ...
бННАЫЕ, ЛНФЕР АШРЭ ЛМНФЕЯРБН БЮПХЮМРНБ, ЦДЕ ПЕЮКХГЮЖХЪ ЩРНИ НОЕПЮЖХХ МЮ C АСДЕР ЕДХМЯРБЕММН БЕПМНИ

Anonymous писал(а): Не могу согласиться...

Даже если программа не обрабатывает тестовую информацию, даже если данная операция выполняется всего один раз, но всT это происходит внутри проекта, написанного только на C, то всT равно какой смысл приплетать сюда языки верхнего уровня? Ради одной простенькой операции?! Вот это уж точно неоправданные затраты... причTм, возможно, и человеческого ресураса тоже..

Конечно, если все пишется на С, то да, как говориться, поздно пить боржоми, если печень отвалилась. К выбору инструмента надо подходить серъезно с самого начала. Должны быть веские причины для написания программы на С, помимо инерции мышления и нежелания разработчика изучать новое, или просто неизвестное старое. Как пример можно привести программу, которая должна очень тесно общаться с ОС - тогда это солидный фактор в пользу выбора языка данной операционной системы.

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

пнуть новенького поощутимее - мое любимое занятие
чтобы не испытывал иллюзий

[to Avanti!]

Написание программ на асме без необходимости ?

Я писал:
Не намного больше, чем на С (я просто показал этим кодом то, что имел в виду)

А имел ввиду я то, что приведенный мною алгоритм эффективнее и проще. Код на асме показывает изящность этого решения. Согласись, для асма этот код маленький.

[to leikind]

Я прекрасно знаю, что такое детерминированные и недетерменированные (и с эпсилон-переходами) конечные автоматы (хотя серьезно никогда этим не занимался, поэтому, буду рад, если мне посоветуют какие либо источники, ссылки в Internet и т. п.). Если вы не заметили, в своей программе я как раз и реализовал очень простой детерминированный конечный автомат. Я попробую вам это доказать.

Как известно ДКА это пятерка (Q, E, f, q0, F), где
Q - множество состояний;
E - входной алфавит;
f - функция переходов;
q0 - начальное состояние;
F - подмножество Q, определяющее множество допускающих состояний.

ДКА и регулярные выражения определяют эквивалентные регулярные языки.

Рассмотрим ДКА реализованный в моей программе (определен неформально ({} - множество)):
A = ({<после любого символа, не пробела>, <после пробела>}, {ASCII или ANSI, как угодно}, f, <после любого символа, не пробела>, {<после пробела>})
функцию f определим следующим образом: при каждом переходе дополнительно реализуется какое либо действие с выходным потоком. Например при переходе с <после любого символа, не пробела> в <после пробела> в выходной поток копируется пробел. А при переходе из <после пробела> в <после пробела> ничего не делается.

Надеюсь убедил.

По поводу обгона Perl'ом С. Как вы и говорили, слишком многое зависит от большого количества фактов. В данном случае я думаю дело в pcre. Опять же в Perl'е те же регекспы реализованы на С.

Теперь о том, что я яко-бы считаю что регулярные выражения медленны по-определению. Я такого никогда не говорил. У меня такого даже в мыслях не было. Регулярные выражения УНИВЕРСАЛЬНЫ.
Я писал: Сравни по скорости прогу на С, специально написанную под данную задачу, и ту же прогу на перле с регулярными выражениями. Я повторяю - СПЕЦИАЛЬНО НАПИСАННУЮ ПОД ДАННУЮ ЗАДАЧУ. То есть, в данном примере, нам не надо строить конечный автомат. Он уже реализован в самой программе. То есть мы проводим вычисления уже готовым автоматом, не заботясь о его построении.

Теперь (я немного отвлекусь от темы), о специфических задачах (не всегда связанных с поиском текста). Регекспы не решение всех проблем и иногда непосредственная реализация конечного автомата намного проще. В качестве примера приведу простую задачу:

Есть строка. Алфавит - {0, 1}. Она определяет двоичное число. Определить, делится ли оно, допустим, на 5.
Построим конечный автомат из 5-и состояний, каждое из которых определяется расширенной функцией переходов: если в результате деления на 5 уже прочитанной части числа, мы имеем остаток 0 - то мы в 0-ом состоянии, если 1 - то в 1-ом и т. д.): Это был граф конечного автомата:). Наверное прийдется пояснять таблицей, а то довольно криво получилось... Итак, такой конечный очень просто запрограммированть и на чистом С и на асме. А теперь, регулярное выражение определяющее тот же регулярный язык, что и этот автомат: Надеюсь, вы согласны, что такое регулярное выражение намного сложнее вывести, чем автомат.

Замечания:
1. Надеюсь правильно вывел. Делал это на бумаге (методом исключения состояний), поэтому мог ошибиться. Для заинтересовавшихся, могу написать прогу.
2. Запись приведенное здесь регулярного выражения отлична от принятой в UNIX. Не следует считать регекспы в UNIX стандартом, они не появились там сразу. Итак
а) объединения двух языков A и B (A + B). Например, A = {001, 100, 11} и B = {001, 101, 10}, то A + B = {001, 100, 101, 10, 11}.
б) конкатенация языков A и B (AB). Пример - A = {001, 100, 11} и B = {10}, то AB = {00110, 10010, 1110}.
в) итерация языка A (A*) - множество всех цепочек, которые можно образовать путем конкатенации любого количества цепочек из A. Пример - A = {0, 1}, A* - все цепочки, состоящие из нулей и единиц.

При поиске просто текста (без метасимволов) тоже есть более эффективные алгоритмы. Бойера-Мура, например. Эффективность - O (n/m) (n - длина текста, m - длина шаблона). Его я думаю, также можно приткнуть к регекспам, увеличив их эффективность. Например, если внутри регулярного выражения есть довольно длинный статический участок текста, то искать его по более эффективному алгоритму. А затем в обе стороны идти по шаблону с помощью регекспов. Но это только спонтанная догадка, ее не реализовывал, может как-нить попробую. Заинтересовавшимся, если будете искать алгоритм Бойера-Мура - ищите в первоисточнике. Почему-то и в Кнуте, и у Кормена там вместо 4-х эвристик всего 3. В результате в среднем время есть O(n/m), но в худшем все равно O(n*m)

И напоследок, никак не хотел поругаться, я вас очень уважаю и согласен со всем, что вы говорили, но не всегда я говорил о том, что вы доказывали, поэтому и получался спор. Но если вы снова с чем-то не согласны, я снова готов доказывать свою точку зрения (пока не докажу или пока вы не докажете мне, что я спорол явную чушь )

[to [uNIx]mend0za]

пнуть новенького поощутимее - мое любимое занятие
чтобы не испытывал иллюзий

Это мне ??? (я то у вас новенький) Если мне, то меня никто не пинал, а если и пинал, у него ничего не получилось...

satanic_mechanic писал(а):[to leikind]

Я прекрасно знаю, что такое детерминированные и недетерменированные (и с эпсилон-переходами) конечные автоматы (хотя серьезно никогда этим не занимался, поэтому, буду рад, если мне посоветуют какие либо источники, ссылки в Internet и т. п.). Если вы не заметили, в своей программе я как раз и реализовал очень простой детерминированный конечный автомат. Я попробую вам это доказать.

Зачем? Зачем мне все эти азы? Я верю, что ты знаешь тему, но ведь речь не об этом. Речь о том, что конечный автомат для разбора текста не нужно писать самому и вручную, ибо есть программные модули для построения автоматов из простой и понятной нотации. Нотация в данном случае - это регекспы, а программные модули - регексп-движки.

satanic_mechanic писал(а):[to leikind]

Теперь о том, что я яко-бы считаю что регулярные выражения медленны по-определению. Я такого никогда не говорил. У меня такого даже в мыслях не было.

ты писал
Регулярные выражения универсальны и очень удобны. А за это мы платим скоростью.

Как еще мне истолковывать это утверждение. как не утверждение о скорости регекспов?


Мы о слишком о простом примере говорим. Автомат с количеством состояний в пару десятков ты вручную еще закодируешь. А в пару тысяч? Зачем заниматься тем, что давно автоматизировано? То есть построением автомата по паттерну?

[to leikind]

Опять вы опровергаете не то, что я утверждаю.

Я не заставляю писать вас конечный автомат вручную и вовсе не утверждаю, что это реально сделать для автомата с количеством состояний в несколько тысяч. Я доказываю, что регекспы МЕДЛЕННЕЕ специализированной программы, потому что универсальны. То есть СПЕЦИАЛЬНО НАПИСАННАЯ ДЛЯ ЭТОЙ ЗАДАЧИ ПРОГРАММА, быстрее программы, использующей регулярные выражения. Например, никто не заставляет строить автомат на этапе выполнения, его можно построить во время написания программы по тому же паттерну с помощью написанной для этого программы и в каком-либо абстрактном виде слить в файл, а затем использовать. Опять-же мы не затрачиваем время на его построение во время выполнения. И опять же это применимо только для программы решения КОНКРЕТНОЙ ЗАДАЧИ. И опять же делать это имеет смысл тогда, когда КРИТИЧНА СКОРОСТЬ. Но я тоже не заставляю вас это делать. Все, что я хочу сказать, это то, что универсальная программа менее эффективна, чем специально заточенная под данную задачу.

Далее, я утверждаю, что автоматы применимы не только для обработки текста, но и во множестве других задач. И вот там задавать их паттернами не удобнее, а наоборот сложнее. И вот зачем, я привел простую задачу про двоичные числа. А не затем, что бы показать, что знаю тему.

Еще раз, был бы рад, если подскажете какие либо источники, ссылки по теме...

С уважением, satanic_mechanic

satanic_mechanic:
в одном из предыдущих постингов из меня сделали жупел для бегинеров,
вот и отрываюсь

возвращаясь к обсуждению языковых средств: есть адекватные и полуадекватные и совсем не адекватные средства решения конкретной задачи. Для обработки текста asm: помилуй мя господи, даже Cи - только в случае крайней необходимости.
Обычно апологеты этих языков приводят в свое оправдание мифические случаи необходимости крайней производительности. Замечу что они не приводят ни одного реального примера для практической задачи. Посему будем считать что традиоционные средства (регекспы+Perl/Ruby/Python/sed/grep) закрывают 99% надобностей. Измышление из пальца высосаных задач оставим для теоретиков.