Boost:: tokenizer vs boost:: split

Ответ 1

Лучший выбор зависит от нескольких факторов. Если вам нужно только сканировать токены один раз, то boost:: tokenizer является хорошим выбором как в производительности, так и в пространстве (эти векторы токенов могут занимать много места, в зависимости от входных данных.)

Если вы собираетесь часто сканировать токены или нужен вектор с эффективным случайным доступом, то более эффективным вариантом может быть boost:: split в вектор.

Например, в вашей входной строке "A ^ B ^ C ^... ^ Z", где токены имеют длину 1 байт, метод boost::split/vector<string> будет потреблять не менее 2 * N-1 байт. С тем, как строки хранятся в большинстве реализаций STL, вы можете понять, что они принимают более 8x, которые считаются. Сохранение этих строк в векторе является дорогостоящим с точки зрения памяти и времени.

Я провел быстрый тест на своей машине, и аналогичная модель с 10 миллионами токенов выглядела так:

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

Если вы просто выполняете одноразовое сканирование токенов, то ясно, что токенизатор лучше. Но, если вы измельчаете структуру, которую хотите повторно использовать в течение всего срока службы вашего приложения, то предпочтительным может быть вектор токенов.

Если вы хотите пройти векторный маршрут, я бы рекомендовал не использовать 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,6 с и 390 МБ на том же сервере и тесте. И, что лучше всего накладных расходов на память этого вектора, является линейным с количеством токенов - никак не зависит от длины токенов, тогда как a std::vector<string> хранит каждый токен.

Ответ 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.

Ответ 3

Это может зависеть от вашей версии boost и того, как вы являетесь функциональностью.

У нас была проблема с производительностью в некоторой логике, которая использовала boost:: split 1.41.0 для обработки тысяч или сотен тысяч меньших строк (ожидалось менее 10 токенов). Когда я запускал код с помощью анализатора производительности, мы обнаружили, что в boost:: split было потрачено удивительное 39% времени.

Мы пробовали некоторые простые "исправления", которые не влияли на производительность материально, как "мы знаем, что у нас не будет более 10 элементов на каждом проходе, поэтому предварительно установите вектор на 10 элементов".

Поскольку нам фактически не нужен вектор и он мог просто перебирать маркеры и выполнять одну и ту же работу, мы изменили код на boost:: tokenize, а тот же раздел кода упал до 1% от времени выполнения.