列表作为序列型对象都支持哪些操作,它们在底层是怎么实现的?

简介: 列表作为序列型对象都支持哪些操作,它们在底层是怎么实现的?

楔子



列表拥有非常多的方法,比如添加元素、查询元素等,这些都属于列表的自定义方法。当然不光是列表,任何对象都可以有自己的自定义方法,而这些方法会保存在类型对象的 tp_methods 里面。

当然列表除了拥有自定义的方法之外,还拥有作为序列型对象所共有的方法,比如合并、基于索引和切片获取元素、基于索引和切片设置元素等等。

d0c613ce30e1ede05e6957f28672244b.png

这些方法会基于种类被抽象成三个方法簇,分别是:

  • tp_as_number:数值型对象拥有的方法;
  • tp_as_sequence:序列型对象拥有的方法;
  • tp_as_mapping:映射型对象拥有的方法;


每个方法簇都包含了大量的 C 函数,每个 C 函数一般会对应 Python 里的一个魔法方法和操作符。比如 tp_as_sequence 的 sq_concat 对应序列型对象的 __add__ 方法,tp_as_number 的 nb_subtract 对应数值型对象的 __sub__ 方法。

那么接下来我们就详细剖析一下这些方法的具体实现过程。


列表的相加



序列型对象都实现了加法运算,比如列表,两个列表相加可以合并为一个新的列表。

print([1, 2, 3] + [4, 5])  
"""
[1, 2, 3, 4, 5]
"""

虽然使用了 + 操作符,但它在底层是由 tp_as_sequence.sq_concat 负责实现的,该字段被赋值为 list_concat 函数,看一下它的内部逻辑。

// Objects/listobject.c
static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{   
    // 两个列表相加之后的新列表的长度
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyListObject *np;
    // 如果 bb 不是列表,抛出 TypeError
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  Py_TYPE(bb)->tp_name);
        return NULL;
    }
#define b ((PyListObject *)bb)
    // 两个列表的长度相加一定小于 PY_SSIZE_T_MAX
    assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
    // 新列表的长度,等于相加的两个列表的长度之和
    size = Py_SIZE(a) + Py_SIZE(b);
    // 如果长度为 0,那么创建一个空列表,然后返回即可
    if (size == 0) {
        return PyList_New(0);
    }
    // 为 PyListObject 和底层数组申请空间(空间大小为 8 * size)
    np = (PyListObject *) list_new_prealloc(size);
    if (np == NULL) {
        return NULL;
    }
    // 将第一个列表的元素增加引用计数之后,拷贝到新列表中
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    // 将第二个列表的元素增加引用计数之后,拷贝到新列表中
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    // 将新列表的 ob_size 设置为 size
    Py_SET_SIZE(np, size);
    // 转成泛型指针之后返回
    return (PyObject *)np;
#undef b
}

逻辑非常简单,假设两个列表 a 和 b 相加,过程如下。

  • 先申请一个新列表,长度为 len(a) + len(b);
  • 将列表 a 的元素拷贝到新列表中;
  • 将列表 b 的元素拷贝到新列表中;

说白了就是两个 for 循环。


列表的重复



列表可以乘上一个整数,将自身重复指定次数,该过程会返回一个新列表。

print([1, 2, 3] * 3)
"""
[1, 2, 3, 1, 2, 3, 1, 2, 3]
"""

虽然使用了 * 操作符,但它在底层是由 tp_as_sequence.sq_repeat 负责实现的,该字段被赋值为 list_repeat 函数,看一下它的内部逻辑。

// Objects/listobject.c
static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    // 获取 a 指向的列表的长度
    const Py_ssize_t input_size = Py_SIZE(a);
    // 如果列表长度为 0,或者乘上一个小于等于 0 的数
    // 那么创建的新列表的长度依旧是 0,因此直接返回空列表即可
    if (input_size == 0 || n <= 0)
        return PyList_New(0);
    assert(n > 0);
    // 长度有限制,不能超过 PY_SSIZE_T_MAX
    if (input_size > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    // 新列表的长度
    Py_ssize_t output_size = input_size * n;
    // 为新列表和底层数组申请空间,底层数组的长度为 output_size
    PyListObject *np = (PyListObject *) list_new_prealloc(output_size);
    if (np == NULL)
        return NULL;
    // 指向新列表的底层数组的首元素
    PyObject **dest = np->ob_item;
    // 如果原始列表的长度为 1,比如 a = [1],n = 3
    // 那么新列表就是 [1, 1, 1]
    if (input_size == 1) {
        // 拿到第一个元素
        PyObject *elem = a->ob_item[0];
        // 因为要重复 n 次,所以引用计数增加 n
        _Py_RefcntAdd(elem, n);
        PyObject **dest_end = dest + output_size;
        // 将新列表的底层数组的元素全部设置为 elem
        while (dest < dest_end) {
            *dest++ = elem;
        }
    }
    // 如果原始列表的长度不为 1
    else {
        PyObject **src = a->ob_item;
        PyObject **src_end = src + input_size;
        // 将原始列表的元素依次拷贝到新列表中,但此时只拷贝了 1 次
        while (src < src_end) {
            _Py_RefcntAdd(*src, n);
            *dest++ = *src++;
        }
        // 将新列表里面的元素再重复 output_size / input_size - 1  次
        // 说白了就是再重复 n - 1 次
        _Py_memory_repeat((char *)np->ob_item, 
                          sizeof(PyObject *)*output_size,
                          sizeof(PyObject *)*input_size);
    }
    // 将新列表的 ob_size 设置为 output_size
    Py_SET_SIZE(np, output_size);
    return (PyObject *) np;
}

假设列表 a 和整数 n 相乘,过程如下。

  • 创建一个新列表,长度为 len(a) * n;
  • 将列表 a 的元素拷贝到新列表中;
  • 将新列表的元素再重复 n - 1 次;


基于索引和切片获取元素



列表可以基于索引和切片截取元素。

data = [1, 2, 3, 4, 5]
print(data[1])  # 2
print(data[1: 4])  # [2, 3, 4]

在底层它由 tp_as_mapping.mp_subscript 实现,该字段被赋值为 list_subscript 函数,看一下它的内部逻辑。

// Objects/listobject.c
static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{   
    // 在基于索引和切片截取时,所有序列型对象的逻辑都差不多
    if (_PyIndex_Check(item)) {
        // 如果 item 是索引,那么转成 Py_ssize_t 整数
        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        // 如果 i 小于 0,那么加上列表长度,转成正数索引
        if (i < 0)
            i += PyList_GET_SIZE(self);
        // 调用 list_item 获取 ob_item 中索引为 i 的元素
        return list_item(self, i);
    }
    // 如果 item 是切片
    else if (PySlice_Check(item)) {
        // start, stop, step 分别表示起始位置、终止位置、步长
        // slicelength 表示切片截取的长度,也就是要截取多少个元素
        Py_ssize_t start, stop, step, slicelength, i;
        size_t cur;
        PyObject* result;
        PyObject* it;
        PyObject **src, **dest;
        // 获取切片的 start、stop、step
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
            return NULL;
        }
        // 传入原始列表的长度,对 start 和 stop 进行调整,并返回 slicelength
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
        // 如果 slicelength <= 0,说明截取不到任何元素
        // 比如 data[5: 1] 或者 data[1: 5: -1],那么直接返回空列表
        if (slicelength <= 0) {
            return PyList_New(0);
        }
        // 如果步长为 1,那么直接将列表中 start 到 stop 之间的元素拷过去即可
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        // 否则说明步长不为 1
        else {
            // 为创建的新列表和底层数组申请空间
            result = list_new_prealloc(slicelength);
            if (!result) return NULL;
            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            // 从 start 处开始遍历,将元素拷贝过去
            // 然后 cur 每次增加 step,遍历次数为 slicelength
            for (cur = start, i = 0; i < slicelength;
                cur += (size_t)step, i++) {
                it = Py_NewRef(src[cur]);
                dest[i] = it;
            }
            // 将新列表的 ob_size 设置为 slicelength
            Py_SET_SIZE(result, slicelength);
            return result;
        }
    }
    // 否则说明 item 既不是索引也不是切片,那么报错
    else {
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers or slices, not %.200s",
                     Py_TYPE(item)->tp_name);
        return NULL;
    }
}

这个和之前介绍的 bytes 对象有点像,因为它们都是序列型对象,在基于索引和切片截取元素时的逻辑也是类似的。

但 bytes 对象只能截取元素,却不能设置元素,而列表是可以的,因为列表是可变对象。


基于索引和切片设置元素



列表是可变对象,因为它支持设置元素,即对内部元素进行修改。基于索引设置元素就不说了,我们主要看切片,它背后还是有一些复杂的。

data = [1, 2, 3, 4, 5, 6, 7, 8]
# 通过切片设置元素,右值一定是一个可迭代对象
data[0: 3] = [11, 22, 33]
# 会将 data[0] 设置为 11,将 data[1] 设置为 22,将 data[2] 设置为 33
print(data)
"""
[11, 22, 33, 4, 5, 6, 7, 8]
"""
# 而且它们的长度是可以不相等的,这里表示将 [0: 3] 的元素设置为 [1, 2]
# 即 data[0] 设置成 1,data[1] 设置成 2,那么问题来了,data[2] 咋办?
# 由于右值中已经没有元素与之匹配了,那么 data[2] 就会被删掉
data[0: 3] = [1, 2]
print(data)
"""
[1, 2, 4, 5, 6, 7, 8]
"""
# 所以如果想删除 [0: 3] 的元素,那么只需要执行 data[0: 3] = [] 即可
# 因为 [] 里面没有元素能与之匹配,所以 data 中 [0: 3] 的位置由于匹配不到
# 那么相当于执行了删除操作,当然由于 Python 的动态特性,还可以像下面这么做
# data[0: 3] = []、data[0: 3] = ()、data[0: 3] = "" 等等也是没问题的
data[0: 3] = ""
print(data)
"""
[5, 6, 7, 8]
"""
# 实际上执行 del data[0] 的时候,就是执行了 data[0: 1] = []
# 当然,如果右值元素多的话也是可以的,相当于插入
# 比如这里的 data[0] 匹配 1,然后左边就结束了
# 于是右侧剩余的元素会依次插在后面
data[0: 1] = [1, 2, 3, 4]
print(data)
"""
[1, 2, 3, 4, 6, 7, 8]
"""
# 重点来了,如果切片的步长不等于 1 的话,那么两边一定要匹配
# 由于 data[:: 2] 会得到 4 个元素,那么右边的可迭代对象的长度就必须也是 4
data[:: 2] = ['a', 'b', 'c', 'd']
print(data)
"""
['a', 2, 'b', 4, 'c', 7, 'd']
"""
# 但如果长度不一致,那么会报错
try:
    data[:: 2] = ['a', 'b', 'c']
except Exception as e:
    # 显然会报错
    print(e)  
"""
attempt to assign sequence of size 3 to extended slice of size 4
"""

至于它的源码有兴趣可以自己看一下,在底层它由 tp_as_mapping.mp_ass_subscript 负责实现,该字段被赋值为 list_ass_subscript 函数。逻辑比较长,但不难理解,我们总结一下。

list_subscript 用于获取元素,list_ass_subscript 用于设置元素。调用这两个函数,我们即可以传入索引,也可以传入切片。

  • 获取元素时传入的是索引,那么 list_subscript 内部会调用 list_item,传入的是切片,那么会调用 list_slice。
  • 设置元素时传入的是索引,那么 list_ass_subscript 内部会调用 list_ass_item,传入的是切片,那么会调用 list_ass_slice。并且 list_ass_slice 虽然是设置元素,但删除元素也是调用的它,比如通过 data[n:n+1]=[] 便可删除索引为 n 的元素。事实上 remove 和 pop 方法都只是计算出待删除元素的索引,真正的删除操作还是通过 list_ass_slice 来执行的。
  • 另外,当传入切片时,只有步长为 1,才会调用 list_slice 和 list_ass_slice。如果步长不为 1,那么就采用循环的方式逐个遍历。


小结


以上我们就介绍了列表作为序列型对象拥有的方法,但除了这些它还有很多自定义的方法。由于列表用得非常广泛,关于它的方法我们都来详细地说上一说,下一篇文章介绍列表的自定义方法。

相关文章
|
6月前
|
NoSQL API Redis
数据对象的底层实现方式你都了解吗?
上一小节我们提到的五种数据类型其实就是 Redis 的数据对象,我们先来看看数据对象的类型:Redis 的 key 都是 string 类型的,以上各类型说的其实都是 value 的类型,以下是对象的几个优点:
52 0
数据对象的底层实现方式你都了解吗?
|
5月前
|
安全 Java 数据库
ifPresent()`方法的用途、使用场景
ifPresent()`方法的用途、使用场景
366 4
|
24天前
|
存储 缓存 索引
集合支持的操作有哪些,它们是怎么实现的?
集合支持的操作有哪些,它们是怎么实现的?
38 8
|
24天前
|
Python
字典是怎么创建的,支持的操作又是如何实现的?
字典是怎么创建的,支持的操作又是如何实现的?
42 8
|
24天前
|
存储 索引 Python
字典是怎么实现的,它的底层结构长什么样子?
字典是怎么实现的,它的底层结构长什么样子?
40 2
|
6月前
|
存储 JSON NoSQL
Redis中当存储数据为List集合时,如何控制集合内每个数据元素的生命周期
Redis中当存储数据为List集合时,如何控制集合内每个数据元素的生命周期
403 0
|
11月前
|
存储 算法 Serverless
哈希原理、模拟封装unordered系列关联式容器及其应用
哈希原理、模拟封装unordered系列关联式容器及其应用
69 0
|
存储
ES6中新增的Set、Map两种数据结构怎么理解以及操作方法
Set是一种叫做集合的数据结构,Map是一种叫做字典的数据结构
114 0
|
敏捷开发 前端开发 Ruby
RailsAdmin如何实现自定义操作
RailsAdmin如何实现自定义操作
98 0
|
存储 并行计算 安全
ConcurrentHashMap的使用方法及其内部实现原理
ConcurrentHashMap的使用方法及其内部实现原理
179 0