您好, 欢迎来到 !    登录 | 注册 | | 设为首页 | 收藏本站

c ++ 11 regex比python慢

c ++ 11 regex比python慢

我将循环数增加到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::vectorconst char *作为回报,其中每个字符指针会指向原来的内子s C字符串 本身。问题是,您不能这样做,因为它们中的每一个都不会被null终止(为此,请参阅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;
}

我已经用-O3用clang 3.3(从主干)构建了示例。也许其他正则表达式库可以执行得更好,但是在任何情况下,分配/解除分配通常都会影响性能

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

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

此示例中相同的代码boost::regexstd::regex接口是相同的,只是需要更改名称空间和包含。

C ++ stdlib regex实现正处于起步阶段,它祝愿它随着时间的推移变得更好。

为了完善起见,我尝试了这一点(上面提到的“最终改进”建议),但是它并没有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;
}

对于带有vector return的情况,返回vectorstring_ref而不是string副本也将更便宜split

这个新的解决方案能够通过返回获得输出。我使用了在https://github.com/mclow/string_view中找到的MarshallClow的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使用基于范围的范围进行范围调整,甚至可以使用它来填充vector

作为测距在iterator_range创建string_view一个多原稿S 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可以像这样工作。

python 2022/1/1 18:53:12 有510人围观

撰写回答


你尚未登录,登录后可以

和开发者交流问题的细节

关注并接收问题和回答的更新提醒

参与内容的编辑和改进,让解决方法与时俱进

请先登录

推荐问题


联系我
置顶