营销网站设计包括,网站费用多少,如何自己做一个订单管理系统,建设网站需要学什么程序4.0 序python中的list对象#xff0c;底层对应的则是PyListObject。如果你熟悉C#xff0c;那么会很容易和C中的list联系起来。但实际上#xff0c;这个C中的list大相径庭#xff0c;反而和STL中的vector比较类似4.1 PyListObject对象我们知道python里面的list对象是支持对…4.0 序python中的list对象底层对应的则是PyListObject。如果你熟悉C那么会很容易和C中的list联系起来。但实际上这个C中的list大相径庭反而和STL中的vector比较类似4.1 PyListObject对象我们知道python里面的list对象是支持对元素进行增删改查等操作的list对象里面存储的底层无一例外都是PyObject * 指针。所以实际上我们可以这样看待python底层的PyListObjectvector。根据我们使用python的list的经验我们可以得出以下两个结论。每个PyListObject维护的元素个数可以不一样所以这是一个变长对象可以对PyListObject维护的元素进行添加、删除等操作所以这是一个可变对象我们来看一下PyListObject对象的定义。typedef struct {//不用解释PyObject加上一个ob_sizePyObject_VAR_HEAD/* ob_item就对应list对象存储的元素ob_item[0]就是list[0]但是我们发现这是一个二级指针至于这里的二级指针是如何和python中list挂上钩的我们后面会详细介绍*/PyObject **ob_item;/*这个allocated是什么呢?其实我在最开始的那一章介绍python源码的时候就已经解释过了。这里再来说一遍我们知道PyObject_VAR_HEAD里面有一个ob_size这是表示变长对象里面已经存储了多少个元素了。而这个allocated则表示最大能存储多少个元素因为这是一个变长对象因此就意味着可以随时对其进行删除、增加等操作如果每次添加都要malloc那么效率会非常低下因此python会事先申请一大份内存而allocated正是记录了这个一大份内存的容量是多少。而ob_size则是目前已经存了多少个如果你学过golang你会发现ob_size对应golang里面切片的len而allocated则对应cap。假设一个能容纳10个元素的PyListObject对象已经存了5个元素那么ob_size就是5allocated就是10。从这里我们已经能够看出0 ob_size allocatedlen(list) ob_size 注意这里的list指的都是list的实例对象而不是list这个类本身ob_item NULL 意味着 ob_size allocated 0*/Py_ssize_t allocated;} PyListObject;刚才说了python事先会申请一大份内存这个并不是指在创建的时候申请一大份内存而是在扩容的时候会申请更多的内存。PyListObject有一个resize操作不用想这个肯定是修改列表容量的。因为allocated一开始是固定的但是随着ob_size越来越大肯定要申请更多的内存即增大allocatedstatic intlist_resize(PyListObject *self, Py_ssize_t newsize){//参数self就是PyListObject *对象本身//参数newsize就是当前的ob_sizePyObject **items;//既然resize所以new_allocated就是新的最大容量size_t new_allocated, num_allocated_bytes;//这里的获取当前PyListObject的allocatedPy_ssize_t allocated self-allocated;//如果当前的容量大于newsize(ob_size)并且newsize 容量除以2//基本上啥也没干直接返回这一步不需要关心。//因为执行这一步表示内存不需要重新分配if (allocated newsize newsize (allocated 1)) {assert(self-ob_item ! NULL || newsize 0);Py_SIZE(self) newsize;return 0;}/*计算重新分配的内存的大小这一步很重要新分配的容量就等于newsize newsize 3 3 if newsize 9 else 6*/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;}//如果新的ob_size是0那么新分配的容量也是0if (newsize 0)new_allocated 0;//所占的字节就是new_allocated * sizeof(PyObject *)//但是我们发现这里乘上的是一个指针的大小这是一个很关键的问题我们后面会详谈num_allocated_bytes new_allocated * sizeof(PyObject *);//为ob_item申请内存items (PyObject **)PyMem_Realloc(self-ob_item, num_allocated_bytes);if (items NULL) {PyErr_NoMemory();return -1;}//指向新的内存块扩展列表。self-ob_item items;//将ob_size变为newsizePy_SIZE(self) newsize;//将allocated变为新的new_allocatedself-allocated new_allocated;return 0;}我们来刚才说python中的list申请容量是按照new_allocated (size_t)newsize (newsize 3) (newsize 9 ? 3 : 6)这样的规则来的我们来看看。allocated 0print(allocated, end )for size in range(100):if allocated size:allocated size (size 3) (3 if size 9 else 6)print(allocated, end ) # 0 4 8 16 25 35 46 58 72 88 106我们具体来计算一下。l []allocated 0print(allocated, end )for _ in range(100):l.append(_)if len(l) allocated:# 从变量名也能看出这获取的是容量但是为什么要除以8呢# 因为[]里面的每一个元素占8个字节啊咦那列表里面存xx * 1000这也占8个字节# 没错是的关于为什么我们会后面说。# 同时这也引出了一个问题为什么python中list对象在支持存储不同类型数据的前提下还能保证查询的时间复杂度是O(1)呢# 先保留这些疑问后面会解答allocated (l.__sizeof__() - [].__sizeof__()) // 8print(allocated, end ) # 0 4 8 16 25 35 46 58 72 88 106可以看到我们计算的结果和官方源码给的是一样的其实这是废话python解释器就是按照官方源码写的。但还有一个特殊情况l [1, 2, 3, 4, 5]print((l.__sizeof__() - [].__sizeof__()) // 8) # 5结果是5我们在之前的结果并没有看见5啊。这是因为对于初始化一个列表时有多少元素容量就是多少此时allocated和ob_size是相等的l.append(6)什么时候会扩容呢是当我们往列表进行append的时候解释器发现容量不够。比如此时上面的ob_size和allocated都是5但是当append一个6的时候解释器发现容量不够了ob_size已经超过allocated了于是才会扩容。按照 newsize (newsize 3) (if newsize 9 ? 3 : 6)# 此时扩容的结果就是9尽管里面只存储的了6个元素但是人家内存已经分配了# 所以计算的就是9个元素的内存那么除以8得到的就是9即分配的内存能够容纳9个元素print((l.__sizeof__() - [].__sizeof__()) // 8) # 9在这里还想问一句对于初始化一个列表你认为l []和l list()哪个速度更快呢首先这两者你print之后得到的都是一个[]答案是l []更快因为python中的list在C语言的层面可以看做是allocated-array过分配数组直接使用的是底层C语言的数据结构。而l list()相当于是python层面上的一个函数调用既然调用肯定要创建栈帧、记录函数参数等等会进行额外的资源消耗。为什么list通过索引查找元素的时间复杂度是O(1)我们之前说了其实不说大家也知道python里面列表通过索引定位元素的时间复杂度是O(1)可是列表里面存放的元素大小不一是怎么做到的呢还记的我们之前说列表里面存储的元素都占8个字节吗我们再来验证一下。import sysl [a * 1000, b * 1000]print(sys.getsizeof(l) - sys.getsizeof([])) # 16print(sys.getsizeof(l[0]) - sys.getsizeof()) # 1000由于python中的对象除了值本身还有其他的信息比如引用计数、ob_size等等这些都是要占内存的。我们把这些值减掉比如列表的话减去一个[]字符串减去一个把共同具有的那些特征那么所占的内存去掉那么剩下来的就是值本身占的内存可以看到加上本身的信息l[0]占了不止1000个字节同理l[1]也是但是我们计算列表的时候发现里面的值只占了16个字节说明每一个值占了8个字节。其实任何一个对象存在列表里面都是8个字节而我们看PyListObject的定义里面有一个PyObject **ob_item因此很容易猜到python的list里面存储的实际上是指针。其实这个ob_item是一个指向指针数组的指针这个指针指向了指针数组的首地址。因此我们可以看到python的list、tuple实际是哪个都是采用了元素外置的方法元素的实际的值都存储在堆上至于列表本身存储的不过是这些元素的内存指针。不管你值本身占的内存有多大但是内存地址是固定的在64位机器上是8个字节。通过索引可以瞬间计算出指针的偏移量从而找到对应元素的指针打印的时候会自动打印指针所指向的内存。索引我们使用id(l[0])查看第一个元素的内存地址时会打印一串数字也就是内存地址但是实际上l[0]在python的底层中存储的就是地址。我们打印的时候打印的也是指针只不过我们没有权限操作指针能有权限操作指针的只有解释器因此当我们打印会自动打印指针的指向内存我们可以认为尽管存储的是指针但是最终操作的都是指针指向的内存。4.2 PyListObject对象的创建与维护4.2.1 创建对象为了创建一个列表python底层只提供了唯一的一条途径--PyList_New。这个函数接收一个size参数从而允许我们在创建一个PyListObject对象时指定元素个数。这里仅仅是指定了元素个数却没有指定元素是什么我们来看看创建PyListObject对象的过程PyObject *PyList_New(Py_ssize_t size){//声明一个PyListObject *对象PyListObject *op;#ifdef SHOW_ALLOC_COUNTstatic int initialized 0;if (!initialized) {Py_AtExit(show_alloc);initialized 1;}#endif//如果size小于0直接抛异常if (size 0) {PyErr_BadInternalCall();return NULL;}//缓冲池是否可用如果可用if (numfree) {//直接使用缓冲池的空间numfree--;op free_list[numfree];_Py_NewReference((PyObject *)op);#ifdef SHOW_ALLOC_COUNTcount_reuse;#endif} else {//不可用的时候申请内存op PyObject_GC_New(PyListObject, PyList_Type);if (op NULL)return NULL;#ifdef SHOW_ALLOC_COUNTcount_alloc;#endif}//如果size小于0ob_item设置为NULLif (size 0)op-ob_item NULL;else {//否则的话为维护的列表申请空间op-ob_item (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));if (op-ob_item NULL) {Py_DECREF(op);return PyErr_NoMemory();}}//设置ob_size和allocated然后返回opPy_SIZE(op) size;op-allocated size;_PyObject_GC_TRACK(op);return (PyObject *) op;}通过源码我们可以看到python在创建列表的时候底层实际上是分为两部分的一部分是创建PyListObject对象另一部分是PyListObject对象所维护的列表这是两块分离的内存它们通过ob_item建立了联系。咦有人会问维护的列表不是PyListObject结构体的一个属性吗是的在这里PyListObject指的是不包含其维护列表的PyListObject当然有时我们也用PyListObject专门只指其维护的列表、或者我们有时也说PyListObject所维护的列表等等这些说法不用刻意区分通过上下文是可以理解的。我们注意到源码里面有一个缓冲池是的创建PyListObject对象时会先检测缓冲池free_lists里面是否有可用的对象有的话直接拿来用否则通过malloc在系统堆上申请。缓冲池中最多维护80个PyListObject对象。/* Empty list reuse scheme to save calls to malloc and free */#ifndef PyList_MAXFREELIST#define PyList_MAXFREELIST 80#endifstatic PyListObject *free_list[PyList_MAXFREELIST];static voidlist_dealloc(PyListObject *op){Py_ssize_t i;PyObject_GC_UnTrack(op);Py_TRASHCAN_SAFE_BEGIN(op)if (op-ob_item ! NULL) {/* Do it backwards, for Christian Tismer.Theres a simple test case where somehow this reducesthrashing when a *very* large list is created andimmediately deleted. */i Py_SIZE(op);//释放list中的每一个元素while (--i 0) {Py_XDECREF(op-ob_item[i]);}PyMem_FREE(op-ob_item);}//然后判断缓冲池里面PyListObject对象的个数如果没满就添加到缓冲池if (numfree PyList_MAXFREELIST PyList_CheckExact(op))free_list[numfree] op;elsePy_TYPE(op)-tp_free((PyObject *)op);Py_TRASHCAN_SAFE_END(op)}4.2.2 添加元素在第一个PyListObject创建时显然numfree是0不会走缓冲池而是直接在堆上申请假设我们申请创建有6个元素的PyListObject对象那么会调用PyList_New(6)来创建PyListObject对象在对象完成之后第一个PyListObject对象就完成了。通过上图我们可以抛出一个问题。import pandas as pd# 具有6个元素的列表l [1, xx, int, {}, pd, ()]print(l.__sizeof__()) # 88print([].__sizeof__()) # 40两者相减得到48,6个元素每个指针正好8字节。我们看到元素外置、存储指针6个元素总共用了48个字节但是剩下的40个字节是哪来的。还记得吗python中的对象在底层都是一个结构体实例我们计算的可以不仅仅是维护的值还有其他的信息啊。首先从图中可以看出ob_refcnt:引用计数占八个字节、ob_typePyTypeObject对象的一个指针八个字节、ob_size容纳元素的个数八个字节、ob_item这是一个二级指针指向了指针数组的指针八个字节、allocated容量八个字节正好40个字节再加上ob_item指向的指针数组里面有6和元素再加上6*848正好88个字节。然后我们看看PyListObject对象是如何设置元素的。intPyList_SetItem(PyObject *op, Py_ssize_t i,PyObject *newitem){//参数为PyObject *、索引、值//一个二级指针PyObject **p;//类型检查if (!PyList_Check(op)) {Py_XDECREF(newitem);PyErr_BadInternalCall();return -1;}//索引检查if (i 0 || i Py_SIZE(op)) {Py_XDECREF(newitem);PyErr_SetString(PyExc_IndexError,list assignment index out of range);return -1;}//ob_item表示数组的首地址//ob_item i直接获取数组中索引为i的元素的指针//当然数组里面存储的本身也是一个指针所以这里的p是一个二级指针p ((PyListObject *)op) - ob_item i;//直接将*p也就是数组中索引为i的指针(一级)指向的元素设置为newitemPy_XSETREF(*p, newitem);return 0;}假设我们设置l[2]100的话那么4.2.3 插入元素设置元素和和插入元素是不同的设置元素不会导致ob_item指向的内存发生改变而插入元素可能会导致ob_item指向的内存发生变化intPyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem){//类型检查if (!PyList_Check(op)) {PyErr_BadInternalCall();return -1;}//底层又调用ins1return ins1((PyListObject *)op, where, newitem);}static intins1(PyListObject *self, Py_ssize_t where, PyObject *v){/*参数selfPyListObject *参数where索引参数v插入的值这是一个PyObject *指针因为list里面存的都是指针*///i:后面for循环遍历用的n则是当前列表的元素个数Py_ssize_t i, n Py_SIZE(self);//指向指针数组的二级指针PyObject **items;//如果v是NULL错误的内部调用if (v NULL) {PyErr_BadInternalCall();return -1;}//列表的元素个数不可能无限增大一般当你还没创建到PY_SSIZE_T_MAX个对象时//你内存就已经玩完了但是python仍然做了检测当达到这个PY_SSIZE_T_MAX时会报出内存溢出错误if (n PY_SSIZE_T_MAX) {PyErr_SetString(PyExc_OverflowError,cannot add more objects to list);return -1;}//调整列表容量既然要inert那么就势必要多出一个元素//这个元素还没有设置进去但是先把这个坑给留出来//当然如果容量够的话是不会扩容的只有当容量不够的时候才会扩容if (list_resize(self, n1) 0)return -1;//确定插入点//这里可以看到如果where小于0那么我们就加上n也就是当前列表的元素个数//比如有6个元素那么我们where-1加上6就是5显然就是insert在最后一个索引的位置上if (where 0) {where n;//如果吃撑了写个-100加上元素的个数还是小于0if (where 0)//那么where0就在开头插入where 0;}//如果where n那么就索引为n的位置插入//可元素个数为n最大索引是n-1啊对所以此时就相当于appendif (where n)where n;//拿到原来的二级指针指向一个指针数组items self-ob_item;//然后让不断遍历把索引为i的值赋值给索引为i1既然是在where处插入//那么where之前的就不需要动了到where处就停止了for (i n; --i where; )items[i1] items[i];//增加引用计数因为它作为列表的一个元素了Py_INCREF(v);//将where处的值设置成v还记得这个v吗对没错这是一个PyObject *指针//打印的话会打印*vitems[where] v;return 0;}所以可以看到python插入数据是非常灵活的。不管你在什么位置插入都是合法的。因为它会自己调整位置在确定位置之后会将当前位置以及之后的所有元素向后挪动一个位置空出来的地方设置为插入的值。因此熟悉C的话会发现这和vector是非常类似的但是和C中的list确实大相径庭的尽管名字一样。既然插入元素那么自然少不了append直接往尾部追加元素了。这个就比较简单了就相当于insert的wheren直接将索引为n的地方设置为append的值即可。这里就不看源码了比较简单。只是如果容量够的话是不需要重新分配空间的。4.2.4 删除元素删除元素对于python的列表来说直接调用l.remove即可l [1, 1, 2, 3]l.remove(1)print(l) # [1, 2, 3]# 会自动删除第一个出现的元素那么底层是如何实现的呢static PyObject *list_remove(PyListObject *self, PyObject *value){//删除值对于底层来说就是删除数组中值对应的指针。//所以value仍然是PyObject *类型//ifor循环遍历用的Py_ssize_t i;//从0开始直到不小于ob_sizefor (i 0; i Py_SIZE(self); i) {//将指针数组里面的每一个元素和value进行比较int cmp PyObject_RichCompareBool(self-ob_item[i], value, Py_EQ);//如果cmp大于0表示元素和value匹配if (cmp 0) {//调用list_ass_slice将其删除if (list_ass_slice(self, i, i1,(PyObject *)NULL) 0)Py_RETURN_NONE;return NULL;}else if (cmp 0)return NULL;}//否则报错x不再list中。PyErr_SetString(PyExc_ValueError, list.remove(x): x not in list);return NULL;}//另外这个list_ass_slice其实起到的是替换的作用只不过也可以充当删除//从源码中可以看出把i: i1部分的元素给删了/*l [1, 2, 3, 4]l[0: 1] []print(l) # [2, 3, 4]*/既然是删除那么和insert一样。全局都会进行移动比如我把第一个元素删了那么第二个元素要顶在第一个元素的位置第n个元素要顶在第n-1个元素的位置上。4.3 PyListObject对象缓冲池还记的我们之前说的缓冲池free_lists吗是用来缓冲PyListObject对象的但是现在问题来了这些缓冲的PyListObject对象从哪里获取的呢或者说是何时创建的呢答案其实一开始就说了是在一个PyListObject对象销毁的时候创建的。static voidlist_dealloc(PyListObject *op){//遍历用的Py_ssize_t i;PyObject_GC_UnTrack(op);Py_TRASHCAN_SAFE_BEGIN(op)//改变每一个元素的引用计数//销毁PyListObject对象维护的元素列表if (op-ob_item ! NULL) {/* Do it backwards, for Christian Tismer.Theres a simple test case where somehow this reducesthrashing when a *very* large list is created andimmediately deleted. */i Py_SIZE(op);while (--i 0) {Py_XDECREF(op-ob_item[i]);}PyMem_FREE(op-ob_item);}//如果缓冲池未满那么放回到缓冲池当中if (numfree PyList_MAXFREELIST PyList_CheckExact(op))free_list[numfree] op;elsePy_TYPE(op)-tp_free((PyObject *)op);Py_TRASHCAN_SAFE_END(op)}我们知道在创建一个新的PyListObject对象时实际上是分为两步的先创建PyListObject然后创建其维护的元素列表。同理在销毁一个PyListObject对象时先销毁销毁维护的元素列表然后再释放PyListObject对象自身现在可以很清晰地明白了原本空荡荡的缓冲池其实是被已经死去的PyListObject对象填充了在以后创建新的PyListObject对象时python会首先唤醒这些死去的PyListObject对象给它们一个洗心革面、重新做人的机会。但注意的是这里的缓冲仅仅是PyListObject对象对于其维护的列表已经不再指向了引用减少那么这些元素就大难临头各自飞了或生存、或毁灭不再被对应的PyListObject的那个指针所束缚。但是为什么要这么做呢可以想一下如果继续维护的那么很可能会产生悬空指针的问题因此这些元素所占的空间必须交还给系统(前提是没有指针指向了)但是实际上是可以将PyListObject对象维护的元素列表保留的即只调整引用计数并将元素都设置为NULL但是并不释放内存空间。因此这样一来释放的内存不会交给系统堆那么再次分配的时候速度会快很多。但是这样带一个问题就是这些内存没人用也会一直占着并且只能供PyListObject对象使用因此python还是为避免消耗过多内存采取将元素列表的内存交换给了系统堆这样的做法在时间和空间上选择了空间。我们之前的PyListObject对象的示意图如果在缓冲池当中应该变成什么样子呢在下一次创建新的list对象时这个PyListObject对象将会被重新唤醒重新分配元素列表所占的内存重新拥抱新的元素列表。正如我就喜欢纸片人不停地换老婆每当出现新的动漫就会拥抱新的纸片人。
