我在 StackOverflow 上研究了一些时间,以找到将具有多个分隔符的字符串拆分为 vector< string >
的良好算法。 .我也找到了一些方法:
boost 方式:
boost::split(vector, string, boost::is_any_of(" \t"));
getline
方法:
std::stringstream ss(string);
std::string item;
while(std::getline(ss, item, ' ')) {
vector.push_back(item);
}
Boost的tokenize方式:
char_separator<char> sep(" \t");
tokenizer<char_separator<char>> tokens(string, sep);
BOOST_FOREACH(string t, tokens)
{
vector.push_back(t);
}
还有很酷的 STL 方式:
istringstream iss(string);
copy(istream_iterator<string>(iss),
istream_iterator<string>(),
back_inserter<vector<string> >(vector));
以及Shadow2531的方法(见链接主题)。
大部分来自this topic .但不幸的是,他们并没有解决我的问题:
Boost 的拆分很容易使用,但是对于大数据(最好情况下大约 1.5*10^6 个单个元素)和大约 10 个分隔符,我使用它的速度非常慢。
getline
, STL 和 Shadow2531 的方法都有一个问题,就是我只能用一个字符作为分隔符。我还需要一些。Boost 的 tokenize 在速度方面更加可怕。用 10 个分隔符将一个字符串拆分为 1.5*10^6 个元素需要 11 秒。
所以我不知道该怎么办:我想要一个非常快速的字符串拆分算法,带有多个分隔符。
Boost 的拆分是最大的还是有办法更快?
最佳答案
想到两件事:
- 使用字符串 View 而不是字符串 作为拆分结果,节省了很多 分配。
- 如果你知道你只是
将使用字符(在
[0,255] 范围),尝试使用
bitset 来测试成员资格而不是
查找
进入分隔符 字符。
以下是应用这些想法的快速尝试:
#include <vector>
#include <bitset>
#include <iostream>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/timer.hpp>
using namespace std;
size_t const N = 10000000;
template<typename C>
void test_custom(string const& s, char const* d, C& ret)
{
C output;
bitset<255> delims;
while( *d )
{
unsigned char code = *d++;
delims[code] = true;
}
typedef string::const_iterator iter;
iter beg;
bool in_token = false;
for( string::const_iterator it = s.begin(), end = s.end();
it != end; ++it )
{
if( delims[*it] )
{
if( in_token )
{
output.push_back(typename C::value_type(beg, it));
in_token = false;
}
}
else if( !in_token )
{
beg = it;
in_token = true;
}
}
if( in_token )
output.push_back(typename C::value_type(beg, s.end()));
output.swap(ret);
}
template<typename C>
void test_strpbrk(string const& s, char const* delims, C& ret)
{
C output;
char const* p = s.c_str();
char const* q = strpbrk(p+1, delims);
for( ; q != NULL; q = strpbrk(p, delims) )
{
output.push_back(typename C::value_type(p, q));
p = q + 1;
}
output.swap(ret);
}
template<typename C>
void test_boost(string const& s, char const* delims)
{
C output;
boost::split(output, s, boost::is_any_of(delims));
}
int main()
{
// Generate random text
string text(N, ' ');
for( size_t i = 0; i != N; ++i )
text[i] = (i % 2 == 0)?('a'+(i/2)%26):((i/2)%2?' ':'\t');
char const* delims = " \t[],-'/\\!\"§$%&=()<>?";
// Output strings
boost::timer timer;
test_boost<vector<string> >(text, delims);
cout << "Time: " << timer.elapsed() << endl;
// Output string views
typedef string::const_iterator iter;
typedef boost::iterator_range<iter> string_view;
timer.restart();
test_boost<vector<string_view> >(text, delims);
cout << "Time: " << timer.elapsed() << endl;
// Custom split
timer.restart();
vector<string> vs;
test_custom(text, delims, vs);
cout << "Time: " << timer.elapsed() << endl;
// Custom split
timer.restart();
vector<string_view> vsv;
test_custom(text, delims, vsv);
cout << "Time: " << timer.elapsed() << endl;
// Custom split
timer.restart();
vector<string> vsp;
test_strpbrk(text, delims, vsp);
cout << "Time: " << timer.elapsed() << endl;
// Custom split
timer.restart();
vector<string_view> vsvp;
test_strpbrk(text, delims, vsvp);
cout << "Time: " << timer.elapsed() << endl;
return 0;
}
使用启用了 -O4
标志的 GCC 4.5.1 使用 Boost 1.46.1 编译它,我得到:
- 时间:5.951(Boost.Split + vector )
- 时间:3.728(Boost.Split + vector
- 时间:1.662(自定义分割+ vector )
- 时间:0.144(自定义分割+ vector )
- 时间:2.13(Strpbrk + vector )
- 时间:0.527(Strpbrk + vector )
注意:由于我的自定义函数删除了空标记,因此输出略有不同。但是,如果您决定使用它,您可以根据您的需要调整此代码。
关于c++ - 使用多个分隔符进行快速字符串拆分,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5505965/