質問

こんにちは、私は正規表現を使用して文字列の分割を行う次のコードの理由を理解したいと思います。

#include<regex>
#include<vector>
#include<string>

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +");
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::sregex_token_iterator();
    auto res = std::vector<std::string>(rit, rend);
    return res;
}

int main(){
    for(auto i=0; i< 10000; ++i)
       split("a b c", " ");
    return 0;
}

は、次の Python コードより遅いです。

import re
for i in range(10000):
    re.split(' +', 'a b c')

ここで

> python test.py  0.05s user 0.01s system 94% cpu 0.070 total
./test  0.26s user 0.00s system 99% cpu 0.296 total

OSXでclang++を使用しています。

O3 でコンパイルすると、以下のようになります。 0.09s user 0.00s system 99% cpu 0.109 total

どのように解決するのですか？

お知らせ

こちらの回答もご覧ください。 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

---

これは、vectorやstringオブジェクトの構築/割り当てを避けるための最適化です。

#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%に近いパフォーマンス向上です。

vectorはループの前に作成され、最初の反復でそのメモリを成長させることができます。その後は clear() によるメモリの解放はなく、vector はメモリを保持し、文字列 をインプレースで .

---

もうひとつのパフォーマンス向上は、建設/破壊を避けることです。 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

究極の改良点は std::vector の const char * の中の部分文字列を指し示すことになります。 s c文字列 といった具合になります。問題は、それぞれがヌル終端でないため、それができないことです（これについては、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文字列 引数のサンプルです。

real    0m1.284s
user    0m1.278s
sys     0m0.005s

同じコードで boost::regex と std::regex のインターフェースは同じで、名前空間とインクルードを変更するだけです。

C++ stdlib regexの実装はまだ初期段階なので、時間が経つにつれて良くなることを祈っています。

EDIT

念のため、これ（上記の "究極の改善案）を試してみましたが、同等のパフォーマンスの向上はありませんでした。 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

この新しいソリューションは、returnで出力を得ることができます。私はMarshall Clowの string_view ( string_ref はリネームされました) libc++ の実装は次の場所で見つかりました。 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);
    }
}

タイミング

real    0m0.385s
user    0m0.385s
sys     0m0.000s

これまでの結果と比較して、いかに高速であるかに注目してください。もちろん、これは vector を埋めているわけではありませんが (おそらく事前に何かをマッチングしているわけでもありません)、 とにかく範囲を取得し、それを範囲ベースの for で範囲指定することもできますし、それを使って vector .

を超える範囲として iterator_range は string_view の上に、オリジナルの string (または nullで終端する文字列 を使用すると、非常に軽量になり、不必要な文字列の割り当てを発生させることがありません。

比較のために 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 のような動作になります。