编写Python程序的时候，有时会遇到“业务逻辑很好理解，但写成代码感觉又丑又慢”的情况，于是计划用此篇总结这类问题。
以下网址列举了Python中常用操作的时间复杂度，可用于参考。
https://wiki.python.org/moin/TimeComplexity
实现矩阵存储结构
在多数编程语言中，我们可以使用二维数组表达一个二维矩阵，在Python中需要首先声明并创建一个“list的list”，并使用预定义的一个值填充：
>>> m, n = 10, 20
>>> none_matrix = [[None for i in range(m)] for j in range(n)]
>>> zero_matrix = [[0 for i in range(m)] for j in range(n)]
之后可以用和其他C系语言类似的方法访问、设置(m, n)位置的元素：
>>> none_matrix[3][2]
# None
>>> none_matrix[3][2] = 10
>>> none_matrix[3][2]
10
另一种思路是使用dict描述矩阵。在Python中dict的key可以为任意不可变类型对象，因此可以使用元组（tuple）作为dict的key，一个元组可以描述任意一个n元坐标。这种方法适合存储稀疏矩阵，即矩阵中绝大部分的值都是默认值的矩阵，对比使用list的传统方法，使用dict存储稀疏矩阵更省内存。同时非常灵活，可以使用元组以外的key保存额外信息。
使用dict的常用的d[(x, y)]来设置值，get方法和default参数获取矩阵某个值。如果使用d[(x, y)]获取值，在值为默认时因为不存在具体值导致KeyError。顺带，对某个dict，例如d，做d[1, 2]，实际上是做d[(1, 2)]，键为元组(1, 2)。
>>> matrix = {}
>>> matrix.get((3, 5))
# None
>>> matrix.get((3, 5), 0)
0
>>> matrix[3, 5] = 10
>>> matrix.get((3, 5))
10
可以考虑使用collections.defaultdict类代替dict。defaultdict类继承dict，唯一区别在于可以为整个字典设置一个键对应值不存在时的默认返回值。
>>> from collections import defaultdict
>>> none_matrix = defaultdict(lambda: None)
>>> none_matrix[3, 5]
# None
>>> zero_matrix = defaultdict(float)
>>> zero_matrix[3, 5]
0
可以自定义一个矩阵类，内部使用dict实现，对接口进行包装，提高代码可读性。
第三种看起来更为“专业”的方法是使用numpy的numpy.matrix类。
可以参考https://docs.scipy.org/doc/numpy/reference/generated/numpy.matrix.html
测试两个list是否包含共同元素
问题：对于两个list，判断是否包含相等的元素。
例如假设有
a = [1, 2, 3]
b = [2, 3, 4]
c = [4, 5, 6]
那么a和b有共同元素2和3，a和c没有共同元素。
来自 https://stackoverflow.com/questions/3170055/test-if-lists-share-any-items-in-python 的回答提到了一些方法。
- 第一种方法 Set Intersection：
bool(set(a) & set(b))
Python中的set使用Hash表，搜索的时间复杂度为O(1)，考虑到Hash冲突，性能可能略低于理想，但通常仍在O(1)数量级。对于两个set进行交操作的总体时间复杂度是O(m+n)。
此种方法要考虑set(some_list)操作，即从list创建set所消耗的时间。暂且没有查阅相关机制，猜测时间上是O(n)，对两个list分别创建set时间复杂度是O(m+n)，同时占用额外空间，复杂度O(m+n)。
- 第二种方法 Generator Expression：
any(i in a for i in b)
本质上是朴素嵌套循环的优雅写法。python中对于list的in操作复杂度是O(n)，整个方法的平均时间复杂度是O(m*n)。对于any，有满足条件就终止的特性，所以可能不需要完整遍历就完成计算。
- 第三种方法 Hybrid：
a = set(a)
any(i in a for i in b)
本质上是之前两种算法的混合。
- 第四种方法 isdisjoint:
not set(a).isdisjoint(b)
关于set类型isdisjoint方法，disjoint意为不相交的，若set_a和set_b没有共同元素，则set_a.isdisjoint(set_b)返回True。
-
性能&总结
原回答对四种方法，分别考虑“重合元素在开始”、“重合元素在末尾”、“随机元素高重合率”、“随机元素低重合率”做了测试，并能够得出部分结论如下：
- 绝大多数情况下 方法4 isdisjoint 最快，一般场景可以直接使用此方法
- 如果list中元素较多，已知大多数情况下两个list中有相同元素，且有很高的元素重合率，list有序，那么 方法2 Generator Expression 有很高几率更快，因为“遇到相同即终止”，不需要完整遍历。
- 遇到“两个list没有重复元素”的情况，方法2 Generator Expression 很慢。
