嗨,我想知道为什么下面的代码使用regex进行字符串拆分
#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,它是下面编辑2的基础。
我将循环增加到1000000以获得更好的计时度量。
这是我的Python计时:
这里有一个相当于你的代码,只是有点漂亮:
时间安排:
这是一种避免构造/分配向量和字符串对象的优化:
时间安排:
这几乎是100%的性能改进。
向量是在循环之前创建的,并且可以在第一次迭代中增加其内存。之后,通过
clear()
没有内存释放,向量维护内存并在适当的位置构造字符串。另一个性能提升将是完全避免构造/破坏
std::string
,从而避免分配/释放其对象。这是一个试探性的方向:
时间安排:
最终的改进是将
std::vector
的const char *
作为返回,其中每个char指针将指向原始s
c字符串本身内部的子字符串。问题是,不能这样做,因为它们中的每一个都不会被null终止(为此,请参见后面的示例中使用C++ 1y^ { CD6}})。最后的改进也可以通过以下方式实现:
我用3.3的叮当声(从树干)和-O3制作了样本。也许其他regex库能够更好地执行,但无论如何,分配/释放常常会影响性能。
增强型正则表达式
这是c字符串参数示例的
boost::regex
计时:相同的代码,
<>希望随着时间的推移,它越来越好,C++ STDLIB正则表达式的实现还处于起步阶段。boost::regex
和std::regex
接口在这个示例中是相同的,只需要更改名称空间和include。编辑
为了完成,我尝试了这个(上面提到的“最终改进”建议),但它并没有在任何方面提高等效
std::vector<std::string> &v
版本的性能:这与array_ref and string_ref proposal有关。下面是使用它的示例代码:
对于带向量返回的
split
情况,返回string_ref
的向量而不是string
副本也会更便宜。编辑2
这个新的解决方案能够通过返回获得输出。我使用了Marshall Clow在https://github.com/mclow/string_view找到的
string_view
(string_ref
已重命名)libc++实现。时间安排:
请注意,与之前的结果相比,这一速度有多快。当然,它不会在循环中填充一个
vector
(也可能不会提前匹配任何内容),但是无论如何,您都会得到一个范围,您可以使用基于范围的for
来覆盖它,甚至可以使用它来填充一个vector
。由于覆盖
iterator_range
会在原始string
(或以空结尾的字符串)上创建string_view
s,因此它非常轻量级,从不生成不必要的字符串分配。为了比较使用这个
split
实现但实际上填充了vector
我们可以这样做:这使用boost range copy算法在每次迭代中填充向量,计时如下:
可以看出,与优化的
string_view
输出参数版本相比没有太大的差异。注意还有a proposal for a ^{} 可以这样工作。
这个版本怎么样?它不是regex,但它很快就解决了拆分问题。。。
$time splittest.exe
实0m0.132s 用户0m0.000s 系统0m0.109s
对于优化,通常需要避免两件事:
两者可以是对立的,因为有时它会比把所有东西都缓存在内存中更快地计算一些东西。。。所以这是一个平衡的游戏。
让我们分析一下您的代码:
我们能做得更好吗?好吧,如果我们可以重用现有的存储,而不是继续分配和释放内存,我们应该会看到一个显著的改进[1]:
在您执行的测试中,子匹配的数量在迭代中是恒定的,这个版本不太可能被打败:它只在第一次运行时分配内存(对于
rsplit
和result
),然后继续重用现有内存。[1]:免责声明,我只证明了这个代码是正确的,我没有测试过它(正如Donald Knuth所说)。
相关问题 更多 >
编程相关推荐