python 内置了dict list等
Python中的的PyListObject是对列表的一个抽象,内置了插入、添加、删除等操作。不同List中存储的元素的个数会是不同的,所以PyListObject是一个变长对象。而PyListObject中支持插入删除等操作,可以在运行时动态地调整其所维护的内存和元素,所以它又是一个可变对象。
我们知道,用户选用list正是为了可以频繁的执行插入或删除等操作,如果是需要存多少就申请多大的内存,这种内存管理显然是低效的。那么Python内部是怎么实现的呢?这就与刚才所提到的allocated有关了,我们知道,在PyObject_VAE_HEAD中有一个ob_size,在PyListObject中,每一次需要申请内存时,总会申请一大块内存存,这时申请的总内存的大小记录记录在allocated中,而其中实际被使用了的内存的数量则记录在ob_size中。
在列表对象的实现文件listObject.c文件中,我们可以看到,Python对于创建一个列表,提供了唯一的一条途径,就是PyList_New()
1 |
|
首先,进行溢出检查。接下来,就是List对象的创建了,Python中的list对象实际上是分为两部分的,一是PyListObject对象本身,二是PyListObject对象维护的元素列表,而这两块内存是通过ob_item建立联系的。
在创建PyListObject对象时,首先检查缓冲池中free_list是否有可用的对象,如果有,则直接使用,若没有可用对象,则通过PyObject_GC_New在系统堆中申请内存,
1 |
|
在创建PyListObject对象时,会首先检查缓冲区中的free_lists中是否有可用的对象。
在创建一个新的的对象时,实际也是分为两部,首先创建PyListObject对象,然后创建PyListObject对象所维护的元素列表,与之对应,在销毁一个list时,销毁的过程也是分离的,首先销毁PyListObject所维护的元素列表,然后释放PyListObject对象自身。。
在删除PylsitObject对象自身时,Python会先检查我们开始提到的那个缓冲池free_list,查看其中缓存的PyListObject的数量是否已经满了,如果没有,就将待删除的PyListObject对象放到缓冲池中,以备后用。
因此,那个在Python启动时空荡荡的缓冲池原来都是被本应该死去的PyListObject对象给填充了,在以后需要创建新的PyListObject的时候,Python会首先唤醒这些对象,重新分配Pyobject*元素列表占用的内存,重新拥抱新的对象。
insert 追加元素性能极差 谨慎使用
append 常数级别
pop 从头部弹出也需要挪动整个列表
pop 从尾部弹出元素 常数级别
list 对象可以根据元素个数进行自动扩容
内部结构在头文件 include/listobject.h 当中
变长对象 包含变长对象公共头部 内部维护了一个动态数组
尾部增删可以快速完成 无需挪动其他元素
如果list对象内部数组已经用满 再添加元素的时候 需要进行扩容
由于内部数组扩容时,需要将列表元素从旧数组拷贝到新数组,时间复杂度为 O(N),开销较大,需要尽量避免。为此, Python 在为内部数组扩容时,会预留一定裕量,一般是
1/8 左右。假设为长度为 1000 的列表对象扩容, Python 会预留大约 125 个空闲位置,分配一个长度 1125 的新数组。 也就是基数上增加0.125
由于扩容操作的存在, append 方法最坏情况下时间复杂度为
O(n) 。由于扩容操作不会频繁发生,将扩容操作时的元素拷贝开销平摊到多个 append 操作中,平均时间复杂度还是 O(1) 。
拷贝
浅拷贝 只是对列表对象进行浅拷贝 对信列表可变元素的修改对旧列表依然可见
拷贝的是元素对象的指针