C + + 11 regex 比 python 慢

嗨，我想知道为什么下面的代码使用正则表达式分割字符串

#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

27545 次浏览
小开
最佳答案

通知

也可以看到这个答案: https://stackoverflow.com/a/21708215，它是底部 编辑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

最终的改进是返回 const char *的 std::vector，其中每个字符指针都指向原 s C 字符串本身内部的一个子字符串。问题是，您不能这样做，因为它们中的每一个都不会以 null 结束(对于这一点，请参阅后面示例中 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;
}

我已经用 -O3构建了叮当3.3(来自树干)的样本。也许其他正则表达式库能够执行得更好，但是在任何情况下，分配/释放通常都会对性能造成影响。

加速，正则

这是 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;
}

对于具有向量返回的 split，返回一个 string_ref向量比返回一个 string拷贝更便宜。

编辑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来扩展，甚至可以用它来填充 vector。

当范围超过 iterator_range时，就会在原来的 string(或者 空终止字符串)上创建 string_view，这会变得非常轻量级，从来不会产生不必要的字符串分配。

只是为了比较使用这个 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的建议是这样工作的。

小开

对于优化，一般来说，您希望避免两件事情:

  • 为不必要的东西消耗 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 所说)。

小开

这个版本怎么样? 它不是正则表达式，但它很快解决了分割..。

#include <vector>
#include <string>
#include <algorithm>


size_t split2(const std::string& s, std::vector<std::string>& result)
{
size_t count = 0;
result.clear();
std::string::const_iterator p1 = s.cbegin();
std::string::const_iterator p2 = p1;
bool run = true;
do
{
p2 = std::find(p1, s.cend(), ' ');
result.push_back(std::string(p1, p2));
++count;


if (p2 != s.cend())
{
p1 = std::find_if(p2, s.cend(), [](char c) -> bool
{
return c != ' ';
});
}
else run = false;
} while (run);
return count;
}


int main()
{
std::vector<std::string> v;
std::string s = "a b c";
for (auto i = 0; i < 100000; ++i)
split2(s, v);
return 0;
}

$time splittest.exe

真正的0m0.132秒 用户0m0.000 s 系统0m0.109

小开

我认为 C + + 11 regex 比 perl 慢得多，可能比 python 慢得多。

为了正确地测量性能，最好是进行测试 使用一些不平凡的表达式，否则你就是在测量一切 而是正则表达式本身。

例如，比较 C + + 11和 perl

C + + 11测试代码

  #include <iostream>
#include <string>
#include <regex>
#include <chrono>


int main ()
{
int veces = 10000;
int count = 0;
std::regex expres ("([^-]*)-([^-]*)-(\\d\\d\\d:\\d\\d)---(.*)");


std::string text ("some-random-text-453:10--- etc etc blah");
std::smatch macha;


auto start = std::chrono::system_clock::now();


for (int ii = 0;  ii < veces; ii ++)
count += std::regex_search (text, macha, expres);


auto milli = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start).count();


std::cout << count << "/" << veces << " matches " << milli << " ms --> " << (milli / (float) veces) << " ms per regex_search" << std::endl;
return 0;
}

在我的计算机编译与 gcc4.9.3我得到的输出

 10000/10000 matches 1704 ms --> 0.1704 ms per regex_search

Perl 测试代码

  use Time::HiRes qw/ time sleep /;


my $veces = 1000000;
my $conta = 0;
my $phrase = "some-random-text-453:10--- etc etc blah";


my $start = time;


for (my $ii = 0; $ii < $veces; $ii++)
{
if ($phrase =~ m/([^-]*)-([^-]*)-(\d\d\d:\d\d)---(.*)/)
{
$conta = $conta + 1;
}
}
my $elapsed = (time - $start) * 1000.0;
print $conta . "/" . $veces . " matches " . $elapsed . " ms --> " . ($elapsed / $veces) . " ms per regex\n";

在我的计算机中再次使用 perl v5.8.8

  1000000/1000000 matches 2929.55303192139 ms --> 0.00292955303192139 ms per regex

所以在这个测试中 C + + 11/perl 的比率是

   0.1704 / 0.002929 = 58.17 times slower than perl

在真实的场景中，我得到的比率要慢100到200倍。 因此，举例来说，解析一个包含100万行代码的大文件需要 对于 perl 大约需要一秒钟，而对于 C + + 11则需要更多的分钟(!) 使用正则表达式的程序。


提交答案