| 操作 | 復雜度 |
|---|---|
| 復制 | O(N) |
| 添加元素(在尾部添加) | O(1) |
| 插入元素(在指定位置插入) | O(N) |
| 獲取元素 | O(1) |
| 修改元素 | O(1) |
| 刪除元素 | O(N) |
| 遍歷 | O(N) |
| 獲取長度為k的切片 | O(k) |
| 刪除切片 | O(N) |
| 列表擴展 | O(k) |
| 測試是否在列表中 | O(N) |
| min()/max() | O(n) |
| 獲取列表長度 | O(1) |
要習慣用列表推導，因為這更加高效和簡短，涉及的語法元素少。在大型的程序中，這意味著更少的錯誤，代碼也更容易閱讀。
>>>[i for i in range(10) if i % 2 == 0] [0, 2, 4, 6, 8]
1.使用enumerate.在循環(huán)使用序列時，這個內置函數(shù)可以方便的獲取其索引：
for i, element in enumerate(['one', 'two', 'three']): print(i, element)
result：
0 one 1 two 2 three
2.如果需要一個一個合并多個列表中的元素，可以使用zip()。對兩個大小相等的可迭代對象進行均勻遍歷時，這是一個非常常用的模式：
for item in zip([1, 2, 3], [4, 5, 6]): print(item)
(1, 4) (2, 5) (3, 6)
3.序列解包
#帶星號的表達式可以獲取序列的剩余部分 >>>first, second, *reset = 0, 1, 2, 3 >>>first 0 >>>second 1 >>>reset [2, 3]
字典是python中最通用的數(shù)據(jù)結構之一。dict可以將一組唯一的鍵映射到相應的值。
我們也可以用前面列表推導的方式來創(chuàng)建一個字典。
squares = {number: number**2 for number in range(10)}
print(squares)
result：
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
在遍歷字典元素時，有一點需要特別注意。字典里的keys(), values()和items()3個方法的返回值不再是列表，而是視圖對象（view objects）。
keys(): 返回dict_keys對象，可以查看字典所有鍵
values():返回dict_values對象，可以查看字典的所有值
items():返回dict_items對象，可以查看字典所有的{key, value}二元元組。
視圖對象可以動態(tài)查看字典的內容，因此每次字典發(fā)生變化的時候，視圖都會相應的改變，見下面這個例子：
words = {'foo': 'bar', 'fizz': 'bazz'}
items= words.items()
words['spam'] = 'eggs'
print(items)
result：
dict_items([('foo', 'bar'), ('fizz', 'bazz'), ('spam', 'eggs')])
視圖無需冗余的將所有值都保存在內存中，像列表那樣。但你仍然可以獲取其長度（使用len）,也可以測試元素是否包含在其中（使用in子句）。當然，視圖是迭代的。
CPython使用偽隨機探測(pseudo-random probing)的散列表(hash table)作為字典的底層數(shù)據(jù)結構。由于這個實現(xiàn)細節(jié)，只有可哈希的對象才能作為字典的鍵。
Python中所有不可變的內置類型都是可哈希的?？勺冾愋停ㄈ缌斜?，字典和集合）就是不可哈希的，因此不能作為字典的鍵。
字典的三個基本操作（添加元素，獲取元素和刪除元素）的平均事件復雜度為O(1)，但是他們的平攤最壞情況復雜度要高得多，為O(N).
| 操作 | 平均復雜度 | 平攤最壞情況復雜度 |
|---|---|---|
| 獲取元素 | O(1) | O(n) |
| 修改元素 | O(1) | O(n) |
| 刪除元素 | O(1) | O(n) |
| 復制 | O(n) | O(n) |
| 遍歷 | O(n) | O(n) |
還有一點很重要，在復制和遍歷字典的操作中，最壞的復雜度中的n是字典曾經(jīng)達到的最大元素數(shù)目，而不是當前的元素數(shù)目。換句話說，如果一個字典曾經(jīng)元素個數(shù)很多，后來又大大減小了，那么遍歷這個字典可能會花費相當長的事件。
因此在某些情況下，如果需要頻繁的遍歷某個詞典，那么最好創(chuàng)建一個新的字典對象，而不是僅在舊字典中刪除元素。
使用字典的常見陷阱就是，它并不會按照鍵的添加順序來保存元素的順序。在某些情況下，字典的鍵是連續(xù)的，對應的散列值也是連續(xù)值（例如整數(shù)），那么由于字典的內部實現(xiàn)，元素的實現(xiàn)可能和添加的順序相同：
keys = {num: None for num in range(5)}.keys()
print(keys)
result：
dict_keys([0, 1, 2, 3, 4])
但是，如果散列方法不同的其它數(shù)據(jù)類型，那么字典就不會保存元素順序。
age = {str(i): i for i in range(100)}
keys = age.keys()
print(keys)
result：
dict_keys(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '30', '31', '32', '33', '34', '35', '36', '37', '38', '39', '40', '41', '42', '43', '44', '45', '46', '47', '48', '49', '50', '51', '52', '53', '54', '55', '56', '57', '58', '59', '60', '61', '62', '63', '64', '65', '66', '67', '68', '69', '70', '71', '72', '73', '74', '75', '76', '77', '78', '79', '80', '81', '82', '83', '84', '85', '86', '87', '88', '89', '90', '91', '92', '93', '94', '95', '96', '97', '98', '99'])
理論上，鍵的順序不應該是這樣的，應該是亂序。。。具體為什么這樣，等以后明白了再補充
如果我們需要保存添加順序怎么辦？python 標準庫的collections模塊提供了名為OrderedDicr的有序字典。
集合是一種魯棒性很好的數(shù)據(jù)結構，當元素順序的重要性不如元素的唯一性和測試元素是否包含在集合中的效率時，大部分情況下這種數(shù)據(jù)結構極其有用。
python的內置集合類型有兩種：
set(): 一種可變的、無序的、有限的集合，其元素是唯一的、不可變的（可哈希的）對象。
frozenset(): 一種不可變的、可哈希的、無序的集合，其元素是唯一的，不可變的哈希對象。
set([set([1, 2, 3]), set([2, 3, 4])])
result:
Traceback (most recent call last): File "/pycharm_project/LearnPython/Part1/demo.py", line 1, in module> set([set([1, 2, 3]), set([2, 3, 4])]) TypeError: unhashable type: 'set'
set([frozenset([1, 2, 3]), frozenset([2, 3, 4])])
result:不會報錯
set里的元素必須是唯一的，不可變的。但是set是可變的，所以set作為set的元素會報錯。
CPython中集合和字典非常相似。事實上，集合被實現(xiàn)為帶有空值的字典，只有鍵才是實際的集合元素。此外，集合還利用這種沒有值的映射做了其它的優(yōu)化。
由于這一點，可以快速的向集合中添加元素、刪除元素、檢查元素是否存在。平均時間復雜度為O(1),最壞的事件復雜度是O(n)。
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。如有錯誤或未考慮完全的地方，望不吝賜教。
標簽：錫林郭勒盟 梅州 浙江 昆明 懷化 石家莊 西寧 文山
巨人網(wǎng)絡通訊聲明：本文標題《Python 列表(List)的底層實現(xiàn)原理分析》，本文關鍵詞 Python,列表,List,的,底層,；如發(fā)現(xiàn)本文內容存在版權問題，煩請?zhí)峁┫嚓P信息告之我們，我們將及時溝通與處理。本站內容系統(tǒng)采集于網(wǎng)絡，涉及言論、版權與本站無關。