Ответ 1
Примечание
См. также этот ответ: fooobar.com/questions/94443/..., который был базой для EDIT 2 внизу.
Я увеличил цикл до 1000000, чтобы получить лучшую временную меру.
Это мое время на Python:
real 0m2.038s
user 0m2.009s
sys 0m0.024s
Здесь эквивалент вашего кода, немного более красивый:
#include <regex>
#include <vector>
#include <string>
std::vector<std::string> split(const std::string &s, const std::regex &r)
{
return {
std::sregex_token_iterator(s.begin(), s.end(), r, -1),
std::sregex_token_iterator()
};
}
int main()
{
const std::regex r(" +");
for(auto i=0; i < 1000000; ++i)
split("a b c", r);
return 0;
}
Timing:
real 0m5.786s
user 0m5.779s
sys 0m0.005s
Это оптимизация, чтобы избежать построения/выделения векторных и строковых объектов:
#include <regex>
#include <vector>
#include <string>
void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::sregex_token_iterator(s.begin(), s.end(), r, -1);
auto rend = std::sregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
Timing:
real 0m3.034s
user 0m3.029s
sys 0m0.004s
Это почти 100% улучшение производительности.
Вектор создается перед циклом и может вырастить свою память в первой итерации. После этого нет освобождения памяти от clear(), вектор поддерживает память и строит строки на месте.
Еще одно повышение производительности - полностью исключить конструкцию/уничтожение std::string и, следовательно, распределение/удаление его объектов.
Это ориентировочно в этом направлении:
#include <regex>
#include <vector>
#include <string>
void split(const char *s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::cregex_token_iterator(s, s + std::strlen(s), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
Timing:
real 0m2.509s
user 0m2.503s
sys 0m0.004s
Конечным улучшением было бы иметь std::vector of const char * в качестве возврата, где каждый указатель char указывал бы на подстроку внутри самой исходной строки s c. Проблема в том, что вы не можете этого сделать, потому что каждый из них не будет завершен нулем (для этого см. Использование С++ 1y string_ref в более позднем примере).
Это последнее улучшение также может быть достигнуто с помощью этого:
#include <regex>
#include <vector>
#include <string>
void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v); // the constant string("a b c") should be optimized
// by the compiler. I got the same performance as
// if it was an object outside the loop
return 0;
}
Я создал образцы с clang 3.3 (from trunk) с -O3. Возможно, другие библиотеки регулярных выражений могут работать лучше, но в любом случае распределения/дезадаптации часто являются результативными.
библиотека Boost.regex
Это время boost::regex для примера аргументов c string:
real 0m1.284s
user 0m1.278s
sys 0m0.005s
Тот же код, boost::regex и std::regex интерфейс в этом примере идентичны, просто необходимо изменить пространство имен и включить.
С наилучшими пожеланиями, чтобы улучшить со временем, реализация регулярных выражений С++ stdlib находится в зачаточном состоянии.
ИЗМЕНИТЬ
Для завершения, я пробовал это (вышеупомянутое предложение "окончательное улучшение" ), и он не улучшил производительность эквивалентной версии std::vector<std::string> &v во всем:
#include <regex>
#include <vector>
#include <string>
template<typename Iterator> class intrusive_substring
{
private:
Iterator begin_, end_;
public:
intrusive_substring(Iterator begin, Iterator end) : begin_(begin), end_(end) {}
Iterator begin() {return begin_;}
Iterator end() {return end_;}
};
using intrusive_char_substring = intrusive_substring<const char *>;
void split(const std::string &s, const std::regex &r, std::vector<intrusive_char_substring> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear(); // This can potentially be optimized away by the compiler because
// the intrusive_char_substring destructor does nothing, so
// resetting the internal size is the only thing to be done.
// Formerly allocated memory is maintained.
while(rit != rend)
{
v.emplace_back(rit->first, rit->second);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<intrusive_char_substring> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
Это связано с предложением array_ref и string_ref. Здесь используется пример кода:
#include <regex>
#include <vector>
#include <string>
#include <string_ref>
void split(const std::string &s, const std::regex &r, std::vector<std::string_ref> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.emplace_back(rit->first, rit->length());
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string_ref> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
Также будет дешевле вернуть вектор string_ref, а не string копий для случая split с векторным возвратом.
EDIT 2
Это новое решение может получить результат по возврату. Я использовал Marshall Clow string_view (string_ref получил переименованную) реализацию libС++, найденную в https://github.com/mclow/string_view.
#include <string>
#include <string_view>
#include <boost/regex.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/transform_iterator.hpp>
using namespace std;
using namespace std::experimental;
using namespace boost;
string_view stringfier(const cregex_token_iterator::value_type &match) {
return {match.first, static_cast<size_t>(match.length())};
}
using string_view_iterator =
transform_iterator<decltype(&stringfier), cregex_token_iterator>;
iterator_range<string_view_iterator> split(string_view s, const regex &r) {
return {
string_view_iterator(
cregex_token_iterator(s.begin(), s.end(), r, -1),
stringfier
),
string_view_iterator()
};
}
int main() {
const regex r(" +");
for (size_t i = 0; i < 1000000; ++i) {
split("a b c", r);
}
}
Timing:
real 0m0.385s
user 0m0.385s
sys 0m0.000s
Обратите внимание, как быстрее это сравнивается с предыдущими результатами. Конечно, он не заполняет vector внутри цикла (и, возможно, не соответствует чему-либо заранее), но вы все равно получаете диапазон, который вы можете использовать с диапазоном for или даже использовать его для заполнения vector.
В диапазоне iterator_range создается string_view поверх исходного string (или строки с нулевым завершением), это становится очень легким и никогда не генерирует ненужные выделения строк.
Просто для сравнения, используя эту реализацию split, но на самом деле заполняя vector, мы могли бы сделать это:
int main() {
const regex r(" +");
vector<string_view> v;
v.reserve(10);
for (size_t i = 0; i < 1000000; ++i) {
copy(split("a b c", r), back_inserter(v));
v.clear();
}
}
Это использует алгоритм копирования расширенного диапазона для заполнения вектора на каждой итерации, время:
real 0m1.002s
user 0m0.997s
sys 0m0.004s
Как видно, большая разница по сравнению с оптимизированной версией выходного параметра string_view.
Обратите внимание также на предложение для std::split, которое будет работать следующим образом.