《Python编程从0到1 视频教学版》_深入Python设计的本质_3.5 案例分析

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第5节，作者是张頔。

3.5 案例分析

各种基本的数据结构和算法首先被用来构建计算机软件世界的基础架构，如程序设计 语言本身、标准库、操作系统和数据库等。对数据结构和算法的深入学习也应当从这些主 题入手。本节以Python 的两种标准库类型 deque 和 OrderedDict 为例，向读者展示将各种 结构结合起来以获取综合优异性能的设计方法。 deque 将数组和链表结合起来构建队列缓 冲区，兼具动态扩展容量和优良的随机索引访问性能。 OrdredDict 则将双向循环列表与散 列表结合，实现有序的字典结构。

【学习目标】

· 进一步加深对基础数据结构的认识；

· 了解混合数种基础结构以构建复杂结构的方法。

3.5.1 deque 链表块

3.2.5节的链表队列在处理大量数据时会频繁地创建和释放节点对象。为了节省这些 操作带来的开销，可以用数据块作为基础单元， 一次分配“一大块”指针，将这些“指针 块”串接起来形成链表。 Python 标准库 collections 提供的deque 对象实现了这种模式。

1. 操作接口

使用如下代码创建一个 deque 对象：

dons import deque

在创建 deque 队列时可以使用可迭代对象进行初始化，或进一步指定最大长度。完整的构造函数如下：

deque([iterable[,maxlen]])--> deque object

从外观 (API) 上看， deque 与列表相比并无太多特别之处：

·append(x): 向队列右侧添加数据。

· appendleft(x): 向队列左侧添加数据。

· clear(): 清空队列。

· copy(): 浅拷贝。

· count(x):统计值为 x 的元素个数。

· extend(iterable): 向队列右侧依次插入可迭代对象给出的元素。

· extendleft(iterable): 向队列左侧依次插入可迭代对象给出的元素。

· index(x[,start[, stop]]): 搜索(在某范围内)x 首次出现的位置，如果没找到则抛出 ValueError异常。

· insert(i,x): 在位置 i插入x。

· pop(): 从右端移除并返回数据，如果队列为空，抛出IndexError异常。

· popleft(): 从左端移除并返回数据，如果队列为空，抛出IndexError异常。

· remove(value): 移除最先出现的值为 value 的节点，如果没有这样的节点，抛出 ValueError异常。

· reverse(): 原地翻转队列。

· rotate(n=1): 循环移位。

·maxlen: 队列最大长度，为 None 则无限制。

这些操作与列表虽不能完全对应，却也相去不远。如 appendleft(x)在列表中可以使用 insert(0,x)完成类似操作。但从内部结构上， deque 采用了如图3.46所示的实现。

Python 的典型实现 CPython 采用了64个引用一组的块结构作为 deque 内存分配的基 本单元，这些基本单元串接形成双向链表(非循环)。 deque 的内部结构维护最左和最右 的块指针 (leftblock/rightblock), 以及这两个块内的队头位置和队尾位置 (leftindex 和 rightindex)。

2. 性能测试

本小节介绍的 deque 类型相比列表类型，在头部插入操作的时间复杂度上占有阶 的优势，前者的头部插入的时间复杂度为 O(1), 后者为 O(n)。deque类型相比3.2.5节 的链表队列类型在头部插入上也占据优势，二者的时间复杂度的阶虽然相同，但前者 由于采用了批量分配内存和使用底层语言 (C) 实现，在性能上要高出一个数量级。用 以下3个程序(如代码3. 14～代码3. 16所示)对比在 list 头部插入和 deque 结构头部 插入的效率。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。