當前位置:成語大全網 - 新華字典 - python內置數據類型列表list和字典dict的性能

python內置數據類型列表list和字典dict的性能

我們來討論下python的兩種最重要的內置數據類型列表list和字典dict上,各種操作的復雜度。

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