算法的時(shí)間復(fù)雜度對(duì)程序的執(zhí)行效率影響最大,在Python中可以通過(guò)選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化時(shí)間復(fù)雜度,如list和set查找某一個(gè)元素的時(shí)間復(fù)雜度分別是O(n)和O(1)。不同的場(chǎng)景有不同的優(yōu)化方式,總得來(lái)說(shuō),一般有分治,分支界限,貪心,動(dòng)態(tài)規(guī)劃等思想。
如用上三角或下三角的方式去保存一個(gè)大的對(duì)稱矩陣。在0元素占大多數(shù)的矩陣?yán)锸褂孟∈杈仃嚤硎尽?/p>
對(duì)于dict和list等數(shù)據(jù)結(jié)構(gòu)的對(duì)象,直接賦值使用的是引用的方式。而有些情況下需要復(fù)制整個(gè)對(duì)象,這時(shí)可以使用copy包里的copy和deepcopy,這兩個(gè)函數(shù)的不同之處在于后者是遞歸復(fù)制的。效率也不一樣:(以下程序在ipython中運(yùn)行)
import copya = range(100000)%timeit -n 10 copy.copy(a) # 運(yùn)行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表示運(yùn)行的次數(shù),后兩行對(duì)應(yīng)的是兩個(gè)timeit的輸出,下同。由此可見(jiàn)后者慢一個(gè)數(shù)量級(jí)。
python dict和set都是使用hash表來(lái)實(shí)現(xiàn)(類似c++11標(biāo)準(zhǔn)庫(kù)中unordered_map),查找元素的時(shí)間復(fù)雜度是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的效率略高(占用的空間也多一些)。
%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
使用()得到的是一個(gè)generator對(duì)象,所需要的內(nèi)存空間與列表的大小無(wú)關(guān),所以效率會(huì)高一些。在具體應(yīng)用上,比如set(i for i in range(100000))會(huì)比set([i for i in range(100000)])快。
但是對(duì)于需要循環(huán)遍歷的情況:
%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
后者的效率反而更高,但是如果循環(huán)里有break,用generator的好處是顯而易見(jiàn)的。yield也是用于創(chuàng)建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
對(duì)于內(nèi)存不是非常大的list,可以直接返回一個(gè)list,但是可讀性yield更佳(人個(gè)喜好)。
python2.x內(nèi)置generator功能的有xrange函數(shù)、itertools包等。
新聞熱點(diǎn)
疑難解答
圖片精選