Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.22.249.158] |
|
Страницы: (3) [1] 2 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Тут на российском сайте для предложений в стандарт появилось новое - предлагают сделать стандартный алгоритм для разбиение строки на подстроки. На что у меня возникло вполне обоснованное возражение: зачем добавлять такой алгоритм, если уже есть regexp'ы. И вот возник вопрос: а действительно, является ли такая замена адекватной и что будет работать быстрее/эффективнее?
|
Сообщ.
#2
,
|
|
|
Думаю, просто разбить строку по символу-разделителю будет по-любому эффективенее, чем regexp'ом. Хотя пример, который там показан, довольно тяжеловатый.
|
Сообщ.
#3
,
|
|
|
В стандартной библиотеке уже всё есть. Можно пользоваться.
Пример: #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; } Бьёт строку по запятым и "съедает" пробелы. |
Сообщ.
#4
,
|
|
|
Как выяснилось, разница довольно существенная - ~20 раз. Но это на такой, довольно простой, задаче.
|
Сообщ.
#5
,
|
|
|
Regexp всегда были очень тяжелым механизмом
Даже на php обычно получается быстрее. RE2, которые компилируют регулярку в конечный (вроде как) автомат работают значительно быстрее классических регулярок, что реализуют поиск с вовратом, но и это далеко не всегда оправдано. |
Сообщ.
#6
,
|
|
|
Цитата Flex Ferrum @ Как выяснилось, разница довольно существенная - ~20 раз. Кто б сомневался. Хотя, разница должна быть ещё больше. С учётом того, что в splitLineRaw большая часть времени тратится на создание std::string и добавление её в вектор, а в splitLineRegEx - на поиск. |
Сообщ.
#7
,
|
|
|
Цитата Олег М @ Цитата Flex Ferrum @ Как выяснилось, разница довольно существенная - ~20 раз. Кто б сомневался. Хотя, разница должна быть ещё больше. С учётом того, что в splitLineRaw большая часть времени тратится на создание std::string и добавление её в вектор, а в splitLineRegEx - на поиск. Временем на создание строки можно пренебречь. После первогого прохода цикла в векторе память уже не выделяется, а в строке работает small string optimization (в gcc-версии), и память тоже не выделяется. Таким образом просто символы копируются. Мне, собственно, была даже больше интересна разница между бустом и регулярками, ибо простой "чистый" спит - явление не то, чтобы частое. Нередко встречаются ситуации, когда сплитить надо по символу или символами, а полученные куски строки - чистить от пробелов. В этом случае алгоритм усложняется и регулярки могут стать более подходящим решением. |
Сообщ.
#8
,
|
|
|
Цитата Flex Ferrum @ После первогого прохода цикла в векторе память уже не выделяется, Там разве не удваивается резерв? Т.е. на первые 6 элементов, в данном случае, память должна выделяться/копироваться 3 раза. |
Сообщ.
#9
,
|
|
|
Цитата Олег М @ Цитата Flex Ferrum @ После первогого прохода цикла в векторе память уже не выделяется, Там разве не удваивается резерв? Т.е. на первые 6 элементов память, в данном случае, должна выделяться/коироваться 3 раза. Это совершенно не важно. Важно, что clear память не освобождает. |
Сообщ.
#10
,
|
|
|
Ну да, не обратил внимания.
А вообще, тоже не вижу особой необходимости вносить такой сплит в стандарт (хотя, и range-for тоже не вижу, но удобно). Лучше бы сделали какой-нибудь парсер, чтоб можно было разбирать строку за один проход. |
Сообщ.
#11
,
|
|
|
Цитата Олег М @ Лучше бы сделали какой-нибудь парсер, чтоб можно было разбирать строку за один проход. Я так понимаю, что в общем случае это невозможно. А для всего остального есть регэкспы. |
Сообщ.
#12
,
|
|
|
Цитата Flex Ferrum @ Я так понимаю, что в общем случае это невозможно. Почему? Относительно простые случаи, типа scanf, вполне возможно перенести в compile-time. А другое и не нужно. Цитата Flex Ferrum @ А для всего остального есть регэкспы. Regexp - не вариант, очень медленный. Большой поток данных им особо не напарсишься, |
Сообщ.
#13
,
|
|
|
Цитата Олег М @ Regexp - не вариант, очень медленный Как видишь, "очень" - это понятие относительное. Если считать boost::split более менее универсальным вариантом split'а - то регэксп медленнее "всего" в два раза. Для ряда задач это может быть вполне приемлемо. Цитата Олег М @ Относительно простые случаи, типа scanf, вполне возможно перенести в compile-time. Ты когда последний раз scanf'ом то пользовался? Этот "относительно простой случай" уже реализован на базе istream'ов. Натравливаешь istream на строку и стримишь из неё то, что нужно, как-то обрабатывая ошибки. Самый что ни наесть compile-time. |
Сообщ.
#14
,
|
|
|
Цитата Flex Ferrum @ Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров, во-вторых, нужен обобщённый алгоритм. На вот, добавь:Как выяснилось, разница довольно существенная - ~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 @ Кстати, а почему с boost::spirit не сравнили? RE2, которые компилируют регулярку в конечный (вроде как) автомат работают значительно быстрее классических регулярок, что реализуют поиск с вовратом, но и это далеко не всегда оправдано. Добавлено P.S. Походу, [] лишние в разделителе. |
Сообщ.
#15
,
|
|
|
Цитата Qraizer @ Некорректное сравнение. Во-первых, разделителей должно быть больше одного для всех примеров, Там не линейная зависимость будет? |