python 列表的实现探析

原创

Yerik

修改于 2021-05-08 10:09:14

1.7K0

修改于 2021-05-08 10:09:14

知其然也要知其所以然，python中的容器对象真的不多，平常我们会很心安理得的根据需求来使用对应的容器，不定长数据用list，想去重用set，想快速进行匹配用dict，字符处理用str，可为何能实现这个效果呢？比如我们用list的时候，知道这玩意可以随意存储各种格式，存整型、浮点、字符串、甚至还可以嵌套list等其他容器，这底层的原理到底是用数组实现的，还是用链表？比如我们的字典，底层是用数组还是其他？如果是其他如哈希表，那又怎么实现输入数据的顺序排列？这次不妨一层层剖析，推演一番。贪多嚼不烂，本次就先对list进行分析

简述

这个名字很容易和其它语言（C++、Java等）标准库中的链表混淆，不过事实上在CPython的列表根本不是列表（这话有点绕，可能换成英文理解起来容易些：python中的list不是我们所学习的list），在CPython中，列表被实现为长度可变的数组。

从细节上看，Python中的列表是由对其它对象的引用组成的连续数组，指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。在实现过程中，Python在创建这些数组时采用了指数分配的方式，其结果导致每次操作不都需要改变数组的大小，但是也因为这个原因添加或取出元素的平均复杂度较低。

这个方式带来的后果是在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。

利用list.insert(i,item) 方法在任意位置插入一个元素——复杂度O(N)
利用list.pop(i) 或list.remove(value) 删除一个元素——复杂度O(N)

源码解析

让我们先看下list实现的源码，源汁源味，细细品评。我们先发现list多重继承自MutableSequence 和Generic。之后我们可以读到，list的相关内嵌函数的实现，如append、pop、extend、insert等其实都是通过继承来实现的，那么我们就不得不去找一下MutableSequence 和Generic这两个类的实现底层，也只有解答了这两个类之后，我们才能回答为何list可以实现动态添加数据，而且删除和插入的复杂度还不是那么优秀。

class list(MutableSequence[_T], Generic[_T]):
    @overload
    def __init__(self) -> None: ...
    @overload
    def __init__(self, iterable: Iterable[_T]) -> None: ...
    if sys.version_info >= (3,):
        def clear(self) -> None: ...
        def copy(self) -> List[_T]: ...
    def append(self, object: _T) -> None: ...
    def extend(self, iterable: Iterable[_T]) -> None: ...
    def pop(self, index: int = ...) -> _T: ...
    def index(self, object: _T, start: int = ..., stop: int = ...) -> int: ...
    def count(self, object: _T) -> int: ...
    def insert(self, index: int, object: _T) -> None: ...
    def remove(self, object: _T) -> None: ...
    def reverse(self) -> None: ...
    if sys.version_info >= (3,):
        def sort(self, *, key: Optional[Callable[[_T], Any]] = ..., reverse: bool = ...) -> None: ...
    else:
        def sort(self, cmp: Callable[[_T, _T], Any] = ..., key: Callable[[_T], Any] = ..., reverse: bool = ...) -> None: ...

    def __len__(self) -> int: ...
    def __iter__(self) -> Iterator[_T]: ...
    def __str__(self) -> str: ...
    __hash__: None  # type: ignore
    @overload
    def __getitem__(self, i: int) -> _T: ...
    @overload
    def __getitem__(self, s: slice) -> List[_T]: ...
    @overload
    def __setitem__(self, i: int, o: _T) -> None: ...
    @overload
    def __setitem__(self, s: slice, o: Iterable[_T]) -> None: ...
    def __delitem__(self, i: Union[int, slice]) -> None: ...
    if sys.version_info < (3,):
        def __getslice__(self, start: int, stop: int) -> List[_T]: ...
        def __setslice__(self, start: int, stop: int, o: Sequence[_T]) -> None: ...
        def __delslice__(self, start: int, stop: int) -> None: ...
    def __add__(self, x: List[_T]) -> List[_T]: ...
    def __iadd__(self: _S, x: Iterable[_T]) -> _S: ...
    def __mul__(self, n: int) -> List[_T]: ...
    def __rmul__(self, n: int) -> List[_T]: ...
    if sys.version_info >= (3,):
        def __imul__(self: _S, n: int) -> _S: ...
    def __contains__(self, o: object) -> bool: ...
    def __reversed__(self) -> Iterator[_T]: ...
    def __gt__(self, x: List[_T]) -> bool: ...
    def __ge__(self, x: List[_T]) -> bool: ...
    def __lt__(self, x: List[_T]) -> bool: ...
    def __le__(self, x: List[_T]) -> bool: ...

MutableSequence

这个类其实是来自于collections.abc.MutableSequence，其实也就是所谓的抽象基础类里面的可变序列的方法。

Python的序列有两种，可变序列和不可变序列并为其提供了两个基类Sequence和MutableSequence，这两个基类存在于内置模块collections.abc中，与其他常见的类如int、list等不同，这两个基类都是抽象基类。这里涉及到一个新的概念抽象基类，什么是抽象基类呢？

对于抽象基类，目前可以不用关注太多，只需知道抽象基类是指不能实例化产生实例对象的类，后面有机会我们再专门来讨论抽象基类。

Sequence和MutableSequence是两个抽象基类，因此这两个类都是不能实例化产生实例对象，那要Sequence和MutableSequence两个抽象基类还有什么作用呢？

其实抽象基类的作用并不是实例化产生实例对象的，它的作用更多的像是定义一种规则，或者官方的说法叫做协议，这样以后我们希望创建这种类型的对象时，要求遵循这种规则或者协议。现在我们需要了解序列类型都有哪些协议，这需要学习abc模块中的Sequence和MutableSequence两个类。

Sequence和MutableSequence两个类的继承关系如下：

图中粗体表示抽象基类，斜体表示抽象方法，不妨理解为并未做具体实现的方法，剩下的为抽象基类中已经实现的方法。

可以看到，这里面的继承关系并不复杂，但是信息量很大，应该牢记这个图，因为这对理解序列类型非常重要。我们看到，可变序列MutableSequence类继承自不可变序列Sequence类，Sequence类又继承了两个类Reversible和Collection，Collection又继承自Container、 Iterable、Sized三个抽象基类。通过这个继承图，我们至少应该能够知道，对于标准不可变序列类型Sequence，应该至少实现以下几种方法（遵循这些协议）：

__contains__,__iter__，__len__，__reversed__，__getitem__，index，count

这几个方法到底意味着什么呢？在前面的list的实现源码里面我们可以窥探一二：

实现了__contains__方法，就意味着list可以进行成员运算，即使用in和not in的效果
实现了__iter__方法，意味着list是一个可迭代对象，可以进行for循环、拆包、生成器表达式等多种运算
实现了__len__方法，意味着可以使用内置函数len()。同时，当判断一个list的布尔值时，如果list没有实现__bool__方法，也会尝试调用__len__方法
实现了__reversed__方法，意味着可以实现反转操作
实现了__getitem__方法，意味着可以进行索引和切片操作
实现了index和count方法，则表示可以按条件取索引和统计频数。

标准的Sequence类型声明了上述方法，这意味着继承自Sequence的子类，其实例化产生的对象将是一个可迭代对象、可以使用for循环、拆包、生成器表达式、in、not in、索引、切片、翻转等等很多操作。这同时也表明，如果我们说一个对象是不可变序列时，暗示这个对象是一个可迭代对象、可以使用for循环、......。

而对于标准可变序列MutableSequence，我们发现，除了要实现不可变序列中几种方法之外，至少还需要实现如下几个方法（遵循这些协议）：

__setitem__,__delitem__,insert,append,extend,pop,remove,__iadd__

这几个方法又意味着什么呢？同样以Python的内置类型list为例进行说明：

实现了__setitem__方法，就可以对列表中的元素进行修改，如a = [1,2]，代码a[0]=2就是在调用这个方法
实现了__delitem__,pop,remove方法，就可以对列表中的元素进行删除，如a = [1,2]，代码del a[0]就是在调用__delitem__方法
实现了insert,append,extend方法，就可以在序列中插入元素
实现了__iadd__方法，列表就可以进行增量赋值

这就是说，对于标准可变序列类型，除了执行不可变类型的查询操作之外，其子类的实例对象都可以执行增删改的操作。

抽象基类Sequence和MutableSequence声明了对于一个序列类型应该实现那些方法，很显然，如果一个类直接继承自Sequence类，内部也重载了Sequence中的七个方法，那么显然这个类一定是序列类型了，MutableSequence的子类也是一样。确实如此，但是当我们查看列表list、字符序列str、元组tuple的继承链时，发现在其mro列表中并没有Sequence和MutableSequence类，也就是说，这些内置类型并没有直接继承自这两个抽象基类，那么为什么我们在文章的开头还要说他们都是序列类型呢？

>>> list.__mro__
(<class 'list'>, <class 'object'>)
>>> tuple.__mro__
(<class 'tuple'>, <class 'object'>)
>>> str.__mro__
(<class 'str'>, <class 'object'>)
>>> dict.__mro__
(<class 'dict'>, <class 'object'>)

其实，Python中有一种被称为鸭子类型的编程风格。在这种风格下，我们并不太关注一个对象的类型是什么，它继承自那个类型，而是关注他能实现那些功能，定义了那些方法。正所谓如果一个东西看起来像鸭子，走起来像鸭子，叫起来像鸭子，那他就是鸭子。

在这种思想之下，如果一个类并不是直接继承自Sequence，但是内部却实现了__contains__、__iter__、__len__、__reversed__、__getitem__、index，count几个方法，我们就可以称之为不可变序列。甚至都不必这么严格，可能只需要实现__len__，__getitem__两个方法就可以称作是不可变序列类型。对于可变序列也同样如此。

鸭子类型的思想贯穿了Python面向对象编程的始终。

Generic

这个类其实就是泛型的实现，从注释中可以发现，这个其实也是抽象基类，本质上用来实现多类型参数输入。比如在list中我们可以既存入int，又可以是str，还可以是list，也可以是dict等等多个不同类型的元素，这个本质上就是依赖于这个类的继承。

class Generic:
    """Abstract base class for generic types.

    A generic type is typically declared by inheriting from
    this class parameterized with one or more type variables.
    For example, a generic mapping type might be defined as::

      class Mapping(Generic[KT, VT]):
          def __getitem__(self, key: KT) -> VT:
              ...
          # Etc.

    This class can then be used as follows::

      def lookup_name(mapping: Mapping[KT, VT], key: KT, default: VT) -> VT:
          try:
              return mapping[key]
          except KeyError:
              return default
    """
    __slots__ = ()
    _is_protocol = False

    @_tp_cache
    def __class_getitem__(cls, params):
        if not isinstance(params, tuple):
            params = (params,)
        if not params and cls is not Tuple:
            raise TypeError(
                f"Parameter list to {cls.__qualname__}[...] cannot be empty")
        msg = "Parameters to generic types must be types."
        params = tuple(_type_check(p, msg) for p in params)
        if cls in (Generic, Protocol):
            # Generic and Protocol can only be subscripted with unique type variables.
            if not all(isinstance(p, TypeVar) for p in params):
                raise TypeError(
                    f"Parameters to {cls.__name__}[...] must all be type variables")
            if len(set(params)) != len(params):
                raise TypeError(
                    f"Parameters to {cls.__name__}[...] must all be unique")
        else:
            # Subscripting a regular Generic subclass.
            _check_generic(cls, params, len(cls.__parameters__))
        return _GenericAlias(cls, params)

    def __init_subclass__(cls, *args, **kwargs):
        super().__init_subclass__(*args, **kwargs)
        tvars = []
        if '__orig_bases__' in cls.__dict__:
            error = Generic in cls.__orig_bases__
        else:
            error = Generic in cls.__bases__ and cls.__name__ != 'Protocol'
        if error:
            raise TypeError("Cannot inherit from plain Generic")
        if '__orig_bases__' in cls.__dict__:
            tvars = _collect_type_vars(cls.__orig_bases__)
            # Look for Generic[T1, ..., Tn].
            # If found, tvars must be a subset of it.
            # If not found, tvars is it.
            # Also check for and reject plain Generic,
            # and reject multiple Generic[...].
            gvars = None
            for base in cls.__orig_bases__:
                if (isinstance(base, _GenericAlias) and
                        base.__origin__ is Generic):
                    if gvars is not None:
                        raise TypeError(
                            "Cannot inherit from Generic[...] multiple types.")
                    gvars = base.__parameters__
            if gvars is not None:
                tvarset = set(tvars)
                gvarset = set(gvars)
                if not tvarset <= gvarset:
                    s_vars = ', '.join(str(t) for t in tvars if t not in gvarset)
                    s_args = ', '.join(str(g) for g in gvars)
                    raise TypeError(f"Some type variables ({s_vars}) are"
                                    f" not listed in Generic[{s_args}]")
                tvars = gvars
        cls.__parameters__ = tuple(tvars)

蓦然回首

作为一个常用数据结构，在很多场景中被用来当做数组使用，可能很多时候都觉得list无非就是一个动态数组，就像C++中的vector或者Go中的slice一样。从源码的实现中，我们也可以发现list继承MutableSequence并且拥有泛型的效果，但这样就可以断言说list就是一个动态数组吗？

我们来思考一个简单的问题，Python中的list允许我们存储不同类型的数据，既然类型不同，那内存占用空间就就不同，不同大小的数据对象又是如何"存入"数组中呢？

我们可以分别在数组中存储了一个字符串，一个整形，以及一个字典对象，假如是数组实现，则需要将数据存储在相邻的内存空间中，而索引访问就变成一个相当困难的事情了，毕竟我们无法猜测每个元素的大小，从而无法定位想要的元素位置。

是否是通过链表结构实现的呢? 毕竟链表支持动态的调整，借助于指针可以引用不同类型的数据，比如下面的图示中的链表结构。但是这样的话使用下标索引数据的时候，需要依赖于遍历的方式查找，O(n)的时间复杂度访问效率实在是太低。

不过对于链表的使用，系统开销也较大，毕竟每个数据项除了维护本地数据指针外，还要维护一个next指针，因此还要额外分配8字节数据，同时链表分散性使其无法像数组一样利用CPU的缓存来高效的执行数据读写。

我们这个时候再来推敲一下list这个结构的内部实现，笔者接下来的推演都是基于CPython来的，不同语言的实现语法应该是不同的，不过思路大同小异。

Python中的list数据结构实现要更比想象的更简单且纯粹一些，保留了数组内存连续性访问的方式，只是每个节点存储的不是实际数据，而是对应数据的指针，以一个指针数组的形式来进行存储和访问数据项，对应的结构如下面图示：

实现的细节可以从其Python的源码中找到，定义如下：

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

内部list的实现的是一个C结构体，该结构体中的ob_item是一个指针数组，存储了所有对象的指针数据，allocated是已分配内存的数量, PyObject_VAR_HEAD是一个宏扩展包含了更多扩展属性用于管理数组，比如引用计数以及数组大小等内容。

动态数组

既然是一个动态数组，则必然会面临一个问题，即如何进行容量的管理，大部分的程序语言对于此类结构使用动态调整策略，也就是当存储容量达到一定阈值的时候，扩展容量，当存储容量低于一定的阈值的时候，缩减容量。道理很简单，不过实施起来可没那么容易，什么时候扩容，扩多少，什么时候执行回收，每次又要回收多少空闲容量，这些都是在实现过程中需要明确的问题。

对于Python中list的动态调整规则程序中定义如下：当追加数据容量已满的时候，通过下面的方式计算再次分配的空间大小，创建新的数组，并将所有数据复制到新的数组中。这是一种相对数据增速较慢的策略，回收的时候则当容量空闲一半的时候执行策略，获取新的缩减后容量大小。其实这个方式就很像TCP的滑动窗口的机制

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
 
new_allocated += newsize
//  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

假如我们使用一种最简单的策略：超出容量加倍，低于一半容量减倍。这种策略会有什么问题呢？设想一下当我们在容量已满的时候进行一次插入，随即删除该元素，交替执行多次，那数组数据岂不是会不断的被整体复制和回收，已经无性能可言了。

append

接下来，我们来看下list数据结构的几个常见操作。首先是在list上执行append的操作，该函数将元素添加到list的尾部。注意这里是指针数据被追加到尾部，而不是实际元素。

test = list()
test.append("hello yerik")

向列表添加字符串：test.append("hello yerik") 时发生了什么？实际上是调用了底层的 C 函数 app1()。

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，此时数组的大小为0，为了能够插入元素，我们需要对数组进行扩容，按照上面的计算公式进行调整大小。比如这时候只有一个元素，那么newsize = 1, 计算的new_allocated = 3 + 1 = 4 ，成功插入元素后，直到插入第五元素之前我们都不需要重新分配新的空间，从而避免频繁调用 list_resize() 函数，提升程序性能。

我们尝试继续添加更多的元素到列表中，当我们插入元素"abc"的时候，其内部数组大小不足以容纳该元素，执行新一轮动态扩容，此时newsize = 5 , new_allocated = 3 + 5 = 8

>>> test.append(520)
>>> test.append(dict())
>>> test.append(list())
>>> test.append("abc")
>>> test
['hello yerik', 520, {}, [], 'abc']

执行插入后的数据存储空间分布如下图所示：

insert

在列表偏移量 2 的位置插入新元素，整数 5：test.insert(1,2.33333333)，内部调用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实现的insert函数接收两个参数，第一个是指定插入的位置，第二个为元素对象。中间插入会导致该位置后面的元素进行移位操作，由于是存储的指针因此实际的元素不需要进行位移，只需要位移其指针即可。

>>> test.insert(2,2.33333333)
>>> test
['hello yerik', 520, 2.33333333, {}, [], 'abc']

插入元素为一个字符串对象，创建该字符串并获得其指针（ptr5）, 将其存入索引为2的数组位置中，并将其余后续元素分别移动一个位置即可，insert函数调用完成。正是由于需要进行“检查扩容”的原因，从而导致了该操作的复杂度达到了O(n)，而不是链表所存在的O(1)

pop

取出列表最后一个元素即l.pop()，调用了 listpop() 函数。在 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

在链表中pop 操作的平均复杂度为 O(1)。不过由于可能需要进行存储空间大小的修改，因此导致复杂度上升

>>> test.pop()
'abc'
>>> test.pop()
[]
>>> test.pop()
{}
>>> test
['hello yerik', 520, 2.33333333]

末尾位置的元素被回收，指针清空，这时候长度为5，容量为8，因此不需要执行任何的回收策略。当我们继续执行三次pop使其长度变为3后，此时使用量低于了一半的容量，需要执行回收策略。回收的方式同样是利用上面的公式进行处理，比如这里新的大小为3，则返回容量大小为3+3 = 6 ，并非回收全部的空闲空间。

pop的操作也是需要进行检查缩小，因此也是导致复杂度为O(n)

Remove

remove函数会指定删除的元素，而该元素可以在列表中的任意位置。因此每次执行remove都必须先依次遍历数据项，进行匹配，直到找到对应的元素位置。执行删除可能会导致部分元素的迁移。Remove操作的整体时间复杂度为O(n)。

>>> test
['hello yerik', 520, 2.33333333]
>>> test.remove(520)
>>> test
['hello yerik', 2.33333333]

其实对于Python列表这种数据结构的动态调整，在其他语言中也都存在，只是大家可能在日常使用中并没有意识到，了解了动态调整规则，我们可以通过比如手动分配足够的空间，来减少其动态分配带来的迁移成本，使得程序运行的更高效。

另外如果事先知道存储在列表中的数据类型都相同，比如都是整形或者字符等类型，可以考虑使用arrays库，或者numpy库，两者都提供更直接的数组内存存储模型，而不是上面的指针引用模型，因此在访问和存储效率上面会更高效一些。

参考资料

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

登录后参与评论

0 条评论

热度