Python列表和元組的底層實現

有關列表（list）和元組（tuple）的底層實現，本節分別從它們的原始碼來進行分析。

首先來分析 list 列表，它的具體結構如下所示：

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

有興趣的讀者，可直接閱讀 list 列表實現的原始碼檔案 listobject.h 和 listobject.c。

list 本質上是一個長度可變的連續陣列。其中 ob_item 是一個指標列表，裡邊的每一個指標都指向列表中的元素，而 allocated 則用於儲存該列表目前已被分配的空間大小。

需要注意的是，allocated 和列表的實際空間大小不同，列表實際空間大小，指的是 len(list) 返回的結果，也就是上邊程式碼中註釋中的 ob_size，表示該列表總共儲存了多少個元素。而在實際情況中，為了優化儲存結構，避免每次增加元素都要重新分配記憶體，列表預分配的空間 allocated 往往會大於 ob_size。

因此 allocated 和 ob_size 的關係是：allocated >= len(list) = ob_size >= 0。

如果當前列表分配的空間已滿（即 allocated == len(list)），則會向系統請求更大的記憶體空間，並把原來的元素全部拷貝過去。

接下來再分析元組，如下所示為 Python 3.7 tuple 元組的具體結構：

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];

    /* ob_item contains space for 'ob_size' elements.
     * Items must normally not be NULL, except during construction when
     * the tuple is not yet visible outside the function that builds it.
     */
} PyTupleObject;

有興趣的讀者，可閱讀 tuple 元組實現的原始碼檔案 tupleobject.h 和 tupleobject.c。

tuple 和 list 相似，本質也是一個陣列，但是空間大小固定。不同於一般陣列，Python 的 tuple 做了許多優化，來提昇在程式中的效率。

舉個例子，為了提高效率，避免頻繁的呼叫系統函數 free 和 malloc 向作業系統申請和釋放空間，tuple 原始檔中定義了一個 free_list： 

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];

所有申請過的，小於一定大小的元組，在釋放的時候會被放進這個 free_list 中以供下次使用。也就是說，如果以後需要再去建立同樣的 tuple，Python 就可以直接從快取中載入。