摘要：前言的列表是一個(gè)非常靈活的數(shù)組，可以隨意調(diào)整長(zhǎng)度。所以可以猜測(cè)這塊應(yīng)該是沒有這樣的一個(gè)預(yù)分配內(nèi)存池。比方說上面的觸發(fā)時(shí)，是，而不是這邊比較重要，因?yàn)樵谶@類減少列表成員時(shí)候，就是傳入縮減后的總數(shù)目。

Python 的列表（list）是一個(gè)非常靈活的數(shù)組，可以隨意調(diào)整長(zhǎng)度。正是因?yàn)檫@種便利，使得我們會(huì)情不自禁地去修改數(shù)組以滿足我們的需求，其中相比于insert, pop 等等而言， append 用法更常見。

有像這樣使用：

>>> test = []
>>> test.append(1)
>>> test.append({2})
>>> test.append([3])
>>> print test

# 輸出 
[1, set([2]), [3]]

也有像這樣使用的：

test = []

for i in range(4):
    test.append(i)
print test

# 輸出 
[0, 1, 2, 3]

這樣用很開心，也很滿足。

但其實(shí)只要遇到能夠動(dòng)態(tài)修改數(shù)據(jù)長(zhǎng)度場(chǎng)景，我們都應(yīng)該馬上反應(yīng)過來一點(diǎn)，那就是內(nèi)存管理的問題。

如果運(yùn)行效率和便捷性同時(shí)滿足的話，那簡(jiǎn)直就是大大的福音呀。

然而，上帝為你開啟一扇窗的同時(shí)肯定也已經(jīng)關(guān)上了一扇門了！

深受預(yù)分配知識(shí)的熏陶，我們也是覺得 list 在初始化是有分配一定的長(zhǎng)度的，要不然每次都申請(qǐng)內(nèi)存那得多 ”low“ 啊。

然后實(shí)際上 list 真的就是這么 ”low“:

import sys

test = []
test_1 = [1]
print sys.getsizeof(test)
print sys.getsizeof(test_1) - sys.getsizeof(test)

# 輸出 
72     # 空列表內(nèi)存大小，也是 list 對(duì)象的總大小
8       # 代表增加一個(gè)成員，list 增加的大小 ( 此大小為對(duì)象指針的長(zhǎng)度 )

我們的猜測(cè)是，list 在定義之后，會(huì)預(yù)先分配好一個(gè)一定大小的池用來塞數(shù)據(jù)，以避免動(dòng)不動(dòng)就申請(qǐng)內(nèi)存。

但是在上面的實(shí)驗(yàn)看出，一個(gè)成員的列表，比一個(gè)空列表，長(zhǎng)度僅僅只是大了 8 字節(jié)（對(duì)象指針的大小），如果真的存在這樣一個(gè)預(yù)分配的池，那么在預(yù)分配個(gè)數(shù)之內(nèi)添加成員，兩者的內(nèi)存大小應(yīng)該是保持不變才對(duì)。

所以可以猜測(cè)這塊 list 應(yīng)該是沒有這樣的一個(gè)預(yù)分配內(nèi)存池。這里需要來個(gè)實(shí)錘

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
        
    // list對(duì)象指針的緩存
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    
    // list 成員的內(nèi)存申請(qǐng)
    nbytes = size * sizeof(PyObject *);
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

當(dāng)我們?cè)趫?zhí)行 test = [1] 時(shí)，實(shí)際上只做了兩件事：

根據(jù)成員的數(shù)目，構(gòu)建相應(yīng)長(zhǎng)度的空列表；(上述代碼)

一個(gè)個(gè)將這些成員塞進(jìn)去；

可能有童鞋會(huì)覺得，在塞成員的那一步，說不定會(huì)觸發(fā)什么機(jī)制使它變大？

很可惜，因?yàn)槌跏蓟玫姆椒ㄊ?PyList_SET_ITEM, 所以這里是木有的觸發(fā)什么機(jī)制，只是簡(jiǎn)單的數(shù)組成員賦值而已：

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

所以整個(gè) list 的初始化，還真的就是木有預(yù)分配的內(nèi)存池，直接按需申請(qǐng)，一個(gè)蘿卜一個(gè)坑，實(shí)在得狠；

初始化過程是這樣還可以理解，如果運(yùn)行中還這樣的話，那就有點(diǎn)說不過去了。

試想下，在文章開頭用 append 的例子中，如果每 append 一個(gè)元素就申請(qǐng)一次內(nèi)存，那么list 可能要被吐槽到懷疑人生了, 所以很明顯，在對(duì)于內(nèi)存的申請(qǐng)，它還是有自己的套路的。

在 list 里面，不管是 insert 、pop 還是 append，都會(huì)遇到 list_resize，故名思義，這個(gè)函數(shù)就是用來調(diào)整 list 對(duì)象的內(nèi)存占用的。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    # 確定新擴(kuò)展之后的占坑數(shù)
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;

    # 申請(qǐng)內(nèi)存
    items = self->ob_item;
    if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

在上面的代碼中，頻繁看到兩個(gè)名詞：newsize 和 new_allocated, 這里需要解釋下，newsize 并不是 增加/減少 的個(gè)數(shù)，而是 增加/減少 之后的成員總數(shù)目。比方說：

a = [1, 2, 3]
a.append(1)

上面的 append 觸發(fā)list_resize 時(shí)， newsize 是 3 + 1， 而不是 1；這邊比較重要，因?yàn)樵?pop 這類減少列表成員時(shí)候，就是傳入縮減后的總數(shù)目。

在 list 的結(jié)構(gòu)定義中，關(guān)于長(zhǎng)度的定義有兩個(gè)，分別是 ob_size(實(shí)際的成員數(shù))，allocated(總成員數(shù))

它們之間的關(guān)系就是：

 0 <= ob_size <= allocated
 len(list) == ob_size

所以 new_allocated 就很好理解了，這個(gè)就是新的總坑數(shù)。

當(dāng)名詞含義理解得差不多時(shí)，我們就能順藤摸瓜知道一個(gè)列表在list_resize 之后，大小會(huì)變成怎樣？

方法其實(shí)從上面注釋和代碼都說得很明白了，這里再簡(jiǎn)單整理下：

先確定一個(gè)基數(shù)：new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

判斷下 new_allocated + newsize 有沒有超過 PY_SIZE_MAX, 如果超過了，直接報(bào)錯(cuò)；

最終確定新的總坑數(shù)是：new_allocated + newsize， 如果 newsize 是 0, 那么總坑數(shù)直接為 0 ；

下面演示下：

#coding: utf8
import sys

test = []
raw_size = sys.getsizeof(test)

test.append(1)
print "1 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "2 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "3 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "4 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "5 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "6 次 append 減去空列表的內(nèi)存大小：%s " % (sys.getsizeof(test) - raw_size)

# 輸出結(jié)果
1 次 append 減去空列表的內(nèi)存大小：32
2 次 append 減去空列表的內(nèi)存大小：32
3 次 append 減去空列表的內(nèi)存大小：32
4 次 append 減去空列表的內(nèi)存大小：32
5 次 append 減去空列表的內(nèi)存大小：64
6 次 append 減去空列表的內(nèi)存大小：64

開始簡(jiǎn)單的代入法一步步算：

其中：

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize （因?yàn)橄旅娴?newsize > 0）

當(dāng)原allocated >= newsize 并且 newsize >= 原allocated / 2 時(shí)，不改變 allocated 不申請(qǐng)內(nèi)存直接返回

通過上面的表格，應(yīng)該比較清楚看到什么時(shí)候會(huì)觸發(fā)改變 allocated，并且當(dāng)觸發(fā)時(shí)它們是如何計(jì)算的。為什么我們需要這樣關(guān)注 allocated？理由很簡(jiǎn)單，因?yàn)檫@個(gè)值決定了整個(gè) list 的動(dòng)態(tài)內(nèi)存的占用大小；

擴(kuò)容是這樣，縮容也是照貓畫虎。反正都是算出新的 allocated， 然后由 PyMem_RESIZE 來處理。

#define PyMem_REALLOC(p, n)    ((size_t)(n) > (size_t)PY_SSIZE_T_MAX  ? NULL 
                : realloc((p), (n) ? (n) : 1))

#define PyMem_RESIZE(p, type, n) 
  ( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL :    
    (type *) PyMem_REALLOC((p), (n) * sizeof(type)) 

基本上，就是判斷是否超過最大數(shù)，否則的話就是和C realloc函數(shù)近似了，以下摘抄了一段關(guān)于C realloc函數(shù)的描述：

綜上所述，在一些明確列表成員或者簡(jiǎn)單處理再塞入列表的情況下，我們不應(yīng)該再用下面的方式：

test = []

for i in xrange(4):
    test.append(i)
print test

而是應(yīng)該用列表推導(dǎo)式：test = [i for i in xrange(4)]。

為什么推薦列表推導(dǎo)呢？顯而易見的效果就有：

簡(jiǎn)練、清晰；

用多少就申請(qǐng)多少，不會(huì)因?yàn)?append 觸發(fā) PyMem_RESIZE 申請(qǐng)過多內(nèi)存；容易造成內(nèi)存浪費(fèi)；

相比 for i in xxx，列表推導(dǎo)方式直接增加元素，少了一些函數(shù)調(diào)用，如：SETUP_LOOP、CALL_FUNCTION 等；

但是上面的推薦肯定也是在某些前提條件下才合適咯：

真的只是為了得到一個(gè)列表；

循環(huán)體內(nèi)邏輯簡(jiǎn)單，沒有太復(fù)雜的處理、判斷、調(diào)用等等；

PS： 切記勿為了使用列表推導(dǎo)而使用，合理使用才是科學(xué)之道；

歡迎各位大神指點(diǎn)交流, QQ討論群: 258498217
轉(zhuǎn)載請(qǐng)注明來源: https://segmentfault.com/a/11...