#c #c #string #visual-studio-2010 #tokenize
#c #c #строка #visual-studio-2010 #токенизировать
Вопрос:
Я работаю над приложением на C / C (в Visual Studio 2010), где мне нужно токенизировать строку, разделенную запятой, и я хотел бы, чтобы это было сделано как можно быстрее. В настоящее время я использую strtok_s . Я провел несколько тестов strtok_s versus sscanf , и мне показалось, что strtok_s это было быстрее (если только я не написал ужасную реализацию :)), но мне было интересно, может ли кто-нибудь предложить более быструю альтернативу.
Комментарии:
1. Я не думаю, что в C вы сможете найти более быструю альтернативу
strtok()(или дажеstrtok_s()— что бы это ни было). Еслиstrtok()вас устраивает, используйте это.2. Придирка: такого языка под названием «C / C » не существует. Это C или Си ? Они разные.
3. Спасибо за быстрые ответы, ребята, изначально у меня был тот же ход мыслей, что и у pmg. Однако, чтобы быть тщательным, я собираюсь создать прототип этих ответов, а затем рассчитать их время и опубликовать результаты для дальнейшего использования.
4. Наилучшие методы для многих вещей отличаются между C и C . Если вы работаете на одном из них, вам нужна наилучшая практика для этого языка. Если вы работаете в обоих, вам, вероятно, нужны две разные рекомендации.
5. @David ya точно, я в основном пытался спросить, что это такое и какой из них самый быстрый. Мне просто любопытно сравнить их, поскольку мне доступны оба варианта, и суть в том, что мне нужно, чтобы это было как можно быстрее. Я опубликую результаты позже, спасибо 🙂
Ответ №1:
Ответ №2:
Лучшее, что вы можете сделать, это убедиться, что вы просматриваете строку только один раз, и создаете вывод на лету. Начните извлекать символы из временного буфера, и когда вы столкнетесь с разделителем, сохраните временный буфер в выходной коллекции, очистите временный буфер, промойте и повторите.
Вот базовая реализация, которая делает это.
template<class C=char>
struct basic_token
{
typedef std::basic_string<C> token_string;
typedef unsigned long size_type;
token_string token_, delim_;
basic_token(const token_stringamp; token, const token_stringamp; delim = token_string());
};
template<class C>
basic_token<C>::basic_token(const token_stringamp; token, const token_stringamp; delim)
: token_(token),
delim_(delim)
{
}
typedef basic_token<char> token;
template<class Char, class Iter> void tokenize(const std::basic_string<Char>amp; line, const Char* delims, Iter itx)
{
typedef basic_token<Char> Token;
typedef std::basic_string<Char> TString;
for( TString::size_type tok_begin = 0, tok_end = line.find_first_of(delims, tok_begin);
tok_begin != TString::npos; tok_end = line.find_first_of(delims, tok_begin) )
{
if( tok_end == TString::npos )
{
(*itx ) = Token(TString(amp;line[tok_begin]));
tok_begin = tok_end;
}
else
{
(*itx ) = Token(TString(amp;line[tok_begin], amp;line[tok_end]), TString(1, line[tok_end]));
tok_begin = tok_end 1;
}
}
}
template<class Char, class Iter> void tokenize(const Char* line, const Char* delim, Iter itx)
{
tokenize(std::basic_string<Char>(line), delim, itx);
}
template<class Stream, class Token> Streamamp; operator<<(Streamamp; os, const Tokenamp; tok)
{
os << tok.token_ << "t[" << tok.delim_ << "]";
return os;
}
…который вы бы использовали следующим образом:
string raw = "35=BW|49=TEST|1346=REQ22|1355=2|1182=88500|1183=88505|10=087^";
vector<stoken> tokens;
tokenize(raw, "|", back_inserter(tokens));
copy(tokens.begin(), tokens.end(), ostream_iterator<stoken>(cout, "n"));
Вывод:
35=BW [|]
49=TEST [|]
1346=REQ22 [|]
1355=2 [|]
1182=88500 [|]
1183=88505 [|]
10=087^ []
Ответ №3:
Я хотел бы напомнить вам, что в strtok и подобных ему системах существует риск того, что вы можете получить обратно другое количество токенов, чем вам хотелось бы.
one|two|three would yield 3 tokens
в то время как
one|||three would yield 2.
Ответ №4:
Тест mmhmm неправильно использовал spirit, его грамматика является недостатком.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/spirit/include/qi.hpp>
/****************************strtok_r************************/
typedef struct sTokenDataC {
char *time;
char *symb;
float bid;
float ask;
int bidSize;
int askSize;
} tokenDataC;
tokenDataC parseTick( char *line, char *parseBuffer )
{
tokenDataC tokenDataOut;
tokenDataOut.time = strtok_r( line,",", amp;parseBuffer );
tokenDataOut.symb = strtok_r( nullptr,",", amp;parseBuffer );
tokenDataOut.bid = atof(strtok_r( nullptr,",", amp;parseBuffer ));
tokenDataOut.ask = atof(strtok_r( nullptr , ",", amp;parseBuffer ));
tokenDataOut.bidSize = atoi(strtok_r( nullptr,",", amp;parseBuffer ));
tokenDataOut.askSize = atoi(strtok_r( nullptr, ",", amp;parseBuffer ));
return tokenDataOut;
}
void test_strcpy_s(int iteration)
{
char *testStringC = new char[64];
char *lineBuffer = new char[64];
printf("test_strcpy_s....n");
strcpy(testStringC,"09:30:00,TEST,13.24,15.32,10,14");
{
timeEstimate<> es;
tokenDataC tokenData2;
for(int i = 0; i < iteration; i )
{
strcpy(lineBuffer, testStringC);//this is more realistic since this has to happen because I want to preserve the line
tokenData2 = parseTick(lineBuffer, testStringC);
//std::cout<<*tokenData2.time<<", "<<*tokenData2.symb<<",";
//std::cout<<tokenData2.bid<<", "<<tokenData2.ask<<", "<<tokenData2.bidSize<<", "<<tokenData2.askSize<<std::endl;
}
}
delete[] lineBuffer;
delete[] testStringC;
}
/****************************strtok_r************************/
/****************************spirit::qi*********************/
namespace qi = boost::spirit::qi;
struct tokenDataCPP
{
std::string time;
std::string symb;
float bid;
float ask;
int bidSize;
int askSize;
void clearTimeSymb(){
time.clear();
symb.clear();
}
};
BOOST_FUSION_ADAPT_STRUCT(
tokenDataCPP,
(std::string, time)
(std::string, symb)
(float, bid)
(float, ask)
(int, bidSize)
(int, askSize)
)
void test_spirit_qi(int iteration)
{
std::string const strs("09:30:00,TEST,13.24,15.32,10,14");
tokenDataCPP data;
auto myString = *~qi::char_(",");
auto parser = myString >> "," >> myString >> "," >> qi::float_ >> "," >> qi::float_ >> "," >> qi::int_ >> "," >> qi::int_;
{
std::cout<<("test_spirit_qi....n");
timeEstimate<> es;
for(int i = 0; i < iteration; i){
qi::parse(std::begin(strs), std::end(strs), parser, data);
//std::cout<<data.time<<", "<<data.symb<<", ";
//std::cout<<data.bid<<", "<<data.ask<<", "<<data.bidSize<<", "<<data.askSize<<std::endl;
data.clearTimeSymb();
}
}
}
/****************************spirit::qi*********************/
int main()
{
int const ITERATIONS = 500 * 10000;
test_strcpy_s(ITERATIONS);
test_spirit_qi(ITERATIONS);
}
Поскольку в clang нет strtok_s, я использую strtok_r для его замены
Выполните итерацию 500 * 10k, время
- test_strcpy_s: 1.40951
- test_spirit_qi: 1.34277
Их время почти одинаковое, не сильно отличается.
компилятор, clang 3.2, -O2
коды времени
Ответ №5:
Это должно быть довольно быстро, без временных буферов, также выделяются пустые токены.
template <class char_t, class char_traits_t,
class char_allocator_t, class string_allocator_t>
inline void _tokenize(
const std::basic_string<char_t, char_traits_t, char_allocator_t>amp; _Str,
const char_tamp; _Tok,
std::vector<std::basic_string<char_t, char_traits_t, char_allocator_t>,
string_allocator_t>amp; _Tokens,
const size_tamp; _HintSz=10)
{
_Tokens.reserve(_HintSz);
const char_t* _Beg(amp;_Str[0]), *_End(amp;_Str[_Str.size()]);
for (const char_t* _Ptr=_Beg; _Ptr<_End; _Ptr)
{
if (*_Ptr == _Tok)
{
_Tokens.push_back(
std::basic_string<char_t, char_traits_t,
char_allocator_t>(_Beg, _Ptr));
_Beg = 1 _Ptr;
}
}
_Tokens.push_back(
std::basic_string<char_t, char_traits_t,
char_allocator_t>(_Beg, _End));
}
Ответ №6:
После тестирования и синхронизации каждого предложенного кандидата результат таков, что strtok явно самый быстрый. Хотя я не удивлен, что моя любовь к тестированию диктовала, что стоит изучить другие варианты. [Примечание: Код был объединен, правки приветствуются 🙂 ]
Учитывая:
typedef struct sTokenDataC {
char *time;
char *symb;
float bid;
float ask;
int bidSize;
int askSize;
} tokenDataC;
tokenDataC parseTick( char *line, char *parseBuffer )
{
tokenDataC tokenDataOut;
tokenDataOut.time = strtok_s( line,",", amp;parseBuffer );
tokenDataOut.symb = strtok_s( null,",", amp;parseBuffer );
tokenDataOut.bid = atof(strtok_s( null,",", amp;parseBuffer ));
tokenDataOut.ask = atof(strtok_s( null , ",", amp;parseBuffer ));
tokenDataOut.bidSize = atoi(strtok_s( null,",", amp;parseBuffer ));
tokenDataOut.askSize = atoi(strtok_s( null, ",", amp;parseBuffer ));
return tokenDataOut;
}
char *testStringC = new char[64];
strcpy(testStringC,"09:30:00,TEST,13.24,15.32,10,14");
int _tmain(int argc, _TCHAR* argv[])
{
char *lineBuffer = new char[64];
printf("Testing method2....n");
for(int i = 0; i < ITERATIONS; i )
{
strcpy(lineBuffer,testStringC);//this is more realistic since this has to happen because I want to preserve the line
tokenData2 = parseTick(lineBuffer,parseBuffer);
}
}
против вызова John Diblings impl через:
struct sTokenDataCPP
{
std::basic_string<char> time;
std::basic_string<char> symb;
float bid;
float ask;
int bidSize;
int askSize;
};
std::vector<myToken> tokens1;
tokenDataCPP tokenData;
printf("Testing method1....n");
for(int i = 0; i < ITERATIONS; i )
{
tokens1.clear();
tokenize(raw, ",", std::back_inserter(tokens1));
tokenData.time.assign(tokens1.at(0).token_);
tokenData.symb.assign(tokens1.at(1).token_);
tokenData.ask = atof(tokens1.at(2).token_.c_str());
tokenData.bid = atof(tokens1.at(3).token_.c_str());
tokenData.askSize = atoi(tokens1.at(4).token_.c_str());
tokenData.bidSize = atoi(tokens1.at(5).token_.c_str());
}
по сравнению с простой реализацией boost.spirit.qi, определяющей грамматику следующим образом:
template <typename Iterator>
struct tick_parser : grammar<Iterator, tokenDataCPP(), boost::spirit::ascii::space_type>
{
tick_parser() : tick_parser::base_type(start)
{
my_string %= lexeme[ (boost::spirit::ascii::char_ ) ];
start %=
my_string >> ','
>> my_string >> ','
>> float_ >> ','
>> float_ >> ','
>> int_ >> ','
>> int_
;
}
rule<Iterator, std::string(), boost::spirit::ascii::space_type> my_string;
rule<Iterator, sTokenDataCPP(), boost::spirit::ascii::space_type> start;
};
с ИТЕРАЦИЯМИ, равными 500 кб:
версия strtok: 2s
версия джона: 115 страниц
ускорение: 172 секунды
Я могу опубликовать полный код, если этого хотят люди, я просто не хотел занимать огромное количество места
Комментарии:
1. Создайте свою собственную версию,
strtok()основанную наstrchr(), для еще более быстрой версии. Вы можете упростить прототип:char *strtokchr(char *src, int ch);; вам не нужно кодировать для нескольких символов «разрыва»; возможно, вы можете работать с последовательными символами «разрыва» по-другому…2. @pmg написал функцию на основе strchr, которая записывалась непосредственно в мою целевую структуру и смогла выполнить 1 миллион итераций за 1 секунду. потрясающее спасибо 🙂
3. УРА! Неплохо. Но не называйте эту функцию так, как я сделал в своем предыдущем комментарии. Этот идентификатор начинается с
strи строчной буквы, поэтому он зарезервирован для реализации. Попробуйтеchrstrtok🙂4. Ваши коды не могут выполняться, особенно грамматика spirit, ее невозможно скомпилировать.1: ошибка пространства имен — вы не добавили пространство имен перед вашими правилами; 2: атрибут синтеза структуры и правило «start» должны быть одного типа. 3. грамматика spirit не выполняет то же самое, что strtok_s. 4. ваша грамматика дает ошибки, она будет анализировать все символы, но не тот шаблон, который вы хотите. Вывод: тщательно протестируйте свои результаты, прежде чем публиковать их