c ++ 11正则表达式比python慢

Question

嗨,我想了解为什么以下代码使用正则表达式进行拆分字符串拆分

#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

Answer 1

注意

另请参阅此答案: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

最终的改进是有一个std::vector的const char *作为回报,其中每个字符指针会指向原来的内子s C字符串本身.问题是,你不能这样做,因为它们中的每一个都不会被终止(为此,请参阅string_ref后面的示例中的C++ 1y的用法).

最后的改进也可以通过以下方式实现:

#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(来自主干)和-O3构建了样本.也许其他正则表达式库能够更好地执行,但无论如何,分配/解除分配通常会影响性能.

Boost.Regex

这是boost::regex用于定时C字符串参数样品:

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

相同的代码boost::regex和std::regex此示例中的接口是相同的,只需更改命名空间和include.

祝愿它随着时间的推移变得更好,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;
}

对于带向量返回的情况,返回向量string_ref而不是string副本也会更便宜split.

编辑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

请注意,与之前的结果相比,这有多快.当然,它不是填充vector循环内部(也不是预先匹配任何东西),但是无论如何你得到一个范围,你可以for使用基于范围的范围,甚至用它来填充a vector.

作为原始(或空终止字符串)上的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输出参数版本相比没有太大区别.

另请注意,有一个提案std::split可以像这样工作.

Answer 2

对于优化,通常,您希望避免两件事:

• 为不必要的东西烧掉CPU周期
• 等待某事发生(内存读取,磁盘读取,网络读取......)

这两者可能是对立的,因为有时它最终会比在内存中缓存所有内容更快地计算某些内容......所以这是一场平衡游戏.

让我们分析你的代码:

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +"); // only computed once

    // search for first occurrence of rsplit
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);

    auto rend = std::sregex_token_iterator();

    // simultaneously:
    // - parses "s" from the second to the past the last occurrence
    // - allocates one `std::string` for each match... at least! (there may be a copy)
    // - allocates space in the `std::vector`, possibly multiple times
    auto res = std::vector<std::string>(rit, rend);

    return res;
}

我们可以做得更好吗？好吧,如果我们可以重用现有存储而不是保持分配和释放内存,我们应该看到一个显着的改进[1]:

// Overwrites 'result' with the matches, returns the number of matches
// (note: 'result' is never shrunk, but may be grown as necessary)
size_t split(std::string const& s, std::vector<std::string>& result){
    static const std::regex rsplit(" +"); // only computed once

    auto rit = std::cregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::cregex_token_iterator();

    size_t pos = 0;

    // As long as possible, reuse the existing strings (in place)
    for (size_t max = result.size();
         rit != rend && pos != max;
         ++rit, ++pos)
    {
        result[pos].assign(rit->first, rit->second);
    }

    // When more matches than existing strings, extend capacity
    for (; rit != rend; ++rit, ++pos) {
        result.emplace_back(rit->first, rit->second);
    }

    return pos;
} // split

在你进行测试,其中子匹配的数量是整个迭代常量,这个版本是不可能被击败的:它只会在第一次运行(无论是分配内存rsplit和result),然后不断重复使用现有的存储器.

[1]:免责声明,我只证明这个代码是正确的我还没有测试过(正如Donald Knuth所说).