# list

# 内部结构

list在的PyVarObject结构体的基础上增加了指向动态数组的指针ob_item和动态数组已分配长度即列表容量allocated两个字段，同时使用PyVarObject结构体中的ob_size字段保存列表长度。

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行为

# 动态扩缩容机制

当list对象内部数组已经用满，则需要创建一个更长的数组并将原数组复制过去，复制过程时间复杂度为O(n)-扩缩容由list_resize函数实现，需要尽量避免。
为了避免频繁扩容，Python每次会为内部数组预留一定容量-即容量大于等于长度。一般这个裕量为1/8的当前长度再加上3(<9)或6(>=9)的裕量，即为1000长度的列表扩容，则会分配一个长度为1125+6的新数组。
- 因为小于9时n*1/8=0，这会导致当list对象从0开始增长时需要频繁扩容，加上了3或6的裕量则可以使得列表容量按照 0、4、8、 16、25、35、46、58、72、88…… 这样的序列进行扩张。这样一来，当 list 对象长度较小时，容量翻倍扩展，扩容频率得到有效限制。
- 注意缩容可能有一个容量下限，比如4。因为这个容量再缩一半也就是省下两个指针的空间而已，意义不大。倒不如不缩，这样也避免了连续append/pop导致的来回扩容缩容。
由于扩容操作的存在，append方法最坏情况下时间复杂度为O(n)，但也由于扩容操作不会频繁发生，这个元素拷贝的开销会平摊到多个append操作中，因此实际时间复杂度还是O(1)。
扩缩容条件
- 扩容：新长度大于底层数组长度
- 缩容：新长度小于底层数组长度的一半

//cpython-v3.7.4\Objects\listobject.c
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;	// 旧数组容量

    /* 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, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

‍

# 头部操作

基于C语言中数组的特性，对于列表头部进行，无论是插入元素还是抛出元素，操作时间复杂度都会为o(n)。
- 当需要频繁操作头部时，考虑使用标准库中的deque。
```
from collections import deque

q = deque()
# enqueue
q.append(job)
# dequeue
q.popleft()
```
insert 方法在 Python 内部由 C 函数 list_insert_impl实现，而 list_insert_impl则调用 ins1函数完成元素插入

// cpython-v3.7.4\Modules\arraymodule.c
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self); // 取出列表长度
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {	// 判断当前是否以及达到最大限制
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) < 0) // 必要时扩容
        return -1;

    if (where < 0) {	// 检查插入位置下标，如果为负数则转换为正数
        where += n;
        if (where < 0)	// 检查下标是否越界
            where = 0;
    }
    if (where > n)	// 检查下标是否越界
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )	// 从末尾开始所有元素逐一向后移动一个位置
        items[i+1] = items[i];
    Py_INCREF(v);	// 自增元素对象引用计数
    items[where] = v;	// 将元素对象指针保存到列表指定位置
    return 0;
}

‍

# 尾部追加

append方法在 Python 内部由 C 函数 list_append实现，而 list_append进一步调用 app1函数完成元素追加

//cpython-v3.7.4\Objects\listobject.c
static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self); // 根据PyVarObject 结构体中的ob_size字段取出容器长度

    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {		// 如果当前长度以及达到最大限制则报错
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) < 0)	// 如果扩容失败（需要扩容的话）
        return -1;

    Py_INCREF(v);			// 自增元素对象引用计数
    PyList_SET_ITEM(self, n, v);	// 将元素对象指针保存到列表最后一个位置，列表新长度为 n+1 ，最后一个位置下标为 n 。
    return 0;
}

# 抛出元素

pop 方法将指定下标的元素从列表中弹出，下标默认为 -1 ，pop 方法在 Python 内部由 C 函数 list_pop_impl实现
如果抛出元素不是最后一个则会调用list_ass_slice函数，其根据函数参数决定执行逻辑：
- 删除语义 ，如果最后一个参数 v 值为 NULL ，执行删除语义，即：del a[ilow:ihigh] ；
- 替换语义 ，如果最后一个参数 v 值不为 NULL ，执行替换语义，即 a[ilow:ihigh] = v 。
```
/* a[ilow:ihigh] = v if v != NULL.
 * del a[ilow:ihigh] if v == NULL.
 *
 * Special speed gimmick:  when v is NULL and ihigh - ilow <= 8, it's
 * guaranteed the call cannot fail.
 */
static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v);
```
因此执行抛出操作时，时间复杂度最优（尾部弹出）是O(1)，最差时间复杂度（头部弹出），因此平均时间复杂度为O(n/2)，即O(n)。

// cpython-v3.7.4\Objects\listobject.c
static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
{
    PyObject *v;
    int status;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (index < 0)		// 检查插入位置下标，如果为负数则转换为正数
        index += Py_SIZE(self);
    if (index < 0 || index >= Py_SIZE(self)) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    v = self->ob_item[index];	// 从底层数组取出待弹出元素
    if (index == Py_SIZE(self) - 1) {	// 如果抛出的是最后一个元素则只需要调整长度而不需要做元素移动
        status = list_resize(self, Py_SIZE(self) - 1);	// 进行可能的动态扩缩容
        if (status >= 0)
            return v; /* and v now owns the reference the list had */
        else
            return NULL;
    }
    Py_INCREF(v);	// 自增元素对象引用计数
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL); // 删除[index,index+1)中的元素
    if (status < 0) {
        Py_DECREF(v); 
        return NULL;
    }
    return v;
}

‍

# 删除元素

与pop传入索引不同，remove方法直接给定待删除元素，在 Python 内部由 C 函数 list_remove实现

// cpython-v3.7.4\Objects\listobject.c
static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

‍

# 浅拷贝

总结：①赋值引用，两个变量名指向同一个列表，通过任意变量名对列表做出的修改都能被另一个变量所看见，因为修改的是同一个列表，这是你说的情况；②浅拷贝，两个变量已经指向不同的列表，但列表均保存相同的元素对象，这时对列表直接进行修改不影响另一个列表，但列表可变元素的修改，对另一列表可见；③深拷贝，两个变量同样指向不同的列表，同时列表元素也指向不同的对象，虽然对象是相等的，这时两个列表就完全独立了。
调用list对象copy方法，将获得list对象的一份浅拷贝。
- 即如果内部由可变元素实际上只是拷贝一份指针过去。
可以利用标准库copy中的deepcopy函数进行深拷贝。
```
from copy import deepcopy
l2 = deepcopy(l1)
```

‍

# 优化

# 预分配机制

#TODO#

‍

# QA

# 为什么list一直有触发扩容但id不变

答案是：obitem是一个指针

import random

lst = []
st = set()
SIZE = random.randint(100, 1000000)
print(f'SIZE:{SIZE}')
for i in range(SIZE):
    if id(lst) not in st and st:
        print(f'id(l):{id(lst)} changed')
    st.add(id(lst))
    lst.append(i)
# print(lst)

← int str →