На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
Страницы: (3) [1] 2 3  все  ( Перейти к последнему сообщению )  
> Ручной slipt строки или то же, но с помощью std::regexp - что быстрее?
    Тут на российском сайте для предложений в стандарт появилось новое - предлагают сделать стандартный алгоритм для разбиение строки на подстроки. На что у меня возникло вполне обоснованное возражение: зачем добавлять такой алгоритм, если уже есть regexp'ы. И вот возник вопрос: а действительно, является ли такая замена адекватной и что будет работать быстрее/эффективнее?
      Думаю, просто разбить строку по символу-разделителю будет по-любому эффективенее, чем regexp'ом. Хотя пример, который там показан, довольно тяжеловатый.
        В стандартной библиотеке уже всё есть. Можно пользоваться. :)

        Пример:
        ExpandedWrap disabled
          #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 -
          Как выяснилось, разница довольно существенная - ~20 раз. Но это на такой, довольно простой, задаче.
            Regexp всегда были очень тяжелым механизмом :yes:
            Даже на php обычно получается быстрее. RE2, которые компилируют регулярку в конечный (вроде как) автомат работают значительно быстрее классических регулярок, что реализуют поиск с вовратом, но и это далеко не всегда оправдано.
              Цитата Flex Ferrum @
              Как выяснилось, разница довольно существенная - ~20 раз.

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

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

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

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

                  Там разве не удваивается резерв? Т.е. на первые 6 элементов, в данном случае, память должна выделяться/копироваться 3 раза.
                  Сообщение отредактировано: Олег М -
                    Цитата Олег М @
                    Цитата Flex Ferrum @
                    После первогого прохода цикла в векторе память уже не выделяется,

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

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

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

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


                          Цитата Flex Ferrum @
                          А для всего остального есть регэкспы.

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

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

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

                            Ты когда последний раз scanf'ом то пользовался? :) Этот "относительно простой случай" уже реализован на базе istream'ов. Натравливаешь istream на строку и стримишь из неё то, что нужно, как-то обрабатывая ошибки. :) Самый что ни наесть compile-time.
                              Цитата Flex Ferrum @
                              Как выяснилось, разница довольно существенная - ~20 раз. Но это на такой, довольно простой, задаче.
                              Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров, во-вторых, нужен обобщённый алгоритм. На вот, добавь:
                              ExpandedWrap disabled
                                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 @
                              RE2, которые компилируют регулярку в конечный (вроде как) автомат работают значительно быстрее классических регулярок, что реализуют поиск с вовратом, но и это далеко не всегда оправдано.
                              Кстати, а почему с boost::spirit не сравнили?

                              Добавлено
                              P.S. Походу, [] лишние в разделителе. <_<
                              Сообщение отредактировано: Qraizer -
                                Цитата Qraizer @
                                Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров,

                                Там не линейная зависимость будет?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0395 ]   [ 17 queries used ]   [ Generated: 28.03.24, 11:53 GMT ]