浅谈正则表达式——C++正则替换引起的性能下降

问题引入

最近在一次解析大文件(10万+行)时，处理空格用到了正则替换，却没想到带来了性能上的问题，特别在此记录给需要的人避坑。假如要用C++处理一个字符串首尾的空格，可以用正则，可以用string自带的erase方法，下面是对这两种方法性能上的测试：

正则替换测试

#include 
#include 
#include 

using namespace std;

void trimmed(std::string& str) {
    str = regex_replace(str, std::regex("^\\s+"), "");
    str = regex_replace(str, std::regex("\\s+$"), "");
}

int main() {
	string str1 = "   123 45 tr54 ewre  "; //字符串首尾共5个空格
	cout << "str1.length = " << str1.length() << endl;
	auto t1 = std::chrono::steady_clock::now();
	trimmed(str1);
	auto t2 = std::chrono::steady_clock::now();
	double elapse = std::chrono::duration<double, std::milli>(t2-t1).count();
	cout << "regex replace use " << elapse << "ms" << endl;
	cout << "str1.length = " << str1.length() << endl;
	cout << str1 << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试结果如下：

使用正则替换，执行完成一次大概耗时0.4ms，看起来耗时很短，但如果乘以100000呢？
0.4ms * 100000 = 40000ms = 40s

常规方法测试

接下来使用string自带的erase方法测试

#include 
#include 
#include 

using namespace std;

void Trimmed(std::string& str) {
    str = str.erase(0, str.find_first_not_of(" "));
    str = str.erase(str.find_last_not_of(" ") + 1);
}

int main() {
	string str2 = "   123 45 tr54 ewre  "; //字符串首尾同样是5个空格
    cout << "str2.length = " << str2.length() << endl;
    auto t3 = std::chrono::steady_clock::now();
    Trimmed(str2);
    auto t4 = std::chrono::steady_clock::now();
    double elapse = std::chrono::duration<double, std::milli>(t4-t3).count();
    cout << "erase use " << elapse << "ms" << endl;
    cout << "str2.length = " << str2.length() << endl;
    cout << str2 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试结果如下

使用erase去除空格，执行一次大概耗时0.0008ms，而正则替换耗时几乎是它的500倍（0.4ms），这个差距就很大了。即使乘以100000，erase耗时0.0008ms * 100000 = 80ms，erase给人的感觉是极致丝滑，正则替换则是程序半天无响应。而这个差距在多次外部调用的情况下更加明显，看下面的模拟测试：

模拟外部多次调用

void test01() {
    auto t1 = std::chrono::steady_clock::now();
    for (int i = 0; i < 100000; i++) {
        string str = "   123 45 tr54 ewre  ";
        trimmed(str);
    }
    auto t2 = std::chrono::steady_clock::now();
    double elapse = std::chrono::duration<double, std::milli>(t2-t1).count();
    cout << "regex----->" << elapse << "ms" << endl;
}

void test02() {
    auto t1 = std::chrono::steady_clock::now();
    for (int i = 0; i < 100000; i++) {
        string str = "   123 45 tr54 ewre  ";
        Trimmed(str);
    }
    auto t2 = std::chrono::steady_clock::now();
    double elapse = std::chrono::duration<double, std::milli>(t2-t1).count();
    cout << "erase=====>" << elapse << "ms" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

test01和test02分别模拟使用正则替换和erase处理10万行的文本中的首尾空格，结果如下：

现在这个差距已经不是500倍了，而是夸张的2300多倍！！！这在性能上是完全不可接受的，故而正则替换性能较差，不建议使用正则去空格。

正则性能差的原因

主要是正则表达式的引擎会导致字符匹配时会发生回溯，此处不做过多叙述，感兴趣的小伙伴可以去阅读正则表达式引起的性能下降一文，一定会有所收获的。

写在最后

不用不知道，正则虽然处理文本很强，但用错了地方，可能带来负面效果，coding就是从这个坑出来，掉进另一个坑里，这其中的乐趣，大概就是爬上坑的过程吧哈哈。