效率问题

October 22nd, 2009 Categories: 杂项

上周发了篇《两条与密码验证相关的正则表达式问题》。今天看了些python的正则表达式,心血来潮,想看看这几种正则哪种效率较高。代码、运行结果见下。这是为什么呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/python
import re
import time
import fpformat
Regex1 = re.compile("^(?=[0-9a-zA-Z@%&]*\d)(?=[0-9a-zA-Z@%&]*[a-zA-Z])(?=[0-9a-zA-Z@%&]*[@%&])[0-9a-zA-Z@%&]{8,}$", re.MULTILINE)
Regex2 = re.compile("^(?=.*\d)(?=.*[a-zA-Z])(?=.*[@%&])[0-9a-zA-Z@%&]{8,}$", re.MULTILINE)
Regex3 = re.compile("^(?![0-9a-z]{8,16}$|[@%&]{8,16}$)[a-z0-9@%&]{8,16}$", re.IGNORECASE |re.MULTILINE)



TimesToDo = 1250;
TestString = ""
for i in range(800):
    TestString += "aba134babdedfg@&%\n"

StartTime = time.time()
for i in range(TimesToDo):
   Regex1.search(TestString)
Seconds = time.time() - StartTime
print "R1 takes " + fpformat.fix(Seconds,3) + " seconds"

StartTime = time.time()
for i in range(TimesToDo):
   Regex2.search(TestString)
Seconds = time.time() - StartTime
print "R2 takes " + fpformat.fix(Seconds,3) + " seconds"

StartTime = time.time()
for i in range(TimesToDo):
   Regex3.search(TestString)
Seconds = time.time() - StartTime
print "R3 takes " + fpformat.fix(Seconds,3) + " seconds"

运行结果:
我爱正则表达式|效率问题

Tags:

3 Responses to “效率问题”

  1. October 22nd, 2009 at 20:17
    1

    R3的flag中含有re.IGNORECASE。将其去掉,在正则[]中加入A-Z,时间可以缩短到2秒多。

    [Reply]

  2. October 23rd, 2009 at 17:15
    2

    一条测试数据不足以说明它们的性能差异,你可以简单地做如下修改:
    —-
    1. 测试字符串改成 “—-aba134babdedfg@&%\n”,

    2. Regex3 = re.compile(“^(?![0-9a-zA-Z]{8,16}$|[@%&]{8,16}$)[a-zA-Z0-9@%&]{8,16}$”, re.MULTILINE)

    立马你就可以看到差异:
    —–
    R1 takes 0.734 seconds
    R2 takes 2.041 seconds
    R3 takes 0.797 seconds

    这说明,一个或单单几个字符串来测试正则的性能,不靠谱,你可不知道用户输入的成千上万不同的字符组合是什么。

    那么引申出正则的优化法则:
    —-
    1. 尽可能将需要匹配的字符串显式地列出来,[a-zA-Z] 显然比 /[a-z]/i 要效率高,而 [abcde...审略...z] 更好一些

    2. 包含更可能少的可能性,范围越窄越好。比如括号,嵌套括号,括号中的或条件;比如大括号中指定的范围以及贪婪匹配*,+符号;这些尽量少用或不用。

    3. 单行匹配就可以的绝不多行匹配

    4. 尽可能地让正则表达式提早结束,也就是说在碰到不匹配的字符串式尽早让正则表达式失败退出。

    关于第4点,可以做个实验:
    —-
    在前面做的修改的基础上,改一下 R3:
    Regex3 = re.compile(“^(?=[a-zA-Z0-9@%&])(?![0-9a-zA-Z]{8,16}$|[@%&]{8,16}$)[a-zA-Z0-9@%&]{8,16}$”, re.MULTILINE)

    看结果:
    —-
    R1 takes 0.851 seconds
    R2 takes 2.045 seconds
    R3 takes 0.707 seconds

    瞧,R3 最快,但正如以上所说,这条测试最快,不代表它在所有环境中都最快,所以根据实际环境来进行优化才算是王道。
    另外,尽可能在前台,使用一些限定,比如javascript做用户输入检测,来限定用户输入的字符串范围,也可以为后台的正则优化提供依据。
    不过还是要重申一下,正则不是万能,复杂要求的输入验证不一定要完全用正则来解决,当然你不在乎性能,不差钱除外 :-P

    [Reply]

  3. October 23rd, 2009 at 18:55
    3

    忘了补充一点,在不需要捕获匹配字符串的情况下,不要用 (),而是用(?:) 这种非捕获括号来代替,这个也是很重要的优化手段

    [Reply]

Leave a Comment