首页 » 编程语言 » Python列表:初学者应该懂得操作和内部实现

Python列表:初学者应该懂得操作和内部实现

 
Python列表:初学者应该懂得操作和内部实现

Python列表:初学者应该懂得操作和内部实现

Python列表:初学者应该懂得操作和内部实现

Python列表:初学者应该懂得操作和内部实现

最近一直在连载 Python 的基础知识,但有的读者反馈说内容有点太初级。面向的读者太垂直,希望能再深入点去讲解下 Python 知识点中的内部实现。

本着“读者为大”的理念,我决定从这篇文章开始在讲解基础知识的同时去深入到内部实现原理。让我们在掌握理论知识的前提下,能更加准确的抓住它的实现原理。

上篇文章 如何理解和使用 Python 中的列表,对 Python 列表的概念和使用做了一个简单的讲解。这篇文章将深入到列表的操作以及内部实现。

简单的操作

掌握了列表的创建以及访问,我们接下来去了解下更重要的一点,“列表的增删改”。

在绝大多数情况下,你创建的列表是动态的。这就意味着你的列表创建之后,会随着程序的运行增删元素。比如,你创建了家庭的年龄列表,随着时间的推移,对应成员的年龄元素会递增,再或者家里娶了媳妇那么这个列表是不是就应该增加一个呢?

0x00、添加元素

在实际的代码中,我们有两种添加元素的情况:

一种是在列表尾部添加,另一种是在列表中插入元素。

列表尾部添加元素,我们可以用到 append() 这个方法:

>>> friends=['Mark','Alison','Kobe']
>>> print(friends)
['Mark', 'Alison', 'Kobe']

>>> friends.append('Jordan')
>>> print(friends)
['Mark', 'Alison', 'Kobe', 'Jordan']
>>>

方法 append()将元素 'Jordan' 添加到了列表尾部,而不影响列表中的其他所有元素。

在实际开发中,我们可以先创建一个空列表,再结合使用一系列的 append() 语句添加元素:

>>> friends=[]
>>> friends.append('Mark')
>>> friends.append('Alison')
>>> friends.append('Kobe')
>>> print(friends)
['Mark', 'Alison', 'Kobe']
>>>

这种创建列表的方式在代码中极其常见,因为经常要程序运行后,你才知道用户要在程序中存储哪些数据。所以为控制用户,你可以先创建一个空列表,然后将用户提供的数据 append 到空列表中。

在列表中插入元素,在 Python 中有个 insert 方法来实现这种情况。你可以指定新元素的索引和值:

>>> friend=['Mark','Alison']
>>> friend.insert(1,'Kobe')
>>> print(friend)
['Mark', 'Kobe', 'Alison']
>>>

0x01、修改列表元素

其实修改列表的元素和访问列表元素的语法类似。修改元素只需要指定列表名和元素的索引即可:

>>> friends=['Mark','Alison']
>>> friends[0]='xiyouMc'
>>> print(friends)
['xiyouMc', 'Alison']
>>>

这样,我们就修改了索引为 0 的值。当然,你可以修改任何元素。

0x02、从列表中删除元素

要删除列表中的元素,大概有两种方式:

一种是使用 del 语句,另一种是 pop 方法。

若要有 del 语句删除列表元素,首先你需要知道准备删除元素的索引值:

>>> friends=['Mark','Alison','Kobe']
>>> del friends[2]
>>> print(friends)
['Mark', 'Alison']
>>>

像这样,我们使用 del 语句就删除了索引为 2 的元素 'Kobe'。

pop ,这个方法支持两种删除方式。在数据结构上来讲 Python 的列表,那么就可以将其理解为栈,通过 pop 也就是弹出,我们可以将栈顶或者尾部元素弹出列表中:

>>> friends=['Mark','Alison','Kobe']
>>> friends.pop()
'Kobe'
>>> print(friends)
['Mark', 'Alison']
>>>

可以看到,我们在 pop 的时候会拿到尾部的元素。所以你可以猜到 pop 函数其实就是从列表中拿出尾部的元素来使用,当然它会将尾部的元素也删除掉。

pop 的另一种方式有点类似于 del 语句,它也是首先需要指定要删除的元素索引:

>>> friends=['Mark','Alison','Kobe']
>>> friends.pop(0)
'Mark'
>>> print(friends)
['Alison', 'Kobe']
>>>

这段代码我们就将列表中索引为 0 的元素 pop 了出来,并将其从列表中删除掉。

综上两种删除方式,在实际代码中,如果你无法确定使用哪种方式来删除,可以参考这个标准:如果你要从列表中删除一个元素,并且不再以任何方式使用它,那么就用 del 语句;如果你要在删除元素后还能继续使用它,那么就使用 pop 方法。

至此列表的概念和使用都已经讲完了,接下来让我们更加深入的去理解列表的内部实现。

这里多说句我个人学习新技术、新语言的态度,学习一门新的语言多数情况下我们都会去学习它怎么使用。但若你想使用的更好,那么一定要深入到它的内部实现原理,掌握了它的原理才能更好使用这门语言。

列表的内部实现

说到 Python 列表的内部实现,其实也就是 CPython 对列表的实现。既然要说 CPython,那么肯定就是 C 相关的。

0x00、数据结构

在 CPython 中,其实列表对象是一个 C 语言中的数据结构。没有 C 基础的读者,我可以简单做个介绍,在 C 程序中数据的传递都是有一定结构的,有了这个结构那么我们就可以在代码中更好的处理数据。所以,这也就叫做数据结构。

那么 Python 列表的数据结构是怎么样的?

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

其中可以看到 ob_item,这是指向列表元素的指针数组,allocated 是指申请的内存的槽的个数。

简单的说下就是列表对象在 C 程序中的数据结构:有一个针数组用来保存列表元素的指针,和一个可以在列表中放多少元素的标记

0x01、列表初始化

上面有提过,列表的初始化可以直接指定参数,也可以初始化一个空列表,a = []

那么 CPython 是怎么实现这个初始化动作的,来看看:

arguments: size of the list = 0
returns: list object = []
PyListNew:
nbytes = size * size of global Python object = 0
allocate new list object
allocate list of pointers (ob_item) of size nbytes = 0
clear ob_item
set list's allocated var to 0 = 0 slots
return list object

可以看到,先分配一个对象的内存块,同时将这个内存块的大小置零。再给这个对象分配一个内存槽的大小。

这里说下,上面说到在列表的数据结构中有个内存的槽的个数。这个个数并不是当前列表就有这么多的元素。列表元素的个数和 len(列表)是一样,就是真正的元素的个数。但分配的槽的大小,会比元素个数大一点,目的就是为了防止在每次添加元素的时候都去调用分配内存的函数。那么接下来看看 Append 函数。

0x02、Append 函数

再次回顾下 Append 函数,它是一个可以在列表中添加元素的函数。

>>> friends=[]
>>> friends.append('Mark')
>>> friends.append('Alison')
>>> print(friends)
['Mark', 'Alison']
>>>

那么这个 Append 函数在 CPython 中又是怎么实现的呢?

其实在 CPython 底层有一个函数 app1 ,就是提供给列表做 Append 操作的。比如我们给一个列表添加一个整数:l.append(1)

arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
n = size of list
call list_resize() to resize the list to size n+1 = 0 + 1 = 1
list[n] = list[0] = new element
return 0

它会先拿到当前列表的大小,同时调用 list_resize() 重新设置一个新的 size。那么 list_resize() 函数是什么?

arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
new_allocated += newsize = 3 + 1 = 4
resize ob_item (list of pointers) to size new_allocated
return 0

可以看到它会多申请一些内存,这样也就避免了多次调用该函数。总的槽大小也就是4,同时第一个位置的数据就是 1。来看看下面这张我手绘的图:

Python列表:初学者应该懂得操作和内部实现

可以看到,L[0] 就是我们新添加的元素,同时多分配出来的内存用虚线表示,它代表已经分配但是未使用的内存。

接下来,我们继续 append(2),调用 list_resize 函数,参数为 n + 1 = 2,但因为已经申请了四个空间,所以不需要再次申请内存。同样的 append(3) 和 append(4) 是一样的。

Python列表:初学者应该懂得操作和内部实现

0x03、Insert 函数

基于上面的例子,我们在这个列表的索引为 1 的位置插入一个新的元素。这时候 CPython 会调用 ins1() 这个函数:

arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
    resize list to size n+1 = 5 -> 4 more slots will be allocated
    starting at the last element up to the offset where, right shift each element 
    set new element at offset where
    return 0

 

Python列表:初学者应该懂得操作和内部实现

虚线的方框依旧是申请未使用的槽空间。现在可以看到已经有了 8 个槽空间,但是列表的大小却是 5。

 

0x04、Pop 操作

在 Python 的列表中,Pop 函数就是取出列表的最后一个元素,在 CPython 对应的函数是 listpop() 函数。

在这个函数还是会调用到 list_resize 函数,如果取出列表元素后的列表大小小于分配的槽空间数的一半,那么将会缩减列表的大小。

arguments: list object
returns: element popped
listpop:
    if list empty:
        return null
    resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
    set list object size to 4
    return last element

Python列表:初学者应该懂得操作和内部实现

可以看到调用 pop 函数之后,虽然索引为 4 的位置已经被取出了,但是在列表中 4 的索引仍然指向原来的整数对象,只不过列表的大小变成了 4。

接下来我们再调用 pop 函数:

Python列表:初学者应该懂得操作和内部实现

由于再次 pop 之后,元素的个数小于了槽空间的一半,所以CPython 将这个列表的槽空间缩减到了 6 。同时你依然可以看到原索引还是指向原数据内存。这也就是说用 pop 的话,你的程序里面就可以持续使用这个数据。


这篇文章算是对 Python 列表做了一个从入门到精通。一开始讲述了下对 Python 列表的操作,包括增加、删除、修改。

之后又对 Python 列表内部实现做了讲解,从 CPython 的角度对列表做一个更深的讲解,在使用列表的同时,你更需要了解为什么那么用。


文章来源:DeveloperPython

 

原文链接:Python列表:初学者应该懂得操作和内部实现,转载请注明来源!

2