python list 底层,python列表list结构特点

　　python数据结构——list和tuple底层实现分析说到Python中list和tuple的底层实现，就要回到最基础的数据结构3354线性表。

　　将一组通常属于同一类型的数据元素视为一个序列。序列中的位置和顺序代表有意义的信息或关系。这样的数据序列是一个线性表。线性表(表)应用广泛，是复杂结构的基础。

　　线性表中的线性来自于每个元素的上下文的顺序连接，即除了第一个元素，表中的每个元素只有一个前驱元素；除了最后一个元素，每个元素只有一个后继元素。所以叫线性表。

　　如何组织线性表中的数据并为其配置高效的操作方法是实现线性表的关键。

　　这里要考虑两个方面：1。保存元素数据信息和元素序列信息应适应计算机内存的管理；2.考虑重要操作的效率，比如位置访问的改变和删除，元素遍历等。

　　因此，提出了两种基本的表格模型。1.顺序表:表元素直接按顺序放在一个分区的连续存储区中，所以元素的顺序自然用存储顺序来表示。2.链接表:将表格元素放入由链接构成的一系列存储块中。这两种模式各有优缺点。

　　我们来看下面的序列表。

　　该表的基本实现非常简单。通常，元素是同一类型的，因此每个元素的存储容量是相同的。只需要排列等间距的存储单元来顺序存储元素数据，并将它们直接映射到存储器中。表中任何元素的位置计算都很简单，只要知道第一个元素的内存位置和逻辑地址(元素索引0，1，2，)*单个元素的存储单元个数足够了，所以索引操作和元素访问都是O(1)次。

　　但是表元素的大小差别很大，如果需要的存储单元不一致，内存就无法按照统一的线性顺序排列。只需将实际的元素数据存储在另一个存储区，将每个元素数据的标签保存在序列表的原存储单元(标识，即引用信息，地址链接在一个独立的存储区实现对元素的间接访问)。因为地址链接的大小肯定是一样的，所以仍然保持了内存的顺序映射。这个结构也叫索引结构。

　　这里要注意的是，在每次对表进行外部操作之后，必须实时记录存储块的容量(max)和当前元素的数量(num)作为支持各种操作的附加数据信息。直接访问元素显然是O(1)时间。如果按下标循环，检查，处理，O(n)时间就复杂了。

　　特别是要注意变化操作中的保序问题，以及尾部操作和定点操作的区别。

　　桌子那头的操作显然很简单。如果判断表未满(maxnum)，可以直接找到末端，根据num进行操作。如果在其他指定的位置添加新元素，比如I，I的位置就被新元素占据，原来I位置的元素直接移到num的末尾。这是一个非保序操作，时间为O(1)。在改变操作之后，不要求元素的顺序与原始顺序一致。如果要保持原来的元素顺序，就要把原来的I-position元素移回i 1，把原来的i 1-position元素移回i 2，后面的元素都要前移。由于元素的数量，保序操作的最差和平均时间为O(n)。删除操作类似。

　　汇总表：优点是在O(1)时间内直接按位置访问元素，元素存储紧凑。除了表格元素，只需要O(1)的空间来存储存储区之外的少量辅助信息(max和num)。缺点：一旦表大了，就需要大量的连续内存空间。存储块划分后无法更新，造成闲置浪费。Add操作移动了很多元素，效率很低。

　　一个序列表包括两部分信息，一部分是元素数据的集合，另一部分是上一次执行操作的记录辅助信息(max和num)。这样，int

　　最后，要考虑表存储区域的大小。当存储区域已满时，必须分配更大的存储区域来替换它。一体式结构在这里失败了。还介绍了分离技术。在不改变表的标识符的情况下，我们可以申请更大的存储区域，然后将现有的元素复制到新的存储区域，并更新存储链接，这样就可以继续添加新元素。这种可扩展容量的表是分离式。

　　对于动态顺序表，前端插入和定位插入，每个操作都与长度有关。如果表的大小从0增加到N，那么整个增长过程中的插入时间将为O(n2)。

　　将(O(1))插入后端，然后考虑容量更新的问题。它涉及到空闲内存单元的数量和替换内存区域的频率。一种策略是线性增长，比如每次更换存储区域增加10个存储单元，那么假设从0容量到1000，每增加10个元素，每次存储变化进行一次元素拷贝，总拷贝数=10 ^ 20 ^ 30。90=49500.考虑到增长到N个容量(N个后端插入)，有1/20n2个复制。虽然每次尾部插入需要O(1)时间，但是一次插入的平均开销变成了O(n)，并不理想。

　　另一种方式是加倍策略。每次更新存储容量翻倍，考虑到容量从0增加到1024，副本数为1 ^ 2 ^ 4。52=1023.对于容量n，表从0到n的整个增长过程，进行尾端插入，每次更新存储区域增加一倍，元素副本数也是O(n)，插入操作的平均时间变成O(1)。比前者有优势。但其实也是以空间换时间。

　　到目前为止，回头看看python的list和tuple，都是采用顺序表的结构。元组不支持更改内部状态的操作。请参见可更新列表。

　　下面的列表被有效地索引和更新，具有O(1)和有序元素。只能使用连续表。元素数据存储在一个连续的存储区域，需要删除和插入来保持顺序。尾部插入O(1)，定位插入O(n)，其中n为长度。列表中可以不断添加新元素，对象标识(其内存地址可以通过内置的id函数看到)保持不变。可以看出使用了分离存储技术，是动态顺序表，存储区域可以扩展和替换。

　　根据python的文档，列表存储区的扩展实际上采用了以下原则：空表分配8个元素的存储区，当插入(append，insert等。)元素已满，存储区域更改为4倍大小(不超过50，000)。如果表非常大(超过50，000个元素)，存储区域将增加一倍。

　　综上所述，python的list是一个连续存储、结构分离的动态顺序表，插入和删除都需要保序。使用时一定要考虑尾插和定位插的效率差异。

　　当然，python并没有提供检查list对象存储容量的函数或方法，也没有人为设置容量的操作。容量更新的操作由python解释器自动分配。它减少了编程负担和人为错误，也限制了表的使用，这是其他策略无法优化的。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。