pythonlist实现原理
数据如何在内存中存储？
在32位的计算机上，1个字节有8位，内存寻址最⼩的单位是字节。假设我们有⼀个int类型的值，他的内存地址从0x01开始，int类型占据4个字节，则其结束于0x13。
那么数据类型有什么意义呢
它确定了特定类型的数据需要申请多⼤的内存地址来存储，并且决定取到的⼆进制数该如何解释。地址存储的只有⼆进制数，但是对于数字和字符，同⼀个⼆进制数代表的意义是不同的。
同类型的数据在内存中是如何连续存储的？
假设将⼀个含有4个数字的集合（数学意义上的集合，下同）连续地存储在⼀起，在内存⾥的表现就像是他们紧挨在⼀起。如果第⼀个元素从0x10开始，那整个集合就在0x25结束。
因为类型相同，所以每个元素的偏移量也相同，公式如下：（c是元素类型的⼤⼩）：
这就是为什么集合要从0开始。根据下标获取指定元素，只需要计算偏移量，⽽不⽤遍历整个集合。
顺序表在内存中的结构是什么？
要在内存中给集合开辟⼀块区域，得先确定⼤⼩；确定区域后，还需要知道当前已经占⽤了多少个元素，⼀旦溢出，就要重新申请空间。要表达这种结构，有两种实现⽅式。⼀种是把头信息和元素串到⼀起，形成⼀个元素个数+2的表。另⼀种就是把头信息和元素分开放，两者之间⽤⼀个元素建⽴⼀个链接，连在⼀起。
存储表信息的单元与元素存储区以连续的⽅式安排在⼀块存储区⾥，两部分数据的整体形成⼀个完整的顺序表对象。⼀体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的⼀部分，顺序表创建后，元素存储区就固定了。
分离式结构中表对象⾥只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另⼀个
独⽴的元素存储区⾥，通过链接与基本表对象关联。
⼀旦表需要扩充，对于⼀体式结构来说，就要重新申请⼀块更⼤的空内存区域，将所有元素放⼊其中，再清空旧的内存区域。
对于分离式结构来说，则需要将链接地址更新⼀下，顺序表对象是不变的。
python获取数组长度
说到扩充，⼜是如何进⾏的呢？
采⽤分离式结构的顺序表，若将数据区更换为存储空间更⼤的区域，则可以在不改变表对象的前提下对其数据存储区进⾏了扩充，所有使⽤这个表的地⽅都不必修改。
扩充的策略可以说有两种。
每次扩充增加固定数⽬的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。特点：节省空间，但是扩充操作频繁，操作次数多。（就是以时间换空间，以后每次添加的元素过多就要多花时间重新扩容）
每次扩充容量加倍，如每次扩充增加⼀倍存储空间。特点：减少了扩充操作的执⾏次数，但可能会浪费空间资源。（以空间换时间，每次扩容占⽤的空间⼤了，但扩容就可以少执⾏些）
不同类型的数据集合在内存中是如何存储的？
当集合包含不同类型的数据时，⽤偏移量来定位就不可靠了，因为各⾃类型不同。
假设集合⾥有12，1.2，'ab’三个元素，他们的位置各不连续，分散在不同的地⽅。申请⼀块3个元素⼤⼩的连续内存，⾥⾯每个元素分别指向集合的三个元素。
这时的元素是外置的。
现在让我们来看看python中的list。
1.元素有位置下标，可以通过索引获取元素 --> 连续的存储空间，计算偏移量获取元素。
2. 元素⽆论如何改变，表对象都不变 --> 分离式结构，表头和元素内容分开存储。这样在更改list时，表对象始终是同⼀个，只是指向的地址不同
3. 元素可以是任意类型 --> 既要求连续存储，⼜可以存储不同类型的数据，⽤的是元素外置的⽅式，存储的只是数据地址的引⽤
4. 可以任意添加新元素 --> 动态扩充的策略
list底层实现
list源码如下：
typedef struct{
PyObject_VAR_HEAD
/* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */    PyObject **ob_item;
/* ob_item contains space for 'allocated' elements.  The number
* currently in use is ob_size.
* Invariants:
*    0 <= ob_size <= allocated
*    len(list) == ob_size
*    ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.    */
Py_ssize_t allocated;
} PyListObject;
list 本质上是⼀个长度可变的连续数组。 其中 ob_item 是⼀个指针列表，⾥边的每⼀个指针都指向列表中的元素，⽽ allocated 则⽤于存储该列表⽬前已被分配的空间⼤⼩。
需要注意的是，allocated 和列表的实际空间⼤⼩不同，列表实际空间⼤⼩，指的是 len(list) 返回的结果，也就是上边代码中注释中的
ob_size，表⽰该列表总共存储了多少个元素。⽽在实际情况中，为了优化存储结构，避免每次增加元素都要重新分配内存，列表预分配的空间 allocated 往往会⼤于 ob_size。
因此 allocated 和 ob_size 的关系是：allocated >= len(list) = ob_size >= 0。
如果当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更⼤的内存空间，并把原来的元素全部拷贝过去。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。