算法的时间复杂度对程序的执行效率影响最大,在Python中可以通过选择合适的数据结构来优化时间复杂度,如list和set查找某一个元素的时间复杂度分别是O(n)和O(1)。不同的场景有不同的优化方式,总得来说,一般有分治,分支界限,贪心,动态规划等思想。
如用上三角或下三角的方式去保存一个大的对称矩阵。在0元素占大多数的矩阵里使用稀疏矩阵表示。
对于dict和list等数据结构的对象,直接赋值使用的是引用的方式。而有些情况下需要复制整个对象,这时可以使用copy包里的copy和deepcopy,这两个函数的不同之处在于后者是递归复制的。效率也不一样:(以下程序在ipython中运行)
timeit后面的-n表示运行的次数,后两行对应的是两个timeit的输出,下同。由此可见后者慢一个数量级。
python dict和set都是使用hash表来实现(类似c++11标准库中unordered_map),查找元素的时间复杂度是O(1)
dict的效率略高(占用的空间也多一些)。
使用()得到的是一个generator对象,所需要的内存空间与列表的大小无关,所以效率会高一些。在具体应用上,比如set(i for i in range(100000))会比set([i for i in range(100000)])快。
但是对于需要循环遍历的情况:
后者的效率反而更高,但是如果循环里有break,用generator的好处是显而易见的。yield也是用于创建generator:
对于内存不是非常大的list,可以直接返回一个list,但是可读性yield更佳(人个喜好)。
python2.x内置generator功能的有xrange函数、itertools包等。
循环之外能做的事不要放在循环内,比如下面的优化可以快一倍:
对于and,应该把满足条件少的放在前面,对于or,把满足条件多的放在前面。如:
join对于累加的方式,有大约5倍的提升。
三种情况中,%的方式是最慢的,但是三者的差距并不大(都非常快)。(个人觉得%的可读性最好)
使用a,b=b,a而不是c=a;a=b;b=c;来交换a,b的值,可以快1倍以上。