[[387994]]

“ resize 是增加列表開(kāi)銷(xiāo)的重要因素。”

Python 列表底層是通過(guò)存儲(chǔ)對(duì)象指針的變長(zhǎng)數(shù)組來(lái)實(shí)現(xiàn)的，使用數(shù)組帶來(lái)的好處就是可以通過(guò)索引隨機(jī)訪問(wèn)列表中的元素。

然而，由于 list 屬于可變數(shù)據(jù)類(lèi)型，我們可以動(dòng)態(tài)地在 list 中增減元素，當(dāng)?shù)讓訑?shù)組不足以容納新元素時(shí)，就要調(diào)整其大小了。這正是“變長(zhǎng)”的含義所在。

那么，list 使用的變長(zhǎng)數(shù)組是如何調(diào)整其大小呢?我們通過(guò)閱讀 Python 源碼來(lái)做下簡(jiǎn)單分析。

【列表初始內(nèi)存分配機(jī)制】

先來(lái)了解一下，創(chuàng)建一個(gè) list 時(shí)，list 底層數(shù)組是什么樣子的。

list___init__() 是創(chuàng)建 list 對(duì)象的接口函數(shù)。它調(diào)用了 list___init___impl(self, iterable)。list___init___impl 接受一個(gè) iterable 作為初始化源。這和我們通常初始化一個(gè) list 對(duì)象的方式是一致的。

list___init___impl 做了哪些初始化工作呢?

list___init___impl() 首先將入?yún)?self 指向的對(duì)象清空，原因是：Python 為提升創(chuàng)建 list 對(duì)象的效率，維護(hù)了一個(gè) free_list 對(duì)象池。它可以回收不再使用的 list 對(duì)象，并重新分配給新 list 對(duì)象使用。

/* Empty list reuse scheme to save calls to malloc and free */ 
#ifndef PyList_MAXFREELIST 
#  define PyList_MAXFREELIST 80 
#endif 
 
static PyListObject *free_list[PyList_MAXFREELIST]; 
static int numfree = 0; 

這個(gè) list 內(nèi)存池的大小為 80.

如果 self 指向的是一個(gè)緩存池中的對(duì)象，則需要先將它清理干凈。

然后，list___init___impl() 調(diào)用 list_preallocate_exact() 為 self 的變長(zhǎng)數(shù)組分配一塊內(nèi)存，這個(gè)數(shù)組中元素的個(gè)數(shù)和 iterable 中元素的個(gè)數(shù)相同。

這樣，list 對(duì)象使用的變長(zhǎng)數(shù)組就創(chuàng)建好了。

【列表 resize 的實(shí)現(xiàn)算法】

那么，變長(zhǎng)數(shù)組是使用什么算法來(lái)調(diào)整其大小呢?

這個(gè)邏輯是在 list_resize() 函數(shù)中實(shí)現(xiàn)的。先看代碼。

static int 
list_resize(PyListObject *self, Py_ssize_t newsize) 
{ 
    PyObject **items; 
    size_t new_allocated, num_allocated_bytes; 
    Py_ssize_t allocated = self->allocated; 
 
    /*Step 1*/ 
    if (allocated >= newsize && newsize >= (allocated >> 1)) { 
        assert(self->ob_item != NULL || newsize == 0); 
        Py_SET_SIZE(self, newsize); 
        return 0; 
    } 
 
    /*Step 2*/ 
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3; 
    /* Do not overallocate if the new size is closer to overalocated size 
     * than to the old size. 
     */ 
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize)) 
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3; 
 
    if (newsize == 0) 
        new_allocated = 0; 
         
    /*Step 3*/ 
    num_allocated_bytes = new_allocated * sizeof(PyObject *); 
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes); 
    if (items == NULL) { 
        PyErr_NoMemory(); 
        return -1; 
    } 
     
    /*Step 4*/ 
    self->ob_item = items; 
    Py_SET_SIZE(self, newsize); 
    self->allocated = new_allocated; 
    return 0; 
} 

list_resize() 的處理邏輯為：

1. 先判斷原 list 對(duì)象已分配的空間是否滿足新需求：大于 newsize，且不超過(guò) newsize 的兩倍(超過(guò) newsize 兩倍時(shí)，需要縮短已分配空間)。滿足，則無(wú)需再調(diào)整。
2. 計(jì)算新數(shù)組的需要容納的元素的數(shù)目：new_allocated。這個(gè)算法有點(diǎn)難理解：它會(huì)額外分配一些內(nèi)存，并將這塊內(nèi)存以 4 的倍數(shù)進(jìn)行對(duì)齊?？梢圆挥萌ゼ?xì)究為什么要這樣計(jì)算。
3. 計(jì)算需要重新分配的內(nèi)存大?。簄um_allocated_bytes。
4. 調(diào)用 PyMem_Realloc() 分配內(nèi)存。

更新 self 指向?qū)ο蟮南嚓P(guān)屬性：調(diào)整變長(zhǎng)數(shù)組指針的指向，設(shè)置 list 中元素的個(gè)數(shù)，設(shè)置已分配空間的大小。

【哪些操作會(huì)導(dǎo)致列表 resize?】

我們已經(jīng)了解了 resize 的執(zhí)行邏輯。那么 list 會(huì)在什么情況下 resize 底層數(shù)組呢?

• 數(shù)組內(nèi)存不夠用的時(shí)候

insert、append、extend、切片賦值，這些操作都有可能需要分配更多的內(nèi)存。

• 數(shù)組內(nèi)存冗余的時(shí)候

pop、remove 可能需要縮減數(shù)組的空間，避免浪費(fèi)。

看起來(lái)，凡是修改 list 元素?cái)?shù)目的操作都有可能導(dǎo)致 resize 的發(fā)生。這些操作函數(shù)(定義在 listobject.c 中)確實(shí)也全部調(diào)用了 list_resize() 函數(shù)。

根據(jù)上邊的 resize 算法，如果你的 list 中的元素?cái)?shù)目抖動(dòng)很大，發(fā)生 resize 的概率就大很多。

因此，我們?cè)陂_(kāi)發(fā)中應(yīng)盡量避免頻繁大幅度增減 list 元素的情況，以提升程序的運(yùn)行效率。

本文轉(zhuǎn)載自微信公眾號(hào)「python學(xué)與思」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系python學(xué)與思公眾號(hào)。