不同方法检测回文的性能 [Python]
今天，我在玩一些编程谜题。遇到一个任务，就是要检查一个字符串是否是回文（即正着读和反着读都一样的字符串），我想到了几种方法来实现这个目标。下面简单介绍这三种方法的基本思路（大部分的代码细节我就省略了）。
def check_palin(victim, method):
if method is 1: # check progressively inner chars
x = 0
while x < (len(victim)/2): # len/2 is num of iter needed for guarantee
if victim[x+0] is victim[-(1+x)]: # on pass n, compare nth letter
# and nth to last letter
x += 1 # then increment the n counter
else:
return False
return True
elif method is 2: # check first and last chars repeatedly
tmp = []
for i in victim:
tmp.append(i) # convert string into list
while len(tmp) > 1: # if 1 or 0 char left, palin is guaranteed
if tmp[0] is tmp[-1]: # if the first and last characters are the same letter
tmp.pop(0) # remove them both
tmp.pop(-1)
else:
return False
return True
elif method is 3: # reverse string and compare to original
tmp = ""
for i in victim: # for every letter
tmp = i + tmp # cat it to the beginning, not append
return tmp == victim
else:
return -1
方法一利用了字符串中字符可以像列表元素一样被索引的特点。可以这样想象这个方法：你用手指分别夹住一个单词的第一个和最后一个字母；每次检查你手指上的字母是否相同；如果不同，这个单词就不是回文；如果相同，你就把手指分别向中间移动一位，然后继续检查。
这个方法的主要计算工作在于条件判断、索引切片和比较操作。还有一个计数器变量，它是进行索引切片计算时的一个常量部分。
方法二同样使用了字符串中字符的索引。首先比较第一个和最后一个字符，然后把它们丢掉，重复这个步骤，直到确认是回文（或者不是）。
这个方法的成本和方法一差不多，但有一些不同：需要将字符串转换为列表，删除列表中的元素，而且不需要计数器变量。
方法三是将给定的字符串反转，然后和原字符串进行比较。反转字符串的方法有很多（比如使用list.__reversed__()等），但我这里只展示了一种可能性：把字符串转换成列表，然后把列表中的每个元素都加到一个新字符串的开头。
由于反转字符串的方法不同，可能涉及到不同的操作和成本。在我选择的方法中，成本主要来自于从列表中切片每个元素，并将其与一个字符串变量连接。
我的问题：
这几种方法中，哪一种执行速度最快，为什么？另外，有没有办法提高这些方法的效率？（顺便问一下，如何测试Python模块的执行速度？）
4 个回答
1
可以使用timeit这个模块。比如说：
import timeit
for method in 1, 2, 3:
print method, timeit.timeit('check_palin("victimmitciv", %i)' % method,
'from __main__ import check_palin', number=1000000)
3
你无法比O(n)更快地检查一个字符串是否是回文（这里的n是指输入字符串的长度）。无论你使用什么额外的方法（比如栈、反转字符串等等），都不会让速度变得更快，只会消耗更多的内存。
2
可以使用 timeit 模块来测试代码的运行速度，使用 profile 模块来获取性能统计数据，使用 dis 模块来查看字节码的详细信息。
下面的脚本展示了这些模块是如何使用的。
从输出结果中可以看到，函数调用的次数对整体性能有很大的影响（当然，字节码指令的数量也一样）。
希望这些信息（以及多做一些实验）能给你一些提示，帮助你提高函数的效率。
from timeit import timeit
from cProfile import runctx
from dis import dis
def analyse(*args):
victim = 'detartrated'
number = 1000
for func in args:
print('\n%s\n' % ('#' * 50))
name = func.__name__
print('test: %s(%r): %r' % (name, victim, func(victim)))
code = '%s(%r)' % (name, victim)
duration = timeit(
code, 'from __main__ import %s' % name, number=number)
usec = 1000000 * duration / number
print('time: %s: %.2f usec/pass\n' % (code, usec))
runctx(code, globals(), locals())
dis(func)
def check_palin1(victim):
""" check progressively inner chars """
x = 0
# len/2 is num of iter needed for guarantee
while x < (len(victim)/2):
# on pass n, compare nth letter and nth to last letter
if victim[x+0] is victim[-(1+x)]:
# then increment the n counter
x += 1
else:
return False
return True
def check_palin2(victim):
""" check first and last chars repeatedly """
tmp = []
for i in victim:
# convert string into list
tmp.append(i)
# if 1 or 0 char left, palin is guaranteed
while len(tmp) > 1:
# if the first and last characters are the same letter
if tmp[0] is tmp[-1]:
# remove them both
tmp.pop(0)
tmp.pop(-1)
else:
return False
return True
def check_palin3(victim):
""" reverse string and compare to original using a loop """
tmp = ""
# for every letter
for i in victim:
# cat it to the beginning, not append
tmp = i + tmp
return tmp == victim
def check_palin4(victim):
""" reverse string and compare to original using slice syntax """
return victim == victim[::-1]
analyse(check_palin1, check_palin2, check_palin3, check_palin4)
输出结果：
##################################################
test: check_palin1('detartrated'): True
time: check_palin1('detartrated'): 3.80 usec/pass
9 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 test.py:20(check_palin1)
6 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
22 0 LOAD_CONST 1 (0)
3 STORE_FAST 1 (x)
24 6 SETUP_LOOP 72 (to 81)
>> 9 LOAD_FAST 1 (x)
12 LOAD_GLOBAL 0 (len)
15 LOAD_FAST 0 (victim)
18 CALL_FUNCTION 1
21 LOAD_CONST 2 (2)
24 BINARY_DIVIDE
25 COMPARE_OP 0 (<)
28 POP_JUMP_IF_FALSE 80
26 31 LOAD_FAST 0 (victim)
34 LOAD_FAST 1 (x)
37 LOAD_CONST 1 (0)
40 BINARY_ADD
41 BINARY_SUBSCR
42 LOAD_FAST 0 (victim)
45 LOAD_CONST 3 (1)
48 LOAD_FAST 1 (x)
51 BINARY_ADD
52 UNARY_NEGATIVE
53 BINARY_SUBSCR
54 COMPARE_OP 8 (is)
57 POP_JUMP_IF_FALSE 73
28 60 LOAD_FAST 1 (x)
63 LOAD_CONST 3 (1)
66 INPLACE_ADD
67 STORE_FAST 1 (x)
70 JUMP_ABSOLUTE 9
30 >> 73 LOAD_GLOBAL 1 (False)
76 RETURN_VALUE
77 JUMP_ABSOLUTE 9
>> 80 POP_BLOCK
31 >> 81 LOAD_GLOBAL 2 (True)
84 RETURN_VALUE
##################################################
test: check_palin2('detartrated'): True
time: check_palin2('detartrated'): 10.57 usec/pass
30 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 test.py:33(check_palin2)
6 0.000 0.000 0.000 0.000 {len}
11 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
10 0.000 0.000 0.000 0.000 {method 'pop' of 'list' objects}
35 0 BUILD_LIST 0
3 STORE_FAST 1 (tmp)
36 6 SETUP_LOOP 27 (to 36)
9 LOAD_FAST 0 (victim)
12 GET_ITER
>> 13 FOR_ITER 19 (to 35)
16 STORE_FAST 2 (i)
38 19 LOAD_FAST 1 (tmp)
22 LOAD_ATTR 0 (append)
25 LOAD_FAST 2 (i)
28 CALL_FUNCTION 1
31 POP_TOP
32 JUMP_ABSOLUTE 13
>> 35 POP_BLOCK
40 >> 36 SETUP_LOOP 75 (to 114)
>> 39 LOAD_GLOBAL 1 (len)
42 LOAD_FAST 1 (tmp)
45 CALL_FUNCTION 1
48 LOAD_CONST 1 (1)
51 COMPARE_OP 4 (>)
54 POP_JUMP_IF_FALSE 113
42 57 LOAD_FAST 1 (tmp)
60 LOAD_CONST 2 (0)
63 BINARY_SUBSCR
64 LOAD_FAST 1 (tmp)
67 LOAD_CONST 3 (-1)
70 BINARY_SUBSCR
71 COMPARE_OP 8 (is)
74 POP_JUMP_IF_FALSE 106
44 77 LOAD_FAST 1 (tmp)
80 LOAD_ATTR 2 (pop)
83 LOAD_CONST 2 (0)
86 CALL_FUNCTION 1
89 POP_TOP
45 90 LOAD_FAST 1 (tmp)
93 LOAD_ATTR 2 (pop)
96 LOAD_CONST 3 (-1)
99 CALL_FUNCTION 1
102 POP_TOP
103 JUMP_ABSOLUTE 39
47 >> 106 LOAD_GLOBAL 3 (False)
109 RETURN_VALUE
110 JUMP_ABSOLUTE 39
>> 113 POP_BLOCK
48 >> 114 LOAD_GLOBAL 4 (True)
117 RETURN_VALUE
##################################################
test: check_palin3('detartrated'): True
time: check_palin3('detartrated'): 2.77 usec/pass
3 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 test.py:50(check_palin3)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
52 0 LOAD_CONST 1 ('')
3 STORE_FAST 1 (tmp)
54 6 SETUP_LOOP 24 (to 33)
9 LOAD_FAST 0 (victim)
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 2 (i)
56 19 LOAD_FAST 2 (i)
22 LOAD_FAST 1 (tmp)
25 BINARY_ADD
26 STORE_FAST 1 (tmp)
29 JUMP_ABSOLUTE 13
>> 32 POP_BLOCK
57 >> 33 LOAD_FAST 1 (tmp)
36 LOAD_FAST 0 (victim)
39 COMPARE_OP 2 (==)
42 RETURN_VALUE
##################################################
test: check_palin4('detartrated'): True
time: check_palin4('detartrated'): 0.65 usec/pass
3 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 test.py:59(check_palin4)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
61 0 LOAD_FAST 0 (victim)
3 LOAD_FAST 0 (victim)
6 LOAD_CONST 1 (None)
9 LOAD_CONST 1 (None)
12 LOAD_CONST 2 (-1)
15 BUILD_SLICE 3
18 BINARY_SUBSCR
19 COMPARE_OP 2 (==)
22 RETURN_VALUE