若干Python性能优化小tips

若干简单易实现的Python性能优化小tips。

部分参考：https://segmentfault.com/a/1190000000666603

一些tips在刷题过程确实得到验证，尚有一些未验证但在实际简单测试中效率有提升。

优化算法时间复杂度

不论什么语言，算法的时间复杂度对程序的执行效率都有决定性影响，在Python中可以通过选择合适的数据结构来优化时间复杂度，如list和set查找指定元素的时间复杂度分别为O(n)和O(1)。同时，可以根据具体情况，采用分治、贪心、动态规划等算法思想。（不过优化算法有些有时候也不是很容易实现，，，）

在算法的常见时间复杂度上排序如下：

$O(1)<O(\log n)<O(n\log n)<O(n^2)<O(n^3)<O(n^k)<O(k^n)<O(n!)$

使用dict或set查找元素

Python中的dict和set是使用hash表实现的，因此查找元素的最优时间复杂度为O(1)，而list是线性表结构，其查询时间复杂度为O(n)。

因此，在需要频繁查找或访问的时候，依据实际情况使用dict或set，要比使用list更快。

# run on jupyter-notebook
a = range(1000)
s = set(a)
d = dict((i,1) for i in a)
%timeit -n 10000 100 in d
%timeit -n 10000 100 in s

# result:
# 10000 loops, best of 3: 56.5 ns per loop
# 10000 loops, best of 3: 38.8 ns per loop

使用set进行交并差运算

set的union、intersection、difference操作要比使用list迭代快，因此涉及list求交集、并集、差集的问题，可以通过转换为set来操作。

set的交并差操作语法：

交集：set(list1)&set(list2)
并集：set(list1)|set(list2)
差集：set(list1)-set(list2)

使用list迭代方法求两个list交集：

%%timeit -n 1000
lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44] 
listb=[2,4,6,9,23] 
intersection=[] 
for a in lista: 
    for b in listb: 
        if a == b:
            intersection.append(a)

# result:
# 1000 loops, best of 3: 3.58 µs per loop

将list转为set后求交集：

%%timeit -n 1000
lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44] 
listb=[2,4,6,9,23] 
intersection=[] 
list(set(lista)&set(listb))

# result:
# 1000 loops, best of 3: 1.58 µs per loop

优化循环

对循环的优化遵循的原则是尽量减少循环过程中计算量，循环外可以做的事情不要放到循环内做，多重循环尽量将内层的计算提到上一层。

# run on jupyter-notebook
a = range(10000)
size_a = len(a)
%timeit -n 1000 for i in a: k = len(a)
%timeit -n 1000 for i in a: k = size_a

# result:
# 1000 loops, best of 3: 361 µs per loop
# 1000 loops, best of 3: 161 µs per loop

优化多个判断表达式的顺序

对于and，把满足条件少的表达式放在前面判断；对于or，把满足条件多的表达式放在后面判断。

Python中的条件表达式是lazy evaluation的，也就是说对于表达式if a and b，在a 为 false的情况下，b表达式的值将不再计算。

# run on jupyter-notebook
a = range(2000)  
%timeit -n 100 [i for i in a if i < 20 or 1000 < i < 2000]
%timeit -n 100 [i for i in a if 1000 < i < 2000 or i < 20]     
%timeit -n 100 [i for i in a if i % 2 == 0 and i > 1900]
%timeit -n 100 [i for i in a if i > 1900 and i % 2 == 0]

# result:
100 loops, best of 3: 98.1 µs per loop
100 loops, best of 3: 78.9 µs per loop
100 loops, best of 3: 88.1 µs per loop
100 loops, best of 3: 37.4 µs per loop

字符串的优化

Python中的字符串对象是不可改变的，因此对字符串的操作如拼接、修改等都会产生一个新的字符串对象，而不是基于原字符串，这种持续的copy过程会在一定程度上影响Python的性能，特别是处理文本较多的情况下。

字符串连接尽量使用join，而不是+

%%timeit -n 100
a = ['a','b','b','d','e','f','g','h','i','j','k','l','m','n']  
s = ""
for i in a:
    s += i

# result:
# 100 loops, best of 3: 880 ns per loop

%%timeit -n 100
a = ['a','b','b','d','e','f','g','h','i','j','k','l','m','n']
s = "".join(a)

# result:
# 100 loops, best of 3: 570 ns per loop

尽量使用内置函数判断，而不是正则表达式

在对字符串可以使用正则表达式或者内置函数进行判断时，尽量使用内置函数，如str.isalpha(), str.isdigit(), str.startswith(("x","y")), str.endswith(("x","y"))。

不使用中间变量交换两个变量的值

使用a,b=b,a的形式来交换a,b两个变量的值。

（实际简单测试过程中，时间差距并不总是很大，还没深究速度差异的内在原因。）

借助中间变量：

%%timeit -n 10000
a,b = 1,2
c=a
a=b
b=c

# result:
# 10000 loops, best of 3: 68.5 ns per loop

不借助中间变量：

%%timeit -n 10000
a,b = 1,2
a,b = b,a

# result:
# 10000 loops, best of 3: 38.3 ns per loop

使用`if is`，而不是`==`

使用if a is True要比使用if a == True快，同理if a is not Noe要比if a != None快。

a = range(10000)
%timeit -n 100 [i for i in a if i == True]
%timeit -n 100 [i for i in a if i is True]

# result:
# 100 loops, best of 3: 370 µs per loop
# 100 loops, best of 3: 248 µs per loop

使用级联比较`x<y<z`

x, y, z = 1,2,3
%timeit -n 1000000 if x < y < z:pass
%timeit -n 1000000 if x < y and y < z:pass

# result:
# 1000000 loops, best of 3: 47.8 ns per loop
# 1000000 loops, best of 3: 50.2 ns per loop

使用`while 1`，而不是`while True`

在Python2.x中，True是全局变量，而不是关键字？

def while_1():
    n = 100000
    while 1:
        n -= 1
        if n <= 0: break
def while_true():
    n = 100000
    while True:
        n -= 1
        if n <= 0: break    

m, n = 1000000, 1000000 
%timeit -n 100 while_1()
%timeit -n 100 while_true()

# result:
# 100 loops, best of 3: 2.2 ms per loop
# 100 loops, best of 3: 3.4 ms per loop

使用`**`，而不是`pow`

%timeit -n 10000 c = pow(2,20)
%timeit -n 10000 c = 2**20

# result:
# 10000 loops, best of 3: 207 ns per loop
# 10000 loops, best of 3: 16.4 ns per loop

优化算法时间复杂度