测试回文的各种方法的性能 [Python] [英] Performance of Various Methods to Test for a Palindrome [Python]
问题描述
今天，我在玩几个编程难题.面对测试字符串以查看它是否为回文的任务，我想到了几种方法来完成此任务.这三种方法的基础描述如下(省略了大部分整理和测试代码).
Today, I was fooling around with a couple of programming puzzles. Faced with the task of testing a string to see whether or not it is a palindrome, I conceived of several ways to accomplish this. The basics of these three methods are depicted below (most neatifying and testing code is omitted).
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
方法 1 利用这样一个事实，即字符串中的字符可以像列表中的元素一样被索引.我们可以这样想象这种方法:你从一个单词的第一个和最后一个字母下面开始；每次迭代时，首先检查手指上方的字母是否相同；如果它们不同，则该词不是回文；如果它们相同，则将每个手指向单词中心移动 1 个字母并重复.
Method 1 takes advantage of the fact that characters in a string can be indexed like elements of a list. We can imagine this method thusly: you start with your fingers under the first and last letters of a word; with each iteration, you first check whether the letters above your fingers are the same; if they are different, the word is not a palindrome; if they are the same, you move each of your fingers 1 letter toward the center of the word and repeat.
此方法的大部分计算将是条件测试、索引切片和比较.还有一个计数器变量，它是索引切片计算的常量部分.
The bulk of computation with this method would be the condition testing, index slicing, and comparisons. There is also a counter variable which is a constant part of a calculation for the index slicing.
方法 2 还使用字符串中的字符索引.比较第一个和最后一个字符，然后丢弃，并重复这些步骤，直到保证(或否定)回文.
Method 2 also employs the indexing of characters in a string. The first and last characters are compared, then discarded, and these steps are repeated until a palindrome is guaranteed (or disproven).
成本与方法 1 类似，但有一些区别:添加了从 str -> 列表的转换，从列表中弹出元素，并减去了一个计数器变量.
Costs would be similar to Method 1, with some differences: the addition of conversion from str -> list, popping elements from a list, and minus a counter variable.
方法 3 反转给定的字符串，然后将其与原始字符串进行比较.有多种方法可以反转字符串(list.__reversed__() 等)，但我只展示了一种这样的可能性:将字符串转换为列表，然后将每个字符串连接起来该列表的元素到新字符串的开始.
Method 3 reverses the given string, and then compares it to the original. There are various ways to reverse a string (list.__reversed__(), etc.), but I've only shown one such possibility: converting the string to a list, and then concatenating each element of that list to the BEGINNING of a new string.
对于反转字符串的不同方法，可能涉及不同的操作，从而涉及不同的成本.对于我在这里选择的方法，我们需要将列表中的每个元素切片并将其与 str 变量连接起来.
With different methods for reversing a string, there may be different operations, and thus costs, involved. For my chosen method here, we have the cost of slicing each and every element from a list and concatenating it with a str variable.
这些方法中哪个执行速度最快，为什么?另外，有什么办法可以提高这些方法的效率吗?(顺便说一句，你如何测试 Python 中模块的执行速度?)
Which of these methods would be the fastest executing and why? Also, is there any way to improve the efficiency of these methods? (On a tangent, how do you test the execution speed of modules in Python?)
推荐答案
使用 timeit 模块用于速度测试，profile 模块用于性能统计数据，以及用于字节码反汇编的 dis 模块.
Use the timeit module for speed-testing, the profile module for performance statistics, and the dis module for bytecode disassembly.
下面的脚本演示了如何使用模块.
The script below demonstrates how the modules can be used.
从输出中需要注意的一件事是函数调用的数量对整体性能的影响有多大(当然，字节码指令的数量也是如此).
One thing to notice from the output is how much the number of function calls can affect the overall performance (and, of course, the same thing goes for the number of bytecode instructions).
希望，这(以及更多的实验)应该为您提供有关如何提高函数效率的足够线索.
Hopefully, that (and a little more experimentation) should give you enough clues on how to improve the efficiency of your functions.
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
这篇关于测试回文的各种方法的性能 [Python]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
