《Resize是增加列表开销的重要因素》。Python列表的底层是通过存储一个可变长度的对象指针数组来实现的。使用数组的好处是可以通过索引随机访问列表中的元素。然而，由于列表是可变数据类型，我们可以动态地添加或删除列表中的元素，当底层数组不足以容纳新元素时，必须调整其大小。这正是“可变长度”的意思。那么，list使用的变长数组是如何调整大小的呢？下面我们通过阅读Python源码来做一个简单的分析。【List初始内存分配机制】我们先来了解下创建List时，List的底层数组是什么样子的。list__init__()是一个创建列表对象的接口函数。它调用list___init___impl(self,iterable)。list___init___impl接受一个可迭代对象作为初始化源。这与我们通常初始化列表对象的方式是一致的。list___init__impl做了哪些初始化工作？list__init___impl()首先清除入参self指向的对象。原因是：Python维护了一个free_list对象池来提高创建list对象的效率。它可以回收不再使用的列表对象，并将它们重新分配给新的列表对象。/*Emptylistreuseschemetosavecallstomallocandfree*/#ifndefPyList_MAXFREELIST#definePyList_MAXFREELIST80#endifstaticPyListObject*free_list[PyList_MAXFREELIST];staticintnumfree=0;这个list内存池的大小是80，如果self指向缓冲池中的对象，需要先清理。然后list___init___impl()调用list_preallocate_exact()为self的变长数组分配一块内存，这个数组的元素个数与iterable的元素个数相同。这样，列表对象使用的变长数组就创建好了。【Listresize实现算法】那么，变长数组的大小调整是用什么算法实现的呢？该逻辑在list_resize()函数中实现。先看代码。staticintlist_resize(PyListObject*self,Py_ssize_tnewsize){PyObject**items;size_tnew_allocated,num_allocated_bytes;Py_ssize_tallocated=self->allocated;/*Step1*/if(allocated>=newsize&&newsize>=(allocated>>1)){assert(self->ob_item!=NULL||newsize==0);Py_SET_SIZE(self,newsize);return0;}/*Step2*/new_allocated=((size_t)newsize+(newsize>>3)+6)&~(size_t)3;/*Donotoverallocateifthenewsizeisclosertooverallocatedsize*thantotheoldsize.*/if(newsize-Py_SIZE(self)>(Py_ssize_t)(new_allocated-newsize))new_allocate=((size_t)newsize+3)&~(size_t)3;if(newsize==0)new_allocated=0;/*Step3*/num_allocated_bytes=new_allocated*sizeof(PyObject*);items=(PyObject**)PyMem_Realloc(self->ob_item,num_allocated_bytes);if(items==NULL){PyErr_NoMemory();返回-1;}/*Step4*/self->ob_item=items;Py_SET_SIZE(self,newsize);self->allocated=new_allocated;return0;}list_resize()的处理逻辑是：先判断原来分配的空间list对象是否满足新要求：大于newsize，不满足超过newsize的两倍（超过当newsize增加一倍时，需要缩短分配的空间），不需要进一步调整。计算新数组需要容纳的元素个数：new_allocated。该算法理解起来有点棘手：它分配了一些额外的内存并将其按4的倍数对齐。您无需深究为什么需要这样计算。计算需要重新分配的内存大小：num_allocated_bytes。调用PyMem_Realloc()分配内存。更新self指向的对象的相关属性：调整变长数组指针的指向，设置链表的元素个数，设置分配空间的大小。【哪些操作会导致list发生resize？】我们已经了解了resize的执行逻辑。那么list在什么情况下会调整底层数组的大小呢？当数组内存不够时，insert、append、extend、slice赋值，这些操作可能需要分配更多的内存。当数组内存冗余时，pop和remove可能需要减少数组的空间，避免浪费。似乎任何修改列表元素数量的操作都可能导致resize发生。这些操作函数（定义在listobject.c中）确实都调用了list_resize()函数。根据上面的resize算法，如果你的列表中的元素个数波动很大，那么resize的概率就会高很多。因此，我们在开发中应尽量避免列表元素的频繁、大幅度的增减，以提高程序的运行效率。本文转载自微信公众号《Python学习与思考》，可通过以下二维码关注。转载本文请联系python学习与思考公众号。
