【列表 resize 的实现算法】

那么，变长数组是使用什么算法来调整其大小呢?

这个逻辑是在 list_resize() 函数中实现的。先看代码。

1. static int 
2. list_resize(PyListObject *self, Py_ssize_t newsize) 
3. { 
4.     PyObject **items; 
5.     size_t new_allocated, num_allocated_bytes; 
6.     Py_ssize_t allocated = self->allocated; 
7.  
8.     /*Step 1*/ 
9.     if (allocated >= newsize && newsize >= (allocated >> 1)) { 
10.         assert(self->ob_item != NULL || newsize == 0); 
11.         Py_SET_SIZE(self, newsize); 
12.         return 0; 
13.     } 
14.  
15.     /*Step 2*/ 
16.     new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3; 
17.     /* Do not overallocate if the new size is closer to overalocated size 
18.      * than to the old size. 
19.      */ 
20.     if (newsize – Py_SIZE(self) > (Py_ssize_t)(new_allocated – newsize)) 
21.         new_allocated = ((size_t)newsize + 3) & ~(size_t)3; 
22.  
23.     if (newsize == 0) 
24.         new_allocated = 0; 
25.          
26.     /*Step 3*/ 
27.     num_allocated_bytes = new_allocated * sizeof(PyObject *); 
28.     items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes); 
29.     if (items == NULL) { 
30.         PyErr_NoMemory(); 
31.         return -1; 
32.     } 
33.      
34.     /*Step 4*/ 
35.     self->ob_item = items; 
36.     Py_SET_SIZE(self, newsize); 
37.     self->allocated = new_allocated; 
38.     return 0; 
39. } 

list_resize() 的处理逻辑为：

1. 先判断原 list 对象已分配的空间是否满足新需求：大于 newsize，且不超过 newsize 的两倍(超过 newsize 两倍时，需要缩短已分配空间)。满足，则无需再调整。
2. 计算新数组的需要容纳的元素的数目：new_allocated。这个算法有点难理解：它会额外分配一些内存，并将这块内存以 4 的倍数进行对齐。可以不用去细究为什么要这样计算。
3. 计算需要重新分配的内存大小：num_allocated_bytes。
4. 调用 PyMem_Realloc() 分配内存。

更新 self 指向对象的相关属性：调整变长数组指针的指向，设置 list 中元素的个数，设置已分配空间的大小。

【哪些操作会导致列表 resize?】

我们已经了解了 resize 的执行逻辑。那么 list 会在什么情况下 resize 底层数组呢?

• 数组内存不够用的时候

insert、append、extend、切片赋值，这些操作都有可能需要分配更多的内存。

• 数组内存冗余的时候

pop、remove 可能需要缩减数组的空间，避免浪费。

看起来，凡是修改 list 元素数目的操作都有可能导致 resize 的发生。这些操作函数(定义在 listobject.c 中)确实也全部调用了 list_resize() 函数。

根据上边的 resize 算法，如果你的 list 中的元素数目抖动很大，发生 resize 的概率就大很多。

因此，我们在开发中应尽量避免频繁大幅度增减 list 元素的情况，以提升程序的运行效率