[[387994]]

“ resize 是增加列表開銷的重要因素。”

Python 列表底層是通過存儲對象指針的變長數(shù)組來實(shí)現(xiàn)的，使用數(shù)組帶來的好處就是可以通過索引隨機(jī)訪問列表中的元素。

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

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

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

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

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

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

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

/* 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; 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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