Ручной slipt строки или то же, но с помощью std::regexp - что быстрее?

Цитата Олег М @ 12.04.17, 15:29

Если честно, я понятия не имею как он работает. Но, судя по твоим же примерам, не слишком хорошо. И это в простейшем случае и в одном потоке.

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

Добавлено 12.04.17, 15:37

Цитата JoeUser @ 12.04.17, 15:35

Я не проверял, но чуйка подсказывает - похоже на правду. std::regex, имхо, коряв по реализации и недопилен по функционалу.

Да, это действительно возможно. Надо на версии от VS попробовать. В релизе.

Пфффф... На скорую руку:

Raw time:    2650000 microsecs.
Common time: 2064000 microsecs.
Boost time:  2451000 microsecs.
Regexp time: 6228000 microsecs.
Spirit time: 2117000 microsecs.

Файл "Осенние визиты.txt" Лукьяненко, объём ~800Кб, кодировка CP-1251, строка "-,./';\\=`?><\":}{|+_)(*&^%$#@!~][", регулярка соответственно "[-,./';\\=`?><\":}{|+_)(*&^%$#@!~]|\\]|\\[" для правильной обработки [ и ]. Также пришлось - поставить в начале, чтоб не рассматривался как символ диапазона. Количество итераций уменьшено до 100. Видно, как подкосились регэкспы, но в общем-то кто-нибудь видит существенную разницу в остальном?
Это было много частых совпадений. Теперь другая строка "0123456789" и соответствующая регулярка "0-9". Тут совпадения должны быть редки.

Raw time:    1070107 microsecs.
Common time: 916091 microsecs.
Boost time:  981098 microsecs.
Regexp time: 548054 microsecs.
Spirit time: 1465146 microsecs.

Упс.
Компилятор Intel® C++ for Windows on IA-32, Version 14.0.2.176, ядро у него GNUсное.

Сообщение отредактировано: Qraizer - 12.04.17, 15:45

Цитата Flex Ferrum @ 12.04.17, 15:36

Цитата Олег М @ 12.04.17, 15:29

Если честно, я понятия не имею как он работает. Но, судя по твоим же примерам, не слишком хорошо. И это в простейшем случае и в одном потоке.

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

Регулярное выражение -- это регулярное выражение
Компиляция в стейт-машину -- это один из возможных вариантов реализации. Некоторые фичи PCRE реализовать таким образом нереально сложно (если возможно), посему в RE2 их просто выкинули. Отсюда вопрос, как сейчас в STL-ях реализовано?

Цитата Qraizer @ 12.04.17, 15:37

Теперь другая строка "0123456789" и соответствующая регулярка "0-9". Тут совпадения должны быть редки.

Думаю, тут вся фишка в самом итераторе. Надо будет попробовать чистый regex_search и ручную обработку smatch'а, чтобы минимизировать внутренние копирования.

Ну, судя по результатам, в STL от MS стейт-машина если и есть, то не является ключевым элементом.

Цитата Flex Ferrum @ 12.04.17, 15:36

То есть регулярка компилируется в стейтмашику, которая потом щёлкает состояниями в зависимости от текущего символа во входном потоке.

Ты, наверное, хотел сказать интерпретируется. Компилируется - это когда в машинный код, по-моему.

Цитата Flex Ferrum @ 12.04.17, 15:47

Думаю, тут вся фишка в самом итераторе.

Я пробовал и так и эдак. Т.е. и диапазон, и явное перечисление. Если ты об этом. На результатах спирита и регулярок это сказывается в пределах погрешностей.

Цитата Qraizer @ 12.04.17, 15:49

Я пробовал и так и эдак. Т.е. и диапазон, и явное перечисление. Если ты об этом. На результатах спирита и регулярок это сказывается в пределах погрешностей.

Я имел в виду использование regex_token_iterator в одном случае и regex_search + std::smatch[-1] в другом.

Цитата Олег М @ 12.04.17, 15:48

Ты, наверное, хотел сказать интерпретируется. Компилируется - это когда в машинный код, по-моему.

Нет. Я сказал именно то, что хотел. Регулярка из строкового вида переводится в подобие AST (ну, должна, по крайней мере), оптимизируется и только потом применяется. А не при каждом применении интерпретируется оригинальная строка.

Добавлено 12.04.17, 16:01
Кстати, а если добавить к сравнению boost::regex и их же boost::expressive?

Сообщение отредактировано: Flex Ferrum - 12.04.17, 16:01

Цитата negram @ 12.04.17, 15:44

посему в RE2 их просто выкинули

Там PCRE емнип не было. Наиболее "близкий" вариант - ECMAScript.

Цитата Qraizer @ 12.04.17, 13:11

Надо тогда уж и splitLineRaw() переделать под коллекцию разделителей.
Как-то так, что ли...

Ну это уже не просто Raw, а скорее RawStupid
Основа оптимизации поиска по "коллекции разделителей" (при их числе > 2-4) - быстро отбраковывать наиболее вероятные (часто встречающиеся символы), не являющиеся разделителями, с тем, чтобы запускать проход по длинной строке разделителей не на каждом символе, а как можно реже. С учетом того, что практически все разделители принадлежат ASCII-диапазону, для разбивки русского текста достаточно запускать проход по строке разделителей по условию if (cur <= X), где X = Max(c[i]). Тогда в примере #32 c "Осенними визитами" splitLineRaw наверняка окажется в безусловных лидерах. Аналогично можно ускорить и обработку латиницы по условию непопадания символа в диапазон (хотя бы) строчных латинских "a"-"z" (ес-но с пред.проверкой непопадания разделителей в этот диапазон).

Сообщение отредактировано: leo - 13.04.17, 08:24

Цитата JoeUser @ 12.04.17, 23:47

Там PCRE емнип не было.

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

Заметьте, в упомянутом boost есть 2 разных варианта: boost::split (который кстати не только строки может разбивать) и, отдельно, boost::regex_split (который объявлен устаревшим в пользу более универсального regex_token_iterator). И в стандартной библиотеке питона те же 2 разных версии split'a есть - обычная и с регулярными выражениями. Так что ИМХО - да, std::split лишним не будет.