- Python里的dict和set的效率有多高?
- 為什么它們是無序的?
- 為什么并不是所有的Python物件都可以當作dict的鍵或set里的元素?
- 為什么dict的鍵和set的元素的順序是根據它們被添加的次序而定的,以及為什么在映射物件的生命周期中,這個順序并不是一成不變的?
- 為什么不應該在迭代回圈dict或是set的同時往里添加元素?
Python里的dict和set的效率有多高?
由實驗得知,不管查詢有多少個元素的字典或集合,所耗費的時間都能忽略不計(前提是字典或者集合不超過記憶體大小).
字典中的散串列
散串列其實是一個稀疏陣列(總是有空白元素的陣列被稱為稀疏陣列).在一般的資料結構教材中,散串列里的單元通常叫作表元(bucket).
在dict的散串列當中,每個鍵值對都占用一個表元,每個表元都有兩個部分,一個是對鍵的參考,另一個是對值的參考.
因為所有的表元的大小一致,所以可以通過偏移量來讀取某個表元.
Python會設法保證大概還有三分之一的表元是空的,所以在快要達到這個閾值的時候,原有散串列會被復制到一個更大的空間里面.
如果要把一個物件放入散串列,那么首先要計算這個元素鍵的散列值.Python中可以用hash()方法來做這件事情.
1.散列值和相等性
內置的hash()方法可以用于所有的內置型別物件.如果是自定義物件呼叫hash()的話,實際上運行的是自定義的__hash__.
如果這兩個物件在比較的時候是相等的,那么它們的散列值必須相等,否則散串列就不能正常運行了.
例如,如果11.0為真,那么hash(1)hash(1.0)也必須為真,但其實這兩個數字(整型和浮點)的內部結構是完全不一樣的.
既然提到了整型,CPython的實作細節里有一條是:如果有一個整型物件,而且它能被存進一個機器字中,那么它的散列值就是它本身的值.
為了讓散列值能夠勝任散串列索引這一角色,它們必須在索引空間中盡量分散開來.這意味著在最理想的狀況下,越是相似但不相等的物件,它們散列值的差別應該越大.
"""
import sys
# 通過sys.maxsize獲取作業系統的整數最大值,轉換成二進制,計算位數,加上一個符號位
MAX_BITS = len(format(sys.maxsize, 'b'))
print('%s-bit Python build' % (MAX_BITS + 1))
def hash_diff(o1, o2):
h1 = '{:>0{}b}'.format(hash(o1), MAX_BITS) # 計算o1的散列值,并用0補滿空位
h2 = '{:>0{}b}'.format(hash(o2), MAX_BITS) # 計算o2的散列值,并用0補滿空位
# 比較h1和h2的每一位,用!標識出來,否則用' '表示
diff = ''.join('!' if b1 != b2 else ' ' for b1, b2 in zip(h1, h2))
count = '!={}'.format(diff.count('!')) # 顯示不同的總數
width = max(len(repr(o1)), len(repr(o2)), 8) # 行頭的寬度
sep = '_' * (width * 2 + MAX_BITS) # 分割線
return '{!r:{width}} {}\n{:{width}} {} {}\n{!r:{width}} {}\n{}'.format(
o1, h1, ' ' * width, diff, count, o2, h2, sep, width=width
)
print(hash_diff(1, 1.0))
print(hash_diff(1.0, 1.0001))
print(hash_diff(1.0001, 1.0002))
print(hash_diff(1.0002, 1.0003))
從Python3.3開始,str,bytes和datetime物件的散列值計算程序中多了隨機的'加鹽'這一步.
所加鹽值是Python行程內的一個常量,但是每次啟動Python解釋器都會生成一個不同的鹽值.
隨機鹽值的加入是為了防止DOS攻擊而采取的一種安全措施.
散串列演算法
為了獲取my_dict[search_key]背后的值,Python首先會呼叫hash(search_key)來計算search_key的散列值,把這個值最低的幾位數字當作偏移量,在散串列里查找表元(具體取幾位,得看當前散串列的大小).若找到的表元是空的,則拋出KeyError例外.
若不是空的,則表元里會有一對found_key:found_value.這時候Python會檢驗search_key == found_key是否為真,如果是,就會回傳found_value.
如果search_key和found_key不匹配的話,這種情況稱為[散列沖突].發生這種情況是因為,散串列所做的其實是把隨機的元素映射到只有幾位的數字上,而散串列本身的索引又只能依賴于這個數字的一部分.為了解決散列沖突,演算法會在散列值中另外再取幾位,然后用特殊的方法處理一下,把新得到的數字再當作索引來尋找表元.
若這次找到的表元是空的,則同樣拋出KeyError;若非空,或者鍵匹配,則回傳這個值;或者又發現了散列沖突,則重復以上的步驟.
從字典中取值的演算法流程如下:給定一個鍵,這個演算法要么回傳一個值,要么拋出KeyError例外
|-------------------------------------------------------------------------|
|計算鍵的散列值 ________使用散列值的另一部分來定位散串列中的零一行 |
| | | ↑ |
| | | | 否 (散列沖突) |
| | ↓ | |
|使用散列值的一部分 表元 | |
|來定位散串列中的一 ------→ 為空? ---------否-------→ 鍵相等? |
|個表元 | | |
| |是 |是 |
| ↓ ↓ |
| 拋出KeyError 回傳表元里的值 |
|--------------------------------------------------------------------------|
添加新元素和更新現有鍵值的操作幾乎跟上面一樣.只不過對于前者,在發現空表元的時候會放入一個新元素;
對于后者,在找到對應的表元后,原表里值物件會被替換成新值.
另外在插入新值時,Python可能會按照散串列的擁擠程度來決定是否要重新分配記憶體來為它擴容.如果增加了散串列的大小,那散列值所占的位數和用作索引的位數就會隨之增加,這樣做的目的是為了減少發生散列沖突的概率.
表面上看,這個演算法似乎很費事,而實際上就是dict里有數百萬個元素,多數的搜索程序中并不會有沖突發生,平均下來每次搜索可能會有一到兩次沖突.
在正常情況下,就算是最不走運的鍵所遇到的沖突的次數用一只手也能數過來.
dict的實作及其導致的結果
1.鍵必須死可散列的
一個可散列的物件必須滿足以下要求:
1)支持hash()函式,并且通過__hash__()方法所得到的散列值是不變的.
2)支持通過__eq__()方法來檢測相等性.
3)若a == b為真,則hash(a) == hash(b)也為真
所有由用戶定義的物件默認都是可散列的,因為它們散列值由id()來獲取,而且它們都是不相等的.
如果你實作了一個類的__eq__()方法,并且希望它是可散列的,那么它一點要有個恰當的__hash__方法,保證a==b為真的情況下hash(a)==hash(b)也必定為真.
否則就會破壞恒定的散串列演算法,導致由這些物件所組成的字典和集合完全失去可靠性,這個后果是非常可怕的.
另一方面,如果一個含有自定義__eq__依賴的類處于可變的狀態,那就不要在這個類中實作__hash__方法,因為它的實體時不可散列的.
'''
學習中遇到問題沒人解答？小編創建了一個Python學習交流群：725638078
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學習教程和PDF電子書！
'''
class A:
def __init__(self, a):
self.a = a
def __hash__(self):
return 1
def __eq__(self, other):
return hash_diff(self, other)
def __repr__(self):
return str(self.a)
a = A(1)
b = A(2)
d1 = {a: 1, b: 2, 1: 3}
print(d1) # {1: 3} 會發現里面只有一個鍵值對
2.字典在記憶體上的開銷巨大
由于字典使用了散串列,而散串列又必須時稀疏的,這導致它在空間上的效率低下.舉例而言.如果你需要存放數量巨大的記錄,那么放在由元組或是具名元組構成的串列中會是比較好的選擇;
最好不要根據JSON的風格,用由字典組成的串列來存放這些記錄,用元組取代字典能節省空間的原因有兩個:
其一是避免了散串列所消耗的空間. 其二是無需把記錄中欄位的名字在每個元素里都存一遍.
在用戶自定義的型別中,__slots__屬性可以改變實體屬性的存盤方式,由dict變成tuple.
3.鍵查詢很快
dict的實作是典型的空間換時間:字典型別有著巨大的記憶體開銷,但它們提供了無視資料量的快速訪問--只要字典能被裝在記憶體里.
4.鍵的次序取決于添加順序
當往dict里添加新鍵而又發生散列沖突的時候,新鍵可能會被安排存放到另一個位置.于是下面的這種情況就會發生:
由dict([(key1, value1), (key2, value2)])和dict([(key2, value2), (key1, value1)])得到的兩個字典,在進行比較的時候,它們是相等的.
但是如果在key1和key2被添加到字典里的程序中有沖突發生的話,這兩個鍵出現在字典里的順序是不一樣的.
下面的示例展示了這個現橡.這個示例用同樣的資料創建了3個字典,唯一的區別就是資料出現的順序不一樣.可以看到,雖然鍵的次序是亂的,這3個字典仍然被視作相等的.
STUDENTS = [
(89, '孫悟空'),
(79, '豬八戒'),
(69, '沙和尚'),
(59, '小白龍'),
(49, '唐僧')
]
d1 = dict(STUDENTS)
print('d1:', d1.keys())
d2 = dict(sorted(STUDENTS))
print('d2:', d2.keys())
d3 = dict(sorted(STUDENTS, key=lambda x: x[1]))
print('d3', d3.keys())
assert d1 == d2 and d2 == d3
5.往字典里添加新鍵可能會改變已有鍵的順序
無論何時往字典里添加新的鍵,Python解釋器都可能做出為字典擴容的決定.擴容導致的結果就是要新建一個更大的散串列,并把字典里已有的元素添加到新表里.
這個程序可能會發生新的散列沖突,導致新散串列中鍵的次序變化.
要注意的是,上面提到的這些變化是否會發生以及如何發生,都依賴于字典背后的實作,因此你不能很自信的說自己知道背后發生了什么.
如果你在迭代一個字典的所有鍵的程序中同時對字典進行修改,那么這個回圈很可能會跳過一些鍵----甚至是跳過那些字典中已經有的鍵.
由此可知,不要對字典同時進行迭代和修改.如果想掃描并修改一個字典,最好分成兩步來進行:
首先對字典迭代,以得出需要添加的內容,把這些內容放在一個新字典里;迭代結束之后再對原字典進行更新.
在Python3中,.keys() .items() .values()方法回傳的都是字典視圖.也就是說,這些方法回傳的值更像集合.
set的實作及其導致的結果
set和frozenset的實作也依賴散串列,但在它們的散串列里存放的只有元素的參考.在set加入到Python之前,我們都是把字典加上無意義的值當作集合來用.
1.集合里的元素必須是可散列的.
2.集合很消耗記憶體.
3.可以很高效的判斷元素是否存在于某個集合.
4.元素的次序取決于被添加到集合里的次序.
5.往集合里添加元素,可能會改變集合里已有元素的次序.
結尾給大家推薦一個非常好的學習教程，希望對你學習Python有幫助！
Python基礎入門教程推薦：更多Python視頻教程-關注B站：Python學習者
https://www.bilibili.com/video/BV1LL4y1h7ny?share_source=copy_web
Python爬蟲案例教程推薦：更多Python視頻教程-關注B站：Python學習者
https://www.bilibili.com/video/BV1QZ4y1N7YA?share_source=copy_web
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/341703.html
標籤：Python