Расщепление струны, используя буст

Это хорошая идея? По какой-то причине я думал, что это должно быть быстрее, чем буст-токенизатор или сплит однако большую часть времени я застреваю в boost :: spirit :: compile

template <typename Iterator>
struct ValueList : bsq::grammar<Iterator, std::vector<std::string>()>
{
ValueList(const std::string& sep, bool isCaseSensitive) : ValueList::base_type(query)
{
if(isCaseSensitive)
{
query = value >> *(sep >> value);
value = *(bsq::char_ - sep);
}
else
{
auto separator = bsq::no_case[sep];
query = value >> *(separator >> value);
value = *(bsq::char_ - separator);
}
}
bsq::rule<Iterator, std::vector<std::string>()> query;
bsq::rule<Iterator, std::string()> value;
};

inline bool Split(std::vector<std::string>& result, const std::string& buffer, const std::string& separator,
bool isCaseSensitive)
{
result.clear();
ValueList<std::string::const_iterator> parser(separator, isCaseSensitive);
auto itBeg = buffer.begin();
auto itEnd = buffer.end();
if(!(bsq::parse(itBeg, itEnd, parser, result) && (itBeg == itEnd)))
result.push_back(buffer);
return true;
}

Я реализовал это, как показано выше. Что не так с моим кодом? или только потому, что разделитель определен во время выполнения, перекомпиляция неизбежна?

EDIT001:
Пример и сравнение с возможной реализацией с boost :: split и оригинальным imp с tokenizer на CoLiRu
Похоже, колиру сейчас нет. В любом случае это результат для 1M запусков на строку «2lkhj309 | ioperwkl | 20sdf39i | rjjdsf | klsdjf230o | kx23904iep2 | xp39f4p2 | xlmq2i3219» с разделителем «|»

8000000 разбивается за 1081мс.
8000000 разбивается за 1169мс.
8000000
распадается в 2663мс.

первый для токенизатора, второй для boost :: split и третий для boost :: spirit

1

Решение

Во-первых, разные версии не делают одно и то же:

  • в частности, сжатие токенов ведет себя иначе (я исправил это для boost::split но это не похоже на функцию для boost::tokenizer)
  • разделители обрабатывались как строковые литералы, а не как наборы символов в версии Spirit (исправлено)

Да, перекомпиляции неизбежны с динамическими разделителями. Но нет, это не узкое место (другие подходы также имеют динамические разделители):


Я сделал некоторые оптимизации. Сроки:

  • Coliru Clang ++:

    8000000 original (boost::tokenizer) rate: 2.84257μs
    10000000 possible (boost::split) rate: 3.09941μs
    10000000 spirit (dynamic version) rate: 1.45456μs
    10000000 spirit (direct version, avoid type erasure) rate: 1.25588μs
    
    next step:
    10000000 spirit (precompiled sep) rate: 1.18059μs
    
  • Coliru G ++

    8000000 original (boost::tokenizer) rate: 2.92805μs
    10000000 possible (boost::split) rate: 2.75442μs
    10000000 spirit (dynamic version) rate: 1.32821μs
    10000000 spirit (direct version, avoid type erasure) rate: 1.10712μs
    
    next step:
    10000000 spirit (precompiled sep) rate: 1.0791μs
    
  • Локальная система g ++:

    sehe@desktop:/tmp$ time ./test
    8000000 original (boost::tokenizer) rate: 1.80061μs
    10000000 possible (boost::split) rate: 1.29754μs
    10000000 spirit (dynamic version) rate: 0.607789μs
    10000000 spirit (direct version, avoid type erasure) rate: 0.488087μs
    
    next step:
    10000000 spirit (precompiled sep) rate: 0.498769μs
    

Как видите, подход Духа не должен быть медленнее. Какие шаги я предпринял? http://paste.ubuntu.com/11001344/

  • тест рефактора для отображения скорости (без изменений) 3.523μs
  • сделал case_insensitivity выбор вызывающего абонента (просто используйте no_case[char_(delimiter)] если необходимо) 2.742μs.
  • Устранить value subrule (сокращенное копирование и динамическая отправка из-за нетерминального правила стертого типа) 2.579μs.
  • Сделан разделитель символов charset вместо строкового литерала: 2.693μs.

    увидеть промежуточная версия на колиру. (Я рекомендую приведенный ниже код, он гораздо более очищен)

  • Использование qi :: raw [] вместо синтезированных атрибутов std :: string (избегайте копирования!) 0.624072μs

  • Устранение всех нетерминалов (то есть стирание типа; см. spirit_direct реализация) ставка: 0.491011μs

Теперь кажется вполне очевидным, что все реализации выиграют от того, что не «компилируют» разделитель каждый раз. Я сделал это не для всех подходов, но для развлечения давайте сделаем это для версии Spirit:

  • Использование жестко закодированных ‘|’ ограничитель 0.455269μs // фиксированный разделитель

Полный список:

Жить на Колиру

#include <boost/algorithm/string.hpp>
#include <boost/tokenizer.hpp>
#include <boost/spirit/include/qi.hpp>

#include <vector>
#include <string>
#include <chrono>
#include <iostream>

void original(std::vector<std::string>& result, const std::string& input, const std::string& delimiter)
{
result.clear();
boost::char_separator<char> sep(delimiter.c_str());
boost::tokenizer<boost::char_separator<char>, std::string::const_iterator, std::string> tok(input, sep);

for (const auto& token : tok)
{
result.push_back(token);
}
}

void possible(std::vector<std::string>& result, const std::string& input, const std::string& delimiter)
{
result.clear();
boost::split(result, input, boost::is_any_of(delimiter), boost::algorithm::token_compress_off);
}

namespace bsq = boost::spirit::qi;

void spirit_direct(std::vector<std::string>& result, const std::string& input, char const* delimiter)
{
result.clear();
using namespace bsq;
if (!parse(input.begin(), input.end(), raw[*(char_ - char_(delimiter))] % char_(delimiter), result))
result.push_back(input);
}

namespace detail {
template <typename Sep> bsq::rule<std::string::const_iterator, std::vector<std::string>()>
make_spirit_parser(Sep const& sep)
{
using namespace bsq;
return raw[*(char_ - sep)] % sep;
}

static const auto precompiled_pipes = make_spirit_parser('|');
}

void spirit(std::vector<std::string>& result, const std::string& input, char const* delimiter)
{
result.clear();
if (!bsq::parse(input.begin(), input.end(), detail::make_spirit_parser(bsq::char_(delimiter)), result))
result.push_back(input);
}

void spirit_pipes(std::vector<std::string>& result, const std::string& input)
{
result.clear();
if (!bsq::parse(input.begin(), input.end(), detail::precompiled_pipes, result))
result.push_back(input);
}

template <typename F> void bench(std::string const& caption, F approach) {
size_t const iterations = 1000000;
using namespace std::chrono;
using C = high_resolution_clock;

auto start = C::now();

size_t count = 0;
for (auto i = 0U; i < iterations; ++i) {
count += approach();
}

auto us = duration_cast<std::chrono::microseconds>(C::now() - start).count();
std::cout << count << " " << caption << " rate: " << (1.*us/iterations) << "μs\n";
}

int main()
{
std::string const input = "2309|ioperwkl|2039i|rjjdsf|klsdjf230o|kx23904iep2|xp,39,4p2|xlmq2i3219||";
auto separator = "|";

std::vector<std::string> result;

bench("original (boost::tokenizer)", [&] {
original(result, input, separator);
return result.size();
});
bench("possible (boost::split)", [&] {
possible(result, input, separator);
return result.size();
});
bench("spirit (dynamic version)", [&] {
spirit(result, input, separator);
return result.size();
});
bench("spirit (direct version, avoid type erasure)", [&] {
spirit_direct(result, input, separator);
return result.size();
});

std::cout << "\nnext step:\n";
bench("spirit (precompiled sep)", [&] {
spirit_pipes(result, input);
return result.size();
});
}
4

Другие решения


По вопросам рекламы [email protected]