優化算法時間復雜度

算法的時間復雜度對程序的執行效率影響最大，在Python中可以通過選擇合適的數據結構來優化時間復雜度，如list和set查找某一個元素的時間復雜度分別是O(n)和O(1)。不同的場景有不同的優化方式，總得來說，一般有分治，分支界限，貪心，動態規劃等思想。

減少冗余數據

如用上三角或下三角的方式去保存一個大的對稱矩陣。在0元素占大多數的矩陣里使用稀疏矩陣表示。

合理使用copy與deepcopy

對于dict和list等數據結構的對象，直接賦值使用的是引用的方式。而有些情況下需要復制整個對象，這時可以使用copy包里的copy和deepcopy，這兩個函數的不同之處在于后者是遞歸復制的。效率也不一樣：（以下程序在ipython中運行）

import copya = range(100000)%timeit -n 10 copy.copy(a) # 運行10次 copy.copy(a)%timeit -n 10 copy.deepcopy(a)10 loops, best of 3: 1.55 ms per loop10 loops, best of 3: 151 ms per loop

timeit后面的-n表示運行的次數，后兩行對應的是兩個timeit的輸出，下同。由此可見后者慢一個數量級。

使用dict或set查找元素

python dict和set都是使用hash表來實現(類似c++11標準庫中unordered_map)，查找元素的時間復雜度是O(1)

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 s10000 loops, best of 3: 43.5 ns per loop10000 loops, best of 3: 49.6 ns per loop

dict的效率略高(占用的空間也多一些)。

合理使用生成器（generator）和yield

%timeit -n 100 a = (i for i in range(100000))%timeit -n 100 b = [i for i in range(100000)]100 loops, best of 3: 1.54 ms per loop100 loops, best of 3: 4.56 ms per loop

使用()得到的是一個generator對象，所需要的內存空間與列表的大小無關，所以效率會高一些。在具體應用上，比如set(i for i in range(100000))會比set([i for i in range(100000)])快。

但是對于需要循環遍歷的情況：

%timeit -n 10 for x in (i for i in range(100000)): pass%timeit -n 10 for x in [i for i in range(100000)]: pass10 loops, best of 3: 6.51 ms per loop10 loops, best of 3: 5.54 ms per loop

后者的效率反而更高，但是如果循環里有break,用generator的好處是顯而易見的。yield也是用于創建generator：

def yield_func(ls): for i in ls: yield i+1def not_yield_func(ls): return [i+1 for i in ls]ls = range(1000000)%timeit -n 10 for i in yield_func(ls):pass%timeit -n 10 for i in not_yield_func(ls):pass10 loops, best of 3: 63.8 ms per loop10 loops, best of 3: 62.9 ms per loop

對于內存不是非常大的list，可以直接返回一個list，但是可讀性yield更佳(人個喜好)。

python2.x內置generator功能的有xrange函數、itertools包等。