python中几个常见的“黑盒子”之 列表list

python常见的数据类型有:字符串,布尔类型,整数,浮点数,数字,日期,列表,元祖,字典。相信前面6个大家都非常的熟悉,但是对于python的列表,元祖,字典我有时候一直在想其内部的实现是怎么样子的,它们就像一个“黑盒子”一样,下面记录一下对于“列表 list”理解过程:

其实,在最开始我一直以为python的列表是通过链表实现的,直到一天,应该说是误打误撞,当我通过交互模式创建一个列表的时候,然后通过id()函数打印出列表中每个元素的地址时,我发现它们的地址是连续的,然后推测python的列表list不是我们传统意义上面的列表(虽然这个推测应该算是误打误撞吧,真实的原因不是这个,这个每个元素地址连续也是因为正好凑巧而已,但是却引起了我的进一步探索和思考),也就是说不是通过链表实现的(因为如果是链表的话其元素地址肯定是不连续的),然后我就猜测这种内存地址连续的情况,python的列表应该是通过数组的形式进行存储实现的。

通过查看python文档:https://wiki.python.org/moin/TimeComplexity,其中记录了这么一句话:Internally, a list is represented as an array;这也进一步验证了我推测的结果。然后查看python的源码:

typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

其中记录了这么一个结构体(省略了源码中的大部分注释,有兴趣可以找到源码看一下),其中:

  ob_item是指向列表对象的指针数组;

  allocated是申请内存的槽的个数。

接着,通过源码获悉,python列表的存储形式就是以数组array的形式进行存储的,然后数组中每一个元素其实存储的是列表对象的指针。

现在我们搞明白了python列表的内部实现方式,所以进一步思考了如下问题:

1.对于列表操作,append操作肯定比insert操作效率要高:

  因为,对于数组来说,用append操作从后面追加一个元素,时间复杂度来说是常量级的,但是用insert操作进行数组的插入来说,当插入第一位或者中间某一位的时候,该元素后面的所有元素都要相应的往后面挪动一位。

2.python中列表的存储形式是数组的形式,这也突出了其和链表的很大的区别:

  a.当我们按照给定的索引值进行某一个元素的访问的话,数组的效率肯定是比链表的效率高出不少的。

     因为,对于数组来说,我们可以直接计算出目标元素在内存中的具体位置,然后直接对其访问;但是对于链表来说,我们要做的是去遍历整个链表才可以得到目标元素。

  b.但是对于插入insert操作来说,情况就和上面不同了。

     因为对于链表来说,我们只要知道在哪里执行insert插入操作就可以了,无论该列表中含有多少元素,操作时间都基本是相同的,造作的成本非常低;但是对于数组就不同了,每次执行插入操作的时候,都需要移动插入点右边的所有元素。甚至有时候,因为插入的元素过多,开始分配的内存空间不够,还需要把这个列表元素整体搬到一个更大的数组中(这是我开始的猜测)。当然,对于这种情况,python的开发者早就想好了对应的方法,就是append操作通常会采用一种动态数组或向量的特定解决方案:

       将内存分配得过大一些,并且等到其要溢出时,在线性时间内再次重新分配内存。

  但是,这样似乎还是我上面猜测的那样,不是会让append和insert一样糟糕么,其实不是这样子的,因为就算这俩种情况都有可能去搬动大量的元素,但最主要的不同是:对于append操作,发生的可能性要小非常多,事实上,我们能够确保每次搬入的数组都大于原数组一定的比例,那么该操作的平均成本(每次搬动的开销平均分摊到每次append操作中去),这样的时间复杂度通常是常量级别的。这里也从而得出来,python的列表对内存的开销是比较大的。

上一篇:java笔记5之逻辑运算符以及&&与&的区别


下一篇:network Driver , TDI(Transport Driver Interface) Drivers