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

Тут на российском сайте для предложений в стандарт появилось новое - предлагают сделать стандартный алгоритм для разбиение строки на подстроки. На что у меня возникло вполне обоснованное возражение: зачем добавлять такой алгоритм, если уже есть regexp'ы. И вот возник вопрос: а действительно, является ли такая замена адекватной и что будет работать быстрее/эффективнее?

Думаю, просто разбить строку по символу-разделителю будет по-любому эффективенее, чем regexp'ом. Хотя пример, который там показан, довольно тяжеловатый.

В стандартной библиотеке уже всё есть. Можно пользоваться.

Пример:

#include <fstream>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <regex>
 
using namespace std;
 
int main() {
   std::string text = "One, two, three";
   std::regex ws_re(",\\s+"); // whitespace
   std::copy( std::sregex_token_iterator(text.begin(), text.end(), ws_re, -1),
              std::sregex_token_iterator(),
              std::ostream_iterator<std::string>(std::cout, "\n"));
 
    return 0;
}

Бьёт строку по запятым и "съедает" пробелы.

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

Как выяснилось, разница довольно существенная - ~20 раз. Но это на такой, довольно простой, задаче.

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

Цитата Flex Ferrum @ 10.04.17, 22:16

Как выяснилось, разница довольно существенная - ~20 раз.

Кто б сомневался.
Хотя, разница должна быть ещё больше. С учётом того, что в splitLineRaw большая часть времени тратится на создание std::string и добавление её в вектор, а в splitLineRegEx - на поиск.

Цитата Олег М @ 11.04.17, 04:41

Цитата Flex Ferrum @ 10.04.17, 22:16

Как выяснилось, разница довольно существенная - ~20 раз.

Кто б сомневался.
Хотя, разница должна быть ещё больше. С учётом того, что в splitLineRaw большая часть времени тратится на создание std::string и добавление её в вектор, а в splitLineRegEx - на поиск.

Временем на создание строки можно пренебречь. После первогого прохода цикла в векторе память уже не выделяется, а в строке работает small string optimization (в gcc-версии), и память тоже не выделяется. Таким образом просто символы копируются.

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

Цитата Flex Ferrum @ 11.04.17, 06:33

После первогого прохода цикла в векторе память уже не выделяется,

Там разве не удваивается резерв? Т.е. на первые 6 элементов, в данном случае, память должна выделяться/копироваться 3 раза.

Сообщение отредактировано: Олег М - 11.04.17, 06:55

Цитата Олег М @ 11.04.17, 06:52

Цитата Flex Ferrum @ 11.04.17, 06:33

После первогого прохода цикла в векторе память уже не выделяется,

Там разве не удваивается резерв? Т.е. на первые 6 элементов память, в данном случае, должна выделяться/коироваться 3 раза.

Это совершенно не важно. Важно, что clear память не освобождает.

Ну да, не обратил внимания.
А вообще, тоже не вижу особой необходимости вносить такой сплит в стандарт (хотя, и range-for тоже не вижу, но удобно).
Лучше бы сделали какой-нибудь парсер, чтоб можно было разбирать строку за один проход.

Цитата Олег М @ 11.04.17, 07:00

Лучше бы сделали какой-нибудь парсер, чтоб можно было разбирать строку за один проход.

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

Цитата Flex Ferrum @ 11.04.17, 07:34

Я так понимаю, что в общем случае это невозможно.

Почему? Относительно простые случаи, типа scanf, вполне возможно перенести в compile-time. А другое и не нужно.

Цитата Flex Ferrum @ 11.04.17, 07:34

А для всего остального есть регэкспы.

Regexp - не вариант, очень медленный. Большой поток данных им особо не напарсишься,

Цитата Олег М @ 11.04.17, 07:42

Regexp - не вариант, очень медленный

Как видишь, "очень" - это понятие относительное. Если считать boost::split более менее универсальным вариантом split'а - то регэксп медленнее "всего" в два раза. Для ряда задач это может быть вполне приемлемо.

Цитата Олег М @ 11.04.17, 07:42

Относительно простые случаи, типа scanf, вполне возможно перенести в compile-time.

Ты когда последний раз scanf'ом то пользовался? Этот "относительно простой случай" уже реализован на базе istream'ов. Натравливаешь istream на строку и стримишь из неё то, что нужно, как-то обрабатывая ошибки. Самый что ни наесть compile-time.

Цитата Flex Ferrum @ 10.04.17, 22:16

Как выяснилось, разница довольно существенная - ~20 раз. Но это на такой, довольно простой, задаче.

Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров, во-вторых, нужен обобщённый алгоритм. На вот, добавь:

template<typename It, typename Ot, typename Cr, typename Pr>
Ot splitLineCommon(It b_str, It e_str, It b_delim, It e_delim, Ot result, Cr creator, Pr comp)
{
    do
    {
        auto pos = std::find_first_of(b_str, e_str, b_delim, e_delim, comp);
        
        *result++ = std::move(creator(b_str, pos));
        b_str = pos;
    } while (b_str++ != e_str);
    
    return result;
}
 
template<typename It, typename Ot, typename Cr>
Ot splitLineCommon(It b_str, It e_str, It b_delim, It e_delim, Ot result, Cr creator)
{
    return splitLineCommon(b_str, e_str, b_delim, e_delim, result, creator,
                           [](typename It::value_type b, typename It::value_type e) { return b == e; });
}
 
/* ... */
std::string delims("[,;]");
 
splitLineCommon(begin(testStr), end(testStr), begin(delims), end(delims), std::back_inserter(/* ... */),
                [](std::string::iterator b, std::string::iterator e) { return std::string(b, e); });

Результат примерно ожидаем.

Цитата negram @ 10.04.17, 23:04

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

Кстати, а почему с boost::spirit не сравнили?

Добавлено 11.04.17, 12:01
P.S. Походу, [] лишние в разделителе.

Сообщение отредактировано: Qraizer - 11.04.17, 12:01

Цитата Qraizer @ 11.04.17, 11:58

Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров,

Там не линейная зависимость будет?

Думаю, линейная, с небольшим бо́льшим единицы коэффициентом пропорциональности от длины списка разделителей.

В общем, я ни разу не специалист в spirit, но то, что удалось вспомнить, вложил в сие. Недурно, как мне кажется. Спецам, владеющим оптимизацией spirit, велкам.

Цитата Qraizer @ 12.04.17, 00:01

В общем, я ни разу не специалист в spirit, но то, что удалось вспомнить, вложил в сие.

Здесь, кстати, тот случай, когда основное время тратится на добавление в std::vector.

Это к тому, что там семантика копирования вместо перемещения? Возможно. Потому спиритисты и приветствуются. Как сказать спириту, чтоб перемещал, я не знаю.

Лучше так и с оптимизацией.

Цитата Flex Ferrum @ 12.04.17, 11:26

Лучше так и с оптимизацией

А что именно там лучше?

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

А что именно там лучше?

Там данные с разных вариантов строк для сплита. Ну и оптимизация включена.

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

Добавлено 12.04.17, 13:31
Как-то так, что ли...

template<typename It>
std::vector<std::string>& splitLineRaw(std::vector<std::string>& result, It cur, It e, const char* c)
{
  while (cur != e)
  {
    auto start = cur;
 
    while (cur != e)
    {
      int  i;
    
      for (i = 0; c[i] != '\0' && *cur != c[i]; ++i) ;
      if (c[i] != '\0') break;
      ++cur;
    }
    result.push_back(std::string(start, cur));
    if (cur == e) break;
    ++cur;
  }
 
  return result;
}

Цитата Flex Ferrum @ 12.04.17, 11:50

Там данные с разных вариантов строк для сплита. Ну и оптимизация включена.

Т.е. можно смело сделать вывод, что все эти regexp'ы и spirit'ы - это, конечно, круто и здорово, но крайне неэффективно.
То же самое касается и парсеров istream, которые стопудово будут работать много хуже старого доброго sscanf.

Крайне неэффективно – это смотря какая задача. Исключения тоже, написанные на коленке под каждый конкретный случай, будут значительно эффективней общего языкового механизма. И самописный RTTI встречался, потому что языковой был запрещён Стандартом Кодирования. Задача сплита строки на подстроки по простому формальному признаку соответствия известному патерну довольно проста. Другое дело, когда стоит задача перенести в код LEX-грамматику. Или отрефакторить и реализоваться PHP-модуль.

Добавлено 12.04.17, 14:27
К тому же не факт, что алгоритмы поиска в строках, реализованные в библиотеках, не заточены под большие массивы данных. Надо попробовать погонять эти splitLineXXX()-ы на парусоткилобайтных строках с 20-значным списком разделителей...

Цитата Олег М @ 12.04.17, 13:46

Т.е. можно смело сделать вывод, что все эти regexp'ы и spirit'ы - это, конечно, круто и здорово, но крайне неэффективно.

Всё зависит от задачи, как правильно заметил Qraizer. Вот, скажем, задали мне вчера вопрос: можно ли (и если можно, то как) при примерно таком коде:

int a = 0, b = 0, c = 0;
 
cin >> /* ... */;

написать в консоле "b=2" и это сразу прыгнет в переменную b. Код вышел довольно простой.

#include <iostream>
#include <regex>
#include <string>
 
using namespace std;
 
int main()
{
    int a = 0;
    int b = 0;
    int c = 0;
 
    std::regex parseRegex(R"(\s*([abc])\s*=\s*([+-]?\d+)\s*)");
    std::smatch baseMatch;
    for (;;)
    {
        std::string line;
        std::getline(std::cin, line);
        if (line == "exit")
            break;
 
        if (!std::regex_match(line, baseMatch, parseRegex))
        {
            std::cout << "Can't match the string! Invalid string format." << std::endl;
            continue;
        }
 
        if (baseMatch.size() != 3)
        {
            std::cout << "Invalid string format." << std::endl;
            continue;
        }
 
        auto varName = baseMatch[1].str();
        auto varValueStr = baseMatch[2].str();
        auto varValue = atoi(varValueStr.c_str());
 
        if (varName == "a")
            a = varValue;
        else if (varName == "b")
            b = varValue;
        else if (varName == "c")
            c = varValue;
 
        std::cout << "a = " << a << std::endl;
        std::cout << "b = " << b << std::endl;
        std::cout << "c = " << c << std::endl;
    }
    return 0;
}

Как ты понимаешь, что чтобы решить эту задачу чисто алгоритмически тебе придётся написать портянку, которая сначала очистит от пробелов строку, потом побьёт её по знаку '=', потом опять очистит от пробелов, потом - проверить что в левой части a, b или c, а в правой - валидное число. И всё это на if'ах, find'ах и тримах. А тут - прогнал через регулярку и получил результат, распиханный в слоты. Удобно. И, главное, более-менее понятно. И изменения вносить несложно.

Добавлено 12.04.17, 14:56

Цитата Qraizer @ 12.04.17, 14:24

Крайне неэффективно – это смотря какая задача. Исключения тоже, написанные на коленке под каждый конкретный случай, будут значительно эффективней общего языкового механизма. И самописный RTTI встречался, потому что языковой был запрещён Стандартом Кодирования. Задача сплита строки на подстроки по простому формальному признаку соответствия известному патерну довольно проста. Другое дело, когда стоит задача перенести в код LEX-грамматику. Или отрефакторить и реализоваться PHP-модуль.

В данном контексте интерес представляет код clang'а. Где ручной RTTI, почти полное отсутствие рантайм-полиморфизма в AST, битовые поля в классах и прочие прелести оптимизации.

Цитата Flex Ferrum @ 12.04.17, 14:39

Как ты понимаешь, что чтобы решить эту задачу чисто алгоритмически тебе придётся написать портянку, которая сначала очистит от пробелов строку, потом побьёт её по знаку '=', потом опять

Единственное, что я понимаю, что такая задача, параметр1=значение1|параметр2=значение2...., довольно просто решается за один проход по строке, безо всяких regexp. Даже если вдруг понадобится удалять пробелы.
Естественно, если ты обрабатываешь ввод с клавиатуры, то похрену на производительность. Но когда идёт поток данных, то тут призадумаешься.

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

Единственное, что я понимаю, что такая задача, параметр1=значение1|параметр2=значение2...., довольно просто решается за один проход по строке, безо всяких regexp.

Так и regexp в данном случае может сделать один проход по строке. Он ведь просто не запрещает возвратные алгоритмы.

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

Так и regexp в данном случае может сделать один проход по строке. Он ведь просто не запрещает возвратные алгоритмы.

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

Существует и такое мнение:

Цитата

...
MinGW-w64 4.9.2 на PCRE показывает результат в 8.3s, а на std::regex -- 44s (я не ошибся, сорок четыре секунды). Но у MinGW есть свои проблемы под Windows, так что здесь все вполне ожидаемо.

Но однозначно, проблема не в C++ как языке или его компиляторе, а конкретно в текущих версиях std::regex.
...

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

Цитата Олег М @ 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 лишним не будет.