deque 对象，快如闪电的双端队列

python

我们已经学习了 list 对象的内部结构，知道它底层是用动态数组实现的。在 list 头部进行插入或删除，都要挪动其后的所有数据，性能非常差！因此，我们不能将 list 对象作为队列使用。

好在 Python 标准库提供了另一种对象—— deque ，很好地补全了 list 的短板。deque 是一种类似 list 的线性表，但它在两端插入删除数据的时间复杂度都是 $O(1)$ ，因而可以作为队列来使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections imoprt deque

# 创建一个deque对象作为队列
q = deque()

# 数据入队：将其插到末尾
q.append(data)

# 数据出队：从头部弹出
data = q.popleft()

您可能会问了，deque 到底跟 list 有何不同？为何两端都能同时支持 $O(1)$ 的插入删除呢？

内部结构

这其中的秘密还得到源码中寻找。Python标准库位于源码中的 Lib 目录，collections 模块源码位于 Lib/collections 目录，模块入口文件为 Lib/collections/__init__.py 。打开 __init__.py 可以看到这段代码（ 29~34 行）：

1
2
3
4
5
6

try:
    from _collections import deque
except ImportError:
    pass
else:
    _collections_abc.MutableSequence.register(deque)

由此可见，deque 是在另一个模块 _collections 中实现的。我们在 Lib 中并没有找到 _collections 模块，它很有可能是一个用 C 语言实现的模块。我们回到 Modules 目录看一看，果然找到了 Modules/_collectionsmodule.c 。

这个源码文件就是 deque 实现之所在，不难找到 deque 对象底层结构体定义（ 71~96 行）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

这里的源码以 Python 3.7.4 版本为例，不同版本可能略有差异。

dequeobject 结构体便是 deque 实例对象的底层肉身，可以看到 deque 将自己保存的元素组织成链表结构，难怪在两端增删元素都很快！跟普通链表节点只保存一个元素不同，deque 的链表节点可以保存很多元素。

block 结构体就是 deque 内部的链表节点，顾名思义，它是一个内存块。block 结构体非常简单，只有 3 个字段：

  • leftlink ，左向指针，指向左边（更接近头部）的内存块；
  • rightlink ，右向指针，指向右边（更接近尾部）的内存块；
  • data ，对象指针数组，deque 中的元素就保存在这里；

内存块 block 由 leftlink 和 rightlink 字段串联，组成一个双向链表。 block 内存块中的 data 数组，长度由 BLOCKLEN 宏定义决定（ 第 21 行 ）：

1
2

#define BLOCKLEN 64
#define CENTER ((BLOCKLEN - 1) / 2)

由此可见，deque 每个链表节点可以保存 64 个元素，因此链表指针开销更小！

如果按照常规套路，每个节点只保存一个元素对象指针，却花费了两个链表指针，链表指针开销比有效数据还大！而按照 deque 的做法，每 64 个元素才花费 2 个链表指针，内存开销大大降低！

顺便提一下，CENTER 宏根据 BLOCKLEN 计算 data 数组中间元素的下标。

回到 deque 底层结构体 dequeobject ，它很显然是一个变长对象，包含变长对象公共字段 PyObject_VAR_HEAD 。除了公共头部，还包含 7 个字段：

  • leftblock ，链表头节点指针，指向双向链表中最左侧的 block 结构体；
  • rightblock ，链表尾节点指针，指向双向链表中最右侧的 block 结构体；
  • leftindex ，deque 最左元素，也就是第一个元素在 leftblock 数组中的下标；
  • rightindex ，deque 最右元素，也就是倒数第一个元素在 rightblock 数组中的下标；
  • state ，内部状态， deque 发生修改时加一（比较 state 在两个时间点的值，即可判断期间是否改动过）；
  • maxlen ，指定 deque 最大长度（可选），添加新元素时如果超过限制，便从另一端弹出等量的元素；
  • weakreflist ，deque 的弱引用链表头指针，具体用法请参考弱引用一节；

上图是一个 deque 实例对象内部结构图，它保存着 68 个元素，ob_size 字段为 68 。元素组织在一个双向链表中，每个节点都是一个 block 结构体，即蓝色部分。

每个 block 都有两个链表指针（浅蓝色），以及一个最多可以保存 64 个元素的对象数组 data 。例子中，中间的 block 是满的，最左和最后的 block 均只保存 2 个元素，灰色部分为空闲空间。

deque 最前面的元素位于 leftblock 中，其下标是 leftindex ，例子中为 62 ，即 data 数组倒数第二个；最后的元素位于 rightblock 中，其下标为 rightindex ，例子中为 1 ，即 data 数组第二个。

当我们调用 append 方法添加元素时，元素最终保存在 rightblock 中。例子中 data 数组仍有空闲空间，因此只需将 rightindex 加一，并将新元素保存在 data 数组对应位置。如果 data 数组已满，则需要分配一个新的 block ，并插在链表最右侧。

当我们调用 appendleft 方法添加元素时，元素最终保存在 leftblock 中。例子中 data 数组仍有空闲空间，因此只需将 leftindex 减一，并将新元素保存在 data 数组对应位置。同样如果 data 数组已满，需要分配一个新的 block ，并插在链表最左侧。

当我们调用 pop 方法移除元素时，尾部元素位于 rightblock 数组的 rightindex 位置。因此，只需将该位置的元素取出返回，并将 rightindex 减一。如果 rightindex 降为 -1 ，说明 rightblock 中的元素均已移除，这时可以将这个 block 从链表中移除并释放。

当我们通过下标访问 deque 元素，我们需要先遍历链表定位到目标元素所在 block ，然后再从 data 数组中取出。如果下标比较靠前，则从前往后遍历比较快；如果下标比较靠后，则从后往前遍历比较快。

假设 deque 长度为 $n$ ，由于一个 block 可以保存 64 个元素，因此链表长度为 $\frac{n}{64}$ 。我们根据下标定位元素，最多只需遍历一半节点，因此时间复杂度为 $O(\frac{n}{128})$ 。尽管这比 $O(n)$ 已经好很多了，但仍为线性时间，当元素较多时还是很慢！

掌握 deque 内部结构后，其常用操作的时间复杂度不难得出：

操纵方法 操作说明 时间复杂度
append 从尾部添加元素 $O(1)$
appendleft 从头部添加元素 $O(1)$
insert 从指定位置插入元素 $O(n)$
pop 从尾部移除元素 $O(1)$
popleft 从尾部移除元素 $O(1)$
[] 下标访问 $O(n)$

接下来，我们再讲解一些源码细节，有兴趣的话可以往下看。

实例创建

deque 类型对象全局只有一个实例，作为静态变量定义于 1638 行处：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

static PyTypeObject deque_type = {
    PyVarObject_HEAD_INIT(NULL, 0)
    "collections.deque",                /* tp_name */
    sizeof(dequeobject),                /* tp_basicsize */
    0,                                  /* tp_itemsize */
    /* methods */
    (destructor)deque_dealloc,          /* tp_dealloc */
    0,                                  /* tp_print */
    0,                                  /* tp_getattr */
    0,                                  /* tp_setattr */
    0,                                  /* tp_reserved */
    deque_repr,                         /* tp_repr */
    &deque_as_number,                   /* tp_as_number */
    &deque_as_sequence,                 /* tp_as_sequence */
    
    // 此处省略部分不讨论的字段

    deque_methods,                      /* tp_methods */
      
    // 此处省略部分不讨论的字段
    
    (initproc)deque_init,               /* tp_init */
    PyType_GenericAlloc,                /* tp_alloc */
    deque_new,                          /* tp_new */
    PyObject_GC_Del,                    /* tp_free */
};

关于实例对象和类型对象的区别和联系，请复习 Python 对象模型部分讲解，以加深理解。

根据前面章节学到的知识，我们知道 deque 实例对象由 tp_new 函数创建，即 deque_new 函数（ 146~176 行）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

static PyObject *
deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    dequeobject *deque;
    block *b;

    /* create dequeobject structure */
    deque = (dequeobject *)type->tp_alloc(type, 0);
    if (deque == NULL)
        return NULL;

    b = newblock();
    if (b == NULL) {
        Py_DECREF(deque);
        return NULL;
    }
    MARK_END(b->leftlink);
    MARK_END(b->rightlink);

    assert(BLOCKLEN >= 2);
    Py_SIZE(deque) = 0;
    deque->leftblock = b;
    deque->rightblock = b;
    deque->leftindex = CENTER + 1;
    deque->rightindex = CENTER;
    deque->state = 0;
    deque->maxlen = -1;
    deque->weakreflist = NULL;

    return (PyObject *)deque;
}

可以看到，Python 创建 deque 对象时，除了分配 dequeobject 结构体，还会预先分配一个内存块（第 12 行）。因此，一个空的 deque 实例对象，内部结构是这样的：

一个 dequeobject 结构体总共 10 个字段，每个字段 8 字节，总长度为 80 字节；一个 block 结构体包含一个长度 64 的指针数组，以及两个链表指针，总共 $(64+2)\times8=528$ 字节；每个需要垃圾收集的对象，还要在对象前预留一个 GC 时用的链表节点，大小为 32 字节（假设开启内存对齐）。

关于 GC 和可收集对象链表节点相关内容，请查阅内存管理部分章节。

因此，一个空的 deque 对象总共占用 $80+528+32=640$ 字节。我们可以验证一下，确实如此！

1
2
3

>>> from collections import deque
>>> sys.getsizeof(deque())
640

添加元素

deque 实例对象的方法在类型对象 deque_type 中定义，请看 tp_methods 字段，它被初始化成 deque_methods （第 1668 行）。deque_methods 是一个静态数组，定义于 1593 行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static PyMethodDef deque_methods[] = {
    {"append",                  (PyCFunction)deque_append,
        METH_O,                  append_doc},
    {"appendleft",              (PyCFunction)deque_appendleft,
        METH_O,                  appendleft_doc},
    {"clear",                   (PyCFunction)deque_clearmethod,
        METH_NOARGS,             clear_doc},
        
    // 以下省略
};

由此可见，append 方法底层由 deque_append 函数处理，而 appendleft 方法底层由 deque_appendleft 处理，其余方法也是类似的。我们以 appendleft 为例，看看 deque 是如何添加元素的。deque_appendleft 函数最终调用 deque_appendleft_internal 函数进行处理，位于在 305 行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static int
deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
{
    if (deque->leftindex == 0) {
        block *b = newblock();
        if (b == NULL)
            return -1;
        b->rightlink = deque->leftblock;
        CHECK_END(deque->leftblock->leftlink);
        deque->leftblock->leftlink = b;
        deque->leftblock = b;
        MARK_END(b->leftlink);
        deque->leftindex = BLOCKLEN;
    }
    Py_SIZE(deque)++;
    deque->leftindex--;
    deque->leftblock->data[deque->leftindex] = item;
    if (NEEDS_TRIM(deque, deque->maxlen)) {
        PyObject *olditem = deque_pop(deque, NULL);
        Py_DECREF(olditem);
    } else {
        deque->state++;
    }
    return 0;
}

这函数只有几个关键步骤，很容易理解：

  1. 第 15 行，将 ob_size 字段加一，表示 deque 元素增加一个；
  2. 第 16 行，将 leftindex 字段减一，扩张左边边界；
  3. 第 17 行，将新元素 item 保存在 data 数组对应位置；

如果 leftindex 等于 0 ，意味着当前 block 的数组空间已用完。这时需要新分配一个 block ，并插入到链表的最左边，具体请看第 4~14 行。

移除元素

我们在以 popleft 为例，看 deque 是如何移除元素的。它底层由 deque_popleft 函数处理（第 215 行）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

static PyObject *
deque_popleft(dequeobject *deque, PyObject *unused)
{
    PyObject *item;
    block *prevblock;

    if (Py_SIZE(deque) == 0) {
        PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
        return NULL;
    }
    assert(deque->leftblock != NULL);
    item = deque->leftblock->data[deque->leftindex];
    deque->leftindex++;
    Py_SIZE(deque)--;
    deque->state++;

    if (deque->leftindex == BLOCKLEN) {
        if (Py_SIZE(deque)) {
            assert(deque->leftblock != deque->rightblock);
            prevblock = deque->leftblock->rightlink;
            freeblock(deque->leftblock);
            CHECK_NOT_END(prevblock);
            MARK_END(prevblock->leftlink);
            deque->leftblock = prevblock;
            deque->leftindex = 0;
        } else {
            assert(deque->leftblock == deque->rightblock);
            assert(deque->leftindex == deque->rightindex+1);
            /* re-center instead of freeing a block */
            deque->leftindex = CENTER + 1;
            deque->rightindex = CENTER;
        }
    }
    return item;
}

deque_popleft 函数也很简单，它的逻辑刚好相反：

  1. 第 7~10 行，调用 Py_SIZE 检查 ob_size 看 deque 是否为空；
  2. 第 12 行，通过 leftblock 和 leftindex 定位待移除元素，并临时保存；
  3. 第 13 行，将 leftindex 加一，使得左边界右移一位；
  4. 第 14 行，调用 Py_SIZE 宏将 ob_size 字段减一，元素总数减少一个；
  5. 第 17~33 行，如果 leftblock 为空，将其从链表中移除，并释放；

注意到，如果元素移除后 deque 变为空（第 18 行），则不会将 leftblock 移除，而是保留待后续使用。同时，调整 leftindex 和 rightindex 指向 block 中间。后续不管从头部还是尾部添加元素，都有空闲空间可用，效率都能得到保障。

【Python源码剖析】系列文章首发于公众号【小菜学编程】，敬请关注：

【Python源码剖析】系列文章首发于公众号【小菜学编程】，敬请关注：

fasionchan 2020-09-28