Эффективный парсинг на С/С++

Pavia

Угу, только моя реализация будет работать и на ARM'е и на AVR и на х86, поскольку использованы только стандартные средства С++! А ваша, написанная на х86 asm'е?
Когда-то я тоже считал asm верхом совершенства, но сейчас в основном, ориентируюсь на встраиваемые системы и контроллеры. В частности используя выше приведенную идиому, накатал NMEA парсер, который и на AVR и на ARM7 и ARM9 и на х86 будет работать без переписывания.

Заметте, я не утверждал, что они самые быстрые и рвут КМП или БМ алгоритмы. Я этой стороны вообще не касался, и здесь согласен с моим апонентом:

Далее...

Поясните подробнее, пока это выглядит просто как сотрясение воздуха.

Это юмор такой? Звучит как тавтология, что-то вроде "с точки зрения банальной эрудиции..." и т.д.

Вообще, согласно теории для каждого НКА есть эквивалентный ДКА и наоборот. Кто вам мешает "конвертнуть" "не эффективный НКА" в эффективный ДКА? У Ахо-Ульмана вполне доходчиво описано, как это сделать.

 

Моя тоже на Си. Я пропагандирую то что на высоком уровне эффективно может работать только тот кто знает низкий.

Очень печально видеть такое. Регулярки дают скорость в написание ии легкость понимание человеком. Но вот скорость от них тоже желательна просто многие уже согласились с той мыслей что это невозможно. Это печально.

ВМ может быть как МТ так и магазинным автоматом. При этом это будут разные ВМ.
Вы же сгребли в кучу универсальную ВМ и специальную для регулярных выражений. А она не может распознать больше чем умеет. Другими словами: не любая ВМ может заметить МТ.

Я бы не хотел в даваться в подробности по определенным причинам.
http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics-of-Expression-Processing/2/

 

М-де... У меня складывается понимание того, что меня не поняли. Постараюсь объясниться...
"Хопкрофт Д, Мотвани Р, Ульман Д. Введение в теорию автоматов, языков и вычислений" ( http://books.google.ru/books?id=Th5...&q=магазинный автомат это по существу&f=false ):

Т.о. магазинный автомат -- надстройка над обычным автоматом. Едем далее...
http://ru.wikipedia.org/wiki/Машина_Тьюринга:

Именно по этому критерию (что все является расширением [надстройкой над] конечного автомата) я и "сгреб их в кучу". Любые дополнительные операции будут выливаться в уменьшение скорости обработки. Что вас, кстати, опечаливает.
Далее. А почему НКА так уж не эффективен? Согластно "Ахо А, Сети Р, Ульман Дж. Компиляторы. Принципы, технологии, инструменты 2-е издание" (стр. 220), НКА для разбора строки требуется не более O(x+r), а ДКА O(x). Т.о. при длине регекспа << длины строки, они практически сравнимы по времени работы.

Мне от этого также веселее не становиться, и я всячески пытаюсь доказать, что регекспы могут работать шустро, при условии простоты и построения "по науке", вы же утверждаете, что я "не прав в корне"!

Ах, вот оно что! Да, признаю, у меня пробел был в этом плане. Просто когда использовал автомат в своих проектах, использовал его исключительно для нарезки токенов, а там пофигу, НКА или ДКА. А sed'ом пользовался не задумываясь о принципах его функционирования, и не требуя от него запредельных скоростей. Впрочем, возвращаясь в рамки топика -- топик стартеру тоже пофиг на эти фичи НКА.

Т.о. ДКА его вполне мог бы устроить, ИМХО. Не факт, что на его задаче (субъективно) он существенно проиграет по скорости специализированным алгоритмам поиска.

Собственно это все что я пытался донести.

 

Только тут умножение, а не сложение.

В большинстве случаев, да.

На самом деле я очень глубоко копал так как мне было интересно самому реализовать регулярные выражения.
Пришел выводу что можно сделать так что они летать будут. Но только для каждого частного случая нужна своя оптимизация.

 

Черт! Прошу прощения, на радостях перепутал. Точнее, не доглядел.
Тогда, да, вопрос снимается.

Так это везде так...
Оптимизация сродни исскуству -- строго индивидуальна. Ну а серебряной пули, как нас учат мудрейшие, не существует...

 

Возвращаясь к напечатанному...

Может, кому и пригодиться. А то тема библиотек шустрых регулярок осталась не раскрытой. Здесь раздают PIRE

Цитата с opennet.ru:

ИМХО, 3/4 ГигаБайта в секунду, весьма неплохо.

PS: любопытно, что за железо такое, позволяющее прочитать файл с такой скоростью?
Т.ч., в рамках топика, вполне может получаиться так, что производительность упрется в вожможности дисковой подсистемы, а не регулярок. Впрочем, не пробывал, утверждать не стану.

 

можно добавить что PIRE это разработка яндекса

 

Если я правильно понял TC (#4):

, то обычный Aho-Corasic + небольшая доработка для сочетаний, покроют все его потребности.

 

Damon
В интернете попадался отчет по регуляркам. С очень крутыми алгоритмами, но вот реализаций не было. Так что это не придел.

 

Pavia
Дык, я не спорю. Просто наткнулся на опеннете, решил сюда запостить. Вдруг, когда-нить, кто-нить будет искать решение подобной проблемы?

gazlan
Как правило, аппетит заказчика имеет свойство расти со временем и алгоритмы приходится усложнять... А, вообще, регулярки были предложены как один из вариантов решения, не более того.

 

Pavia

не раса кокса? этот алг в более развитом состоянии используется как стандартный в плане.