效率问题

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:
Leave a comment | Trackback

3 Responses to “效率问题”

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

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

    [Reply]

    Reply
  2. cnhacktnt
    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]

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

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

    [Reply]

    Reply

Leave a Comment