用對(duì)數(shù)據(jù)結(jié)構(gòu)是一個(gè)程序員應(yīng)用的基本技能，這篇整理一下python中基本的抽象數(shù)據(jù)類(lèi)型的一下特征，主要是增刪改查方面的性能。
list
python的列表內(nèi)部實(shí)現(xiàn)是數(shù)組（具體實(shí)現(xiàn)要看解析器, CPython的實(shí)現(xiàn) ），因此就有組數(shù)的特點(diǎn)安岂。超過(guò)容量會(huì)增加更多的容量，set, get 是O(1)帆吻，但del, insert, in的性能是O(n)域那。具體的看下表，'n'是容器中當(dāng)前的元素?cái)?shù)猜煮， 'k'需要操作的元素個(gè)數(shù)
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy | O(n) | O(n) |
| Append[1] | O(1) | O(1) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| Extend[1] | O(k) | O(k) |
| Sort | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | |
| min(s), max(s) | O(n) | |
| Get Length | O(1) | O(1) |
dict
關(guān)于字典需要了解的是hash函數(shù)和哈希桶次员。一個(gè)好的hash函數(shù)使到哈希桶中的值只有一個(gè)，若多個(gè)key hash到了同一個(gè)哈希桶中王带，稱之為哈希沖突淑蔚。查找值時(shí)，會(huì)先定位到哈希桶中愕撰，再遍歷hash桶刹衫。更詳細(xì)的信息請(qǐng)點(diǎn)這里。在hash基本沒(méi)有沖突的情況下get, set, delete, in方面都是O(1)搞挣。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy[2] | O(n) | O(n) |
| Get Item | O(1) | O(n) |
| Set Item[1] | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| x in s | O(1) | O(n) |
| Iteration[2] | O(n) | O(n) |
set
內(nèi)部實(shí)現(xiàn)是dict的带迟。在in操作上是O(1), 這一點(diǎn)比list要強(qiáng)。
| Operation | Average case | Worst Case |
|---|---|---|
| x in s | O(1) | O(n) |
| Union s|t | O(len(s)+len(t)) | |
| Intersection s&t | O(min(len(s), len(t)) | O(len(s) * len(t)) |
| Multiple intersection s1&s2&..&sn | (n-1)*O(l) where l is max(len(s1),..,len(sn)) | |
| Difference s-t | O(len(s)) | |
| s.difference_update(t) | O(len(t)) | |
| Symmetric Difference s^t | O(len(s)) | O(len(s) * len(t)) |
| s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) |
