list列表數據類型常用操作性能:
1、按索引取值和賦值(v=a[i],a[i]=v)
由於列表的隨機訪問特性,這兩個操作執行時間與列表大小無關,均為O(1)
2、列表的曾長,可以選擇append()和_add_() "+"
list.append(v)的執行時間O(1)
list = list + [v],執行時間是O(n+k),因為新增了壹個新的列表,其中k是被加的列表長度
舉例:4種生成前n個整數列表的方法
如圖:
我們可以計算壹下這四個函數的耗時,如下
執行結果:
我們可以看到,4種方法運行時間差別很大,test1使用列表連接最慢,而test4使用list range最快,速度相差近200倍。
如下圖,我們總結下list基本操作的性能如何:
上圖可知pop()從列表末尾移除元素O(1),但是pop(i)從列表中間移除元素要O(n),為什麽呢?
因為從中部移除元素,要把移除元素後面的元素全部向前挪壹位,才保證了列表按索引取值和賦值很快,達到O(1)。
dict數據類型:
字典和列表不同,dict根據key找到value,而list根據index。
字典最常用的取值get和賦值set,其性能為O(1),而contain(in)操作判斷字典是否存在某個key,其性能也是O(1)
list和dict的in操作對比:
設計壹個性能試驗,驗證list中檢索壹個值,對比dict中檢索壹個值的耗時對比。如下程序:
如果如下:
可見list的in操作復雜度為O(n)
PS:大家可以去python官方的算法復雜度網站看看:
https://wiki.python.org/moin/TimeComplexity