Python中字典的緩存池
前言：
我們知道字典里面有一個(gè)ma_keys和ma_values，其中ma_keys是一個(gè)指向PyDictKeysObject的指針，ma_values是一個(gè)指向PyObject *數(shù)組的二級(jí)指針。當(dāng)哈希表為分離表時(shí)，鍵由ma_keys維護(hù)，值由ma_values維護(hù)；當(dāng)哈希表為結(jié)合表時(shí)，鍵和值均由ma_keys維護(hù)。
那么當(dāng)我們?cè)阡N毀一個(gè)PyDictObject時(shí)，也肯定是要先釋放ma_keys和ma_values。
如果是分離表，會(huì)將每個(gè)value的引用計(jì)數(shù)減1，然后釋放ma_values；再將每個(gè)key的引用計(jì)數(shù)減1，然后釋放ma_keys。最后再釋放PyDictObject本身。
如果是結(jié)合表，由于key、value都在ma_keys中，將每個(gè)key、value的引用計(jì)數(shù)減1之后，只需要再釋放ma_keys即可。最后再釋放PyDictObject本身。
整個(gè)過程還是很清晰的，只不過這里面遺漏了點(diǎn)什么東西，沒錯(cuò)，就是緩存池。在介紹浮點(diǎn)數(shù)的時(shí)候，我們說不同的對(duì)象都有自己的緩存池，當(dāng)然字典也不例外。并且除了PyDictObject之外，PyDictKeysObject也有相應(yīng)的緩存池，畢竟它負(fù)責(zé)存儲(chǔ)具體的鍵值對(duì)。
那么下面我們就來研究一下這兩者的緩存池。
PyDictObject緩存池
字典的緩存池和列表的緩存池高度相似，都是采用數(shù)組實(shí)現(xiàn)的，并且容量也是80個(gè)。
#ifndef PyDict_MAXFREELIST #define PyDict_MAXFREELIST 80 #endif static PyDictObject *free_list[PyDict_MAXFEELIST]; static int numfree = 0; //緩存池當(dāng)前存儲(chǔ)的元素個(gè)數(shù)
開始時(shí)，這個(gè)緩存池什么也沒有，直到第一個(gè)PyDictObject對(duì)象被銷毀時(shí)，緩存池里面才開始接納被銷毀的PyDictObject對(duì)象。
static void
dict_dealloc(PyDictObject *mp)
{
//獲取ma_values指針
PyObject **values = mp->ma_values;
//獲取ma_keys指針
PyDictKeysObject *keys = mp->ma_keys;
Py_ssize_t i, n;
//因?yàn)橐讳N毀，所以讓GC不再跟蹤
PyObject_GC_UnTrack(mp);
//用于延遲釋放
Py_TRASHCAN_SAFE_BEGIN(mp)
//調(diào)整引用計(jì)數(shù)
//如果values不為NULL，說明是分離表
if (values != NULL) {
//將指向的value、key的引用計(jì)數(shù)減1
//然后釋放ma_values和ma_keys
if (values != empty_values) {
for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
Py_XDECREF(values[i]);
}
free_values(values);
}
DK_DECREF(keys);
}
//否則說明是結(jié)合表
else if (keys != NULL) {
//結(jié)合表的話，dk_refcnt一定是1
//此時(shí)只需要釋放ma_keys，因?yàn)殒I值對(duì)全部由它來維護(hù)
//在DK_DECREF里面，會(huì)將每個(gè)key、value的引用計(jì)數(shù)減1
//然后釋放ma_keys
assert(keys->dk_refcnt == 1);
DK_DECREF(keys);
}
//將被銷毀的對(duì)象放到緩存池當(dāng)中
if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
free_list[numfree++] = mp;
else
//如果緩存池已滿，則將釋放內(nèi)存
Py_TYPE(mp)->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}同理，當(dāng)創(chuàng)建字典時(shí)，也會(huì)優(yōu)先從緩存池里面獲取。
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
//...
if (numfree) {
mp = free_list[--numfree];
}
//...
}因此在緩存池的實(shí)現(xiàn)上，字典和列表有著很高的相似性。不僅都是由數(shù)組實(shí)現(xiàn)，在銷毀的時(shí)候也都會(huì)放在數(shù)組的尾部，創(chuàng)建的時(shí)候也會(huì)從數(shù)組的尾部獲取。當(dāng)然啦，因?yàn)檫@么做符合數(shù)組的特性，如果銷毀和創(chuàng)建都是在數(shù)組的頭部操作，那么時(shí)間復(fù)雜度就從O(1)變成了O(n)。
我們用Python來測(cè)試一下：
d1 = {k: 1 for k in "abcdef"}
d2 = {k: 1 for k in "abcdef"}
print("id(d1):", id(d1))
print("id(d2):", id(d2))
# 放到緩存池的尾部
del d1
del d2
# 緩存池：[d1, d2]
# 從緩存池的尾部獲取
# 顯然id(d3)和上面的id(d2)是相等的
d3 = {k: 1 for k in "abcdefghijk"}
# id(d4)和上面的id(d1)是相等的
d4 = {k: 1 for k in "abcdefghijk"}
print("id(d3):", id(d3))
print("id(d4):", id(d4))
# 輸出結(jié)果
"""
id(d1): 1363335780736
id(d2): 1363335780800
id(d3): 1363335780800
id(d4): 1363335780736
"""輸出結(jié)果和我們的預(yù)期是相符合的，以上就是PyDictObject的緩存池。
PyDictKeysObject緩存池
PyDictKeysObject也有自己的緩存池，同樣基于數(shù)組實(shí)現(xiàn)，大小是80。
//PyDictObject的緩存池叫 free_list //PyDictKeysObject的緩存池叫 keys_free_list //兩者不要搞混了 static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST]; static int numfreekeys = 0; //緩存池當(dāng)前存儲(chǔ)的元素個(gè)數(shù)
我們先來看看它的銷毀過程：
static void
free_keys_object(PyDictKeysObject *keys)
{
//將每個(gè)entry的me_key、me_value的引用計(jì)數(shù)減1
for (i = 0, n = keys->dk_nentries; i < n; i++) {
Py_XDECREF(entries[i].me_key);
Py_XDECREF(entries[i].me_value);
}
#if PyDict_MAXFREELIST > 0
//將其放在緩存池當(dāng)中
//當(dāng)緩存池未滿、并且dk_size為8的時(shí)候被緩存
if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
keys_free_list[numfreekeys++] = keys;
return;
}
#endif
PyObject_FREE(keys);
}銷毀的時(shí)候，也是放在了緩存池的尾部，那么創(chuàng)建的時(shí)候肯定也是先從緩存池的尾部獲取。
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
PyDictKeysObject *dk;
Py_ssize_t es, usable;
//...
//創(chuàng)建 ma_keys，如果緩存池有可用對(duì)象、并且size等于8，
//那么會(huì)從 keys_free_list 中獲取
if (size == PyDict_MINSIZE && numfreekeys > 0) {
dk = keys_free_list[--numfreekeys];
}
else {
// 否則malloc重新申請(qǐng)
dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
+ es * size
+ sizeof(PyDictKeyEntry) * usable);
}
}
//...
return dk;
}所以PyDictKeysObject的緩存池和列表同樣是高度相似的，只不過它想要被緩存，還需要滿足一個(gè)額外的條件，那就是dk_size必須等于8。很明顯，這個(gè)限制是出于對(duì)內(nèi)存方面的考量。
我們還是來驗(yàn)證一下：
import ctypes
class PyObject(ctypes.Structure):
_fields_ = [("ob_refcnt", ctypes.c_ssize_t),
("ob_type", ctypes.c_void_p)]
class PyDictObject(PyObject):
_fields_ = [("ma_used", ctypes.c_ssize_t),
("ma_version_tag", ctypes.c_uint64),
("ma_keys", ctypes.c_void_p),
("ma_values", ctypes.c_void_p)]
d1 = {_: 1 for _ in "mnuvwxyz12345"}
print(
PyDictObject.from_address(id(d1)).ma_keys
) # 1962690551536
# 鍵值對(duì)個(gè)數(shù)超過了8，dk_size必然也超過了 8
# 那么當(dāng)銷毀d1的時(shí)候，d1.ma_keys不會(huì)被緩存
# 而是會(huì)直接釋放掉
del d1
d2 = {_: 1 for _ in "a"}
print(
PyDictObject.from_address(id(d2)).ma_keys
) # 1962387670624
# d2 的 dk_size 顯然等于 8
# 因此它的 ma_keys 是會(huì)被緩存的
del d2
d3 = {_: 1 for _ in "abcdefg"}
print(
PyDictObject.from_address(id(d3)).ma_keys
) # 1962699215808
# 盡管 d2 的 ma_keys 被緩存起來了
# 但是 d3 的 dk_size 大于 8
# 因此它不會(huì)從緩存池中獲取，而是重新創(chuàng)建
# d4 的 dk_size 等于 8
# 因此它會(huì)獲取 d2 被銷毀的 ma_keys
d4 = {_: 1 for _ in "abc"}
print(
PyDictObject.from_address(id(d4)).ma_keys
) # 1962387670624所以從打印的結(jié)果來看，由于d4.ma_keys和d2.ma_keys是相同的，因此證實(shí)了我們的結(jié)論。不像列表和字典，它們是只要被銷毀，就會(huì)放到緩存池里面，因?yàn)樗鼈儧]有存儲(chǔ)具體的數(shù)據(jù)，大小是固定的。
但是PyDictKeysObject不同，它存儲(chǔ)了entry，每個(gè)entry占24字節(jié)。如果內(nèi)部的entry非常多，那么緩存起來會(huì)有額外的內(nèi)存開銷。因此Python的策略是，只有在dk_size等于8的時(shí)候，才會(huì)緩存。當(dāng)然這三者在緩存池的實(shí)現(xiàn)上，是基本一致的。
小結(jié)
總的來說，Python的字典是一個(gè)被高度優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榻忉屍髟谶\(yùn)行的時(shí)候也重度依賴字典，這就決定了它的效率會(huì)非常高。當(dāng)然，我們沒有涉及字典的全部?jī)?nèi)容，比如字典有很多方法，比如keys、values、items方法等等，我們并沒有說。這些有興趣的話，可以對(duì)著源碼看一遍，不是很難。總之我們平時(shí)，也可以盡量多使用字典。
到此這篇關(guān)于Python中字典的緩存池的文章就介紹到這了,更多相關(guān)Python緩存池內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python光學(xué)仿真學(xué)習(xí)Gauss高斯光束在空間中的分布
這篇文章主要介紹了Python光學(xué)仿真學(xué)習(xí)中Gauss高斯光束在空間中的分布理解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2021-10-10
Python的numpy庫(kù)下的幾個(gè)小函數(shù)的用法(小結(jié))
這篇文章主要介紹了Python的numpy庫(kù)下的幾個(gè)小函數(shù)的用法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
解決Python plt.savefig 保存圖片時(shí)一片空白的問題
今天小編就為大家分享一篇解決Python plt.savefig 保存圖片時(shí)一片空白的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-01-01
通過mod_python配置運(yùn)行在Apache上的Django框架
這篇文章主要介紹了通過mod_python配置運(yùn)行在Apache上的Django框架,Django是最具人氣的Python web開發(fā)框架,需要的朋友可以參考下2015-07-07
Python中函數(shù)的創(chuàng)建與調(diào)用你了解嗎
這篇文章主要為大家詳細(xì)介紹了Python中函數(shù)的創(chuàng)建與調(diào)用，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
tensorflow實(shí)現(xiàn)簡(jiǎn)單的卷積神經(jīng)網(wǎng)絡(luò)
這篇文章主要為大家詳細(xì)介紹了tensorflow實(shí)現(xiàn)簡(jiǎn)單的卷積神經(jīng)網(wǎng)絡(luò)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
讓你分分鐘學(xué)會(huì)python條件語(yǔ)句
學(xué)好Python和條件語(yǔ)句,將方便有效提高工作效率,這篇文章主要給大家介紹了關(guān)于python條件語(yǔ)句的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08
python?Ajenti控制面板輕松地管理所有服務(wù)器網(wǎng)站
Ajenti是一個(gè)值得擁有的管理面板,免費(fèi)開源的管理面板工具,可以幫助你集中管理多個(gè)服務(wù)器和網(wǎng)站,Ajenti?支持?Linux、BSD、Mac?OS?X和Windows?等多個(gè)操作系統(tǒng),并且可以通過一個(gè)直觀的?Web?界面來完成各種系統(tǒng)管理任務(wù)2024-01-01
本文主要介紹了Python中Tkinter布局管理grid的使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
解決django-xadmin列表頁(yè)filter關(guān)聯(lián)對(duì)象搜索問題
今天小編就為大家分享一篇解決django-xadmin列表頁(yè)filter關(guān)聯(lián)對(duì)象搜索問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-11-11