知らせ
この回答も参照してください: https://stackoverflow.com/a/21708215は、ここの下部にある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;
}
タイミング：
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;
}
タイミング：
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;
}
}
タイミング：
real 0m2.509s
user 0m2.503s
sys 0m0.004s
最終的な改善は、各 char ポインターが元のc 文字列自体の内部の部分文字列を指すように、 std::vectorofを返すことです。問題は、それらのそれぞれが null で終了しないため、それを行うことができないことです (これについては、後のサンプルで C++1y の使用法を参照してください)。const char *s 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;
}
-O3 を指定して (trunk から) clang 3.3 でサンプルをビルドしました。他の正規表現ライブラリの方がパフォーマンスが向上する可能性がありますが、いずれにせよ、割り当て/割り当て解除はパフォーマンス ヒットになることがよくあります。
Boost.Regex
これは、 C 文字列引数のサンプルのboost::regexタイミングです。
real 0m1.284s
user 0m1.278s
sys 0m0.005s
このサンプルの同じコードboost::regexとstd::regexインターフェイスは同じで、名前空間とインクルードを変更するだけで済みます。
時間が経つにつれて改善されることを願っています。C++ 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;
}
また、 with vector returnの場合、コピーではstring_refなくvector を返す方が安くなります。stringsplit
編集2
この新しいソリューションは、リターンによって出力を取得できます。https://github.com/mclow/string_viewにあるMarshall Clow のstring_view(string_ref名前が変更された) libc++ 実装を使用しました。
#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);
}
}
タイミング：
real 0m0.385s
user 0m0.385s
sys 0m0.000s
これが以前の結果と比較してどれほど速いかに注目してください。もちろん、ループ内で a を埋めるわけではありません(また、おそらく事前に何かを照合することもvectorありません) が、とにかく範囲を取得します。forvector
元の(またはnull で終了する string ) の createに及ぶため、これは非常に軽量になり、不要な文字列割り当てが生成されることはありませんiterator_range。string_viewstring
この実装を使用して比較するだけです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ご覧のとおり、最適化された出力パラメーター バージョンと比較して大きな違いはありません。
このように機能する a の提案があるstd::splitことにも注意してください。