我将循环数增加到1000000,以获得更好的计时措施。
这是我的Python时间:
real 0m2.038suser 0m2.009ssys 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.786suser 0m5.779ssys 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.034suser 0m3.029ssys 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.509suser 0m2.503ssys 0m0.004s
最终的改进是有一个
std::vector的
const char *作为回报,其中每个字符指针会指向原来的内子
sC字符串
本身。问题是,您不能这样做,因为它们中的每一个都不会被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
这是
boost::regex用于定时 C字符串 参数样品:
real 0m1.284suser 0m1.278ssys 0m0.005s
此示例中相同的代码
boost::regex和
std::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的情况,返回vector
string_ref而不是
string副本也将更便宜
split。
编辑2
这个新的解决方案能够通过返回获得输出。我使用了在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.385suser 0m0.385ssys 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.002suser 0m0.997ssys 0m0.004s
可以看出,与优化的
string_view输出参数版本相比没有太大差异。
请注意,还有一个建议
std::split可以像这样工作。



