boost :: tokenizer vs boost :: split

Question

我试图将每个'^'字符上的c ++字符串解析为矢量标记.我一直使用boost :: split方法,但我现在正在编写性能关键代码,并想知道哪一个提供了更好的性能.

例如:

string message = "A^B^C^D";
vector<string> tokens;
boost::split(tokens, message, boost::is_any_of("^"));

与

boost::char_separator<char> sep("^");
boost::tokenizer<boost::char_separator<char> > tokens(text, sep);

哪一个会提供更好的性能？为什么？

Answer 1

最好的选择取决于几个因素.如果您只需要扫描一次令牌,那么boost :: tokenizer在运行时和空间性能方面都是一个不错的选择(这些令牌向量会占用大量空间,具体取决于输入数据.)

如果你要经常扫描令牌,或者需要一个有效随机访问的向量,那么boost :: split成一个向量可能是更好的选择.

例如,在令牌长度为1字节的"A ^ B ^ C ^ ... ^ Z"输入字符串中,该boost::split/vector<string>方法将消耗至少 2*N-1个字节.通过字符串存储在大多数STL实现中的方式,您可以确定它的计数超过8倍.将这些字符串存储在向量中在内存和时间方面是昂贵的.

我在我的机器上运行了一个快速测试,类似的模式有1000万个令牌,如下所示:

• boost :: split = 2.5s和~620MB
• boost :: tokenizer = 0.9s和0MB

如果您只是对令牌进行一次性扫描,那么显然令牌器更好.但是,如果您在应用程序的生命周期中粉碎成要重用的结构,则可能首选使用标记向量.

如果你想去矢量路线,那么我建议不要使用a vector<string>,而是使用string :: iterators的矢量.只需粉碎成一对迭代器并保留你的大串令牌以供参考.例如:

using namespace std;
vector<pair<string::const_iterator,string::const_iterator> > tokens;
boost::split(tokens, s, boost::is_any_of("^"));
for(auto beg=tokens.begin(); beg!=tokens.end();++beg){
   cout << string(beg->first,beg->second) << endl;
}

这个改进的版本在同一台服务器和测试上需要1.6s和390MB.并且,最重要的是,此向量的内存开销与令牌的数量呈线性关系 - 不依赖于令牌的长度,而是std::vector<string>存储每个令牌.

Answer 2

我发现使用相当不同的结果clang++ -O3 -std=c++11 -stdlib=libc++.

首先,我提取了一个文本文件,其中包含逗号分隔的~470k字,没有换行符,如下所示:

path const inputPath("input.txt");

filebuf buf;
buf.open(inputPath.string(),ios::in);
if (!buf.is_open())
    return cerr << "can't open" << endl, 1;

string str(filesystem::file_size(inputPath),'\0');
buf.sgetn(&str[0], str.size());
buf.close();

然后我运行了各种定时测试,将结果存储到运行之间清除的预先大小的矢量中,例如,

void vectorStorage(string const& str)
{
    static size_t const expectedSize = 471785;

    vector<string> contents;
    contents.reserve(expectedSize+1);

    ...

    {
        timed _("split is_any_of");
        split(contents, str, is_any_of(","));
    }
    if (expectedSize != contents.size()) throw runtime_error("bad size");
    contents.clear();

    ...
}

作为参考,计时器就是这样的:

struct timed
{
    ~timed()
    {
        auto duration = chrono::duration_cast<chrono::duration<double, ratio<1,1000>>>(chrono::high_resolution_clock::now() - start_);

        cout << setw(40) << right << name_ << ": " << duration.count() << " ms" << endl;
    }

    timed(std::string name="") :
        name_(name)
    {}


    chrono::high_resolution_clock::time_point const start_ = chrono::high_resolution_clock::now();
    string const name_;
};

我还计时了一次迭代(没有矢量).结果如下:

Vector: 
                              hand-coded: 54.8777 ms
                         split is_any_of: 67.7232 ms
                     split is_from_range: 49.0215 ms
                               tokenizer: 119.37 ms
One iteration:
                               tokenizer: 97.2867 ms
                          split iterator: 26.5444 ms
            split iterator back_inserter: 57.7194 ms
                split iterator char copy: 34.8381 ms

令牌器比这慢得多split,一次迭代图甚至不包括字符串副本:

{
    string word;
    word.reserve(128);

    timed _("tokenizer");
    boost::char_separator<char> sep(",");
    boost::tokenizer<boost::char_separator<char> > tokens(str, sep);

    for (auto range : tokens)
    {}
}

{
    string word;

    timed _("split iterator");
    for (auto it = make_split_iterator(str, token_finder(is_from_range(',', ',')));
         it != decltype(it)(); ++it)
    {
        word = move(copy_range<string>(*it));
    }
}

明确的结论:使用split.