列表的性能问题

队列的弹出问题

利用Python的原生语法很难写出一个真正完全能达到 \(O(1)\) 的队列，究其原因是由于 insert 方法的时间复杂度问题：

class queue:
	def __init__(self,q):
		self.q=[]
	def popright(self):
		self.q.pop()
	def appendleft(self,elem):
		self.q.insert(0,elem)

由于Python的底层使用的是数组的数据结构，这就导致在插入数据的时候，必须要让这些数据向右移动一位，这就使得时间复杂度变成了 \(O(1)\) .

如果我们想要实现时间复杂度为 \(O(1)\) 的队列怎么办？可以使用Python官方库的 collections 库。

from collections import deque

利用 pop() 和 popleft() 、append() 和 appendleft() 就能让时间复杂度实现为 \(O(1)\) 了。

查找性能问题

Python默认的查找是利用 in 关键字，如下：

if i in range(1,10):

这个操作的时间复杂度是多少？很遗憾，Python在列表上是使用线性查找的方式进行查找的，时间复杂度自然就是 \(O(n)\) ，这在列表很大的时候就会出现很麻烦的场面。

为了查找的方便，可以将列表转化为集合再去查找，这样的效果会更好，因为Python的集合底层使用的是哈希表的结构，在查找的时候时间复杂度就变成了 \(O(1)\) .

L = [1,2,3,4,5]
L_Set = set(L)
if i in L_Set

需要注意的是转换成集合的操作实际上也是 \(O(n)\) 的，也就是说仅仅在你需要多次查找的时候才有必要将其转化为集合。

字典的优化

合并操作

利用解包操作可以快速合并两个字典：

l1 = {'foo':1}
l2 = {'boo':2}
dict_inserted = {**l1,**l2}

最终我们得到了两个合并后的字典。
需要注意的是 Python 3.9 及之后的版本有个更好的方案：运算符 | ，使用如下：

{'name':'fool','score':100} | {'name':'student'}    
# 结果为 {'name':'student','score':100}
{'name':'student'} | {'name':'fool','score':100} 
# 结果为 {'name':'fool','score':100}

需要注意的是这个运算符遵循“后来居上”的原则，所以如果有相同的key将会保留后来的值。

有序字典

有序字典是 collections 库中的一个字典加强型容器，它可以保留键的有序性，从而不至于在数据转换的时候打乱顺序。

一个应用就是去重：

from collections import OrderedDict
nums = [10,3,3,4,6,2,7,7,1,4,0]
list(OrderedDict.fromkeys(nums).keys())
# 运行结果为 [10, 3, 4, 6, 2, 7, 1, 0]

传统方法是将列表变为一个集合，但是这样的副作用就是打乱了顺序从而出现顺序问题。

元组的优化

命名元组

Python中的默认元组依靠索引进行调用，但是在元素过多的情况下，索引调用就会变得相当麻烦。这个时候可以利用 collections 库优化：

from collections import namedtuple
namedtuple("Point",["x","y"])
p1 = Point(x=1,y=0)

在实际调用的时候，我们可以像调用方法一样调用属性值：

p1.x

从某种程度上比较像字典，但是它与字典的不同之处在于：

• 命名元组仍然可以用数字索引取元素，而字典只能用key取元素。
• 命名元组不可变，它与字典的关系可以理解成元组与列表之间的关系。