《流畅的Python》 读书笔记 第二章数据结构(2) 231011

2.5 对序列使用+和*

通常 + 号两侧的序列由相同类型的数据所构成，在拼接的过程中，两个被操作的序列都不会被修改，Python 会新建一个包含同样类型数据的序列来作为拼接的结果

+和*都遵循这个规律，不修改原有的操作对象，而是构建一个全新的序列

l1 = [1,2,3]
l2 = [4,5,6]
print(id(l1))
print(id(l2))
l3 = l1+l2
print(id(l3)) # 变了
l4 = l1 * 3
print(id(l4)) # 变了
print(id(l1)) # 没变
print(id(l2)) # 没变

2.5.1 建立由列表组成的列表

如果在 a * n 这个语句中，序列 a 里的元素是对其他可变对象的引用的话，你就需要格外注意了

你想用my_list = [[]] * 3 来初始化一个由列表组成的列表，但是你得到的列表里包含的 3 个元素其实是 3 个引用，而且这 3 个引用指向的都是同一个列表

这一段在Python官方的doc中就有描述

参考: https://docs.python.org/zh-cn/3.9/library/stdtypes.html#typesseq

board = [['_'] * 3 for i in range(3)]
print(board)
board[1][2] = 'X'
print(board) 

other_board = [['_'] * 3] * 3
print(other_board)
other_board[1][2] = 'X'
print(other_board) 

看完上面的代码，你知道结果是什么吗?

你要做啥，完全取决于你

# 第一个print
[['_', '_', '_'], ['_', '_', 'X'], ['_', '_', '_']]

# 第二个print
[['_', '_', 'X'], ['_', '_', 'X'], ['_', '_', 'X']]

2.6 序列的增量赋值

+= 背后的特殊方法是 __iadd__（用于“就地加法”）。但是如果一个类没有实现这个方法的话，Python 会退一步调用 __add__

看下面的示例代码就能很好的说明这段

class A:
    def __init__(self,age):
        self.age = age
    def __iadd__(self, other):
        print('calling iadd')
        self.age+=other.age
        return self

class B:
    def __init__(self,age):
        self.age = age
    def __add__(self, other):
        print('calling add')
        self.age+=other.age
        return self

a1 = A(1)
a2 = A(2)
a1+=a2 # calling iadd
print(a1.age) # 3

b1 = B(1)
b2 = B(2)
b1+=b2 # calling add
print(b1.age) # 3

a += b

对 可 变 序 列（ 例 如 list、bytearray 和 array.array）来说，a 会就地改动，就像调用了 a.extend(b) 一样

但是如果 a 没有实现__iadd__的话，a += b 这个表达式的效果就变得跟 a = a + b 一样了：首先计算 a + b，得到一个新的对象，然后赋值给 a。也就是说，在这个表达式中，变量名会不会被关联到新的对象，完全取决于这个类型有没有实现__iadd__这个方法

总体来讲，可变序列一般都实现了 __iadd__ 方法，因此 += 是就地加法。而不可变序列根本就不支持这个操作，对这个方法的实现也就无从谈起

我觉得说的有点啰嗦了，从"也就是说，在这个..."中的"这个"是有点歧义的。可以概括为

可变序列调用a+=b，就地加法，a不变

不可变序列调用a+=b，就会产生一个新的对象a(来自a+b的赋值)

看下面的例子，ae是不可变的， 因此做了+=后id都变了，而c是可变的，id没有变化

a = 1
b = 2
print(id(a))
a += b
print(id(a))

c = [1]
print(id(c))
d = [2]
c +=d
print(id(c))

e = 'e'
print(id(e))
f = 'f'
e +=f
print(id(e))

+= 的概念也适用于 *=，不同的是，后者相对应的是 __imul__

我在https://zhuanlan.zhihu.com/p/656429071 中对此参考官方文档详细的描述了

很重要的一句话

对不可变序列进行重复拼接操作的话，效率会很低，因为每次都有一个新对象，而解释器需要把原来对象中的元素先复制到新的对象里，然后再追加新的元素

2.6.1 一个关于+=的谜题

t = (1, 2, [30, 40])
t[2] += [50, 60]

到底会发生下面 4 种情况中的哪一种？
a. t 变成 (1, 2, [30, 40, 50, 60])。
b. 因为 tuple 不支持对它的元素赋值，所以会抛出 TypeError 异常。
c. 以上两个都不是。
d. a 和 b 都是对的。

这种问题一般来讲，不用想，肯定是a、b中的一个，c可能性不大，d怎么都不可能（又异常又正常）

可答案就是d

稍作改动你能看到异常也能看到改变后的t

t = (1, 2, [30, 40])
try:
    t[2] += [50, 60]
except TypeError as e:
    print(e)
    print(t)

书中还对此展开了字节码

>>> s = [1,2,[3,4]]
>>> s = (1,2,[30,40])
>>> b = [50,60]
>>> import dis
>>> dis.dis('s[2]+=b') # 此处 原文是s[a]
  1           0 LOAD_NAME                0 (s)
              2 LOAD_CONST               0 (2)
              4 DUP_TOP_TWO
              6 BINARY_SUBSCR①
              8 LOAD_NAME                1 (b)
             10 INPLACE_ADD②
             12 ROT_THREE
             14 STORE_SUBSCR③
             16 LOAD_CONST               1 (None)
             18 RETURN_VALUE

上面是我的结果，跟书中的不太一样(这种我就不懂了，懂的大神可以说说)

对上面的①②③作者阐述了

➊ 将 s[a] 的值存入 TOS（Top Of Stack，栈的顶端）。
➋ 计算 TOS += b。这一步能够完成，是因为 TOS 指向的是一个可变对象（也就是示例 2-15
里的列表）。
➌ s[a] = TOS 赋值。这一步失败，是因为 s 是不可变的元组（示例 2-15 中的元组 t）。

至此我得到了 3 个教训。
• 不要把可变对象放在元组里面。
• 增量赋值不是一个原子操作。我们刚才也看到了，它虽然抛出了异常，但还是完成了操作。
• 查看 Python 的字节码并不难，而且它对我们了解代码背后的运行机制很有帮助

难倒是不难，就是看不懂有点愁，背后都是C，全忘了~

有读者提出，如果写成 t[2].extend([50, 60]) 就能避免这个异常。确实是这样，但这个例子是为了
展示这种奇怪的现象而专门写的

2.7 list.sort方法和内置函数sorted

Python 的一个惯例：如果一个函数或者方法对对象进行的是就地改动，那它就应该返回None，好让调用者知道传入的参数发生了变动，而且并未产生新的对象

list.sort就是这么一个例子，还要random.shuffle等

以前有学员问为何返回是None，我总是回复，这个在于对方的设计，现在总算有了一个新的说辞，听着还蛮高大上的。

用返回 None 来表示就地改动这个惯例有个弊端，那就是调用者无法将其串联起来。而返回一个新对象的方法（比如说 str 里的所有方法）则正好相反，它们可以串联起来调用，从而形成连贯接口（fluent interface）。详情参见维基百科中有关连贯接口的讨论（https://en.wikipedia.org/wiki/Fluent_
interface）

我习惯称之为链式调用，就像selenium库中ActionChains类的API的调用

list.sort 方法还是 sorted 函数，都有两个可选的关键字参数

一个只有一个参数的函数 你会想到lambda吧~

作者给的例子

>>> fruits = ['grape', 'raspberry', 'apple', 'banana']
>>> sorted(fruits)
['apple', 'banana', 'grape', 'raspberry'] ➊
>>> fruits
['grape', 'raspberry', 'apple', 'banana'] ➋
>>> sorted(fruits, reverse=True)
['raspberry', 'grape', 'banana', 'apple'] ➌
>>> sorted(fruits, key=len)
['grape', 'apple', 'banana', 'raspberry'] ➍
>>> sorted(fruits, key=len, reverse=True)
['raspberry', 'banana', 'grape', 'apple'] ➎
>>> fruits
['grape', 'raspberry', 'apple', 'banana'] ➏
>>> fruits.sort() ➐
>>> fruits
['apple', 'banana', 'grape', 'raspberry'] ➑

我在https://zhuanlan.zhihu.com/p/658316452中也详细阐述了一些简单的用法

可选参数 key 还可以在内置函数 min() 和 max() 中起作用。另外，还有些标准库里的函数也接受这个参数，像 itertools.groupby() 和 heapq.nlargest() 等

headq示例代码

import heapq

# 创建一个列表  
numbers = [1,-4,3,10,-15,9]

# 使用 heapq.nlargest() 并设置 key 参数为 square（平方）  
largest_three = heapq.nlargest(3, numbers, key=lambda x: x ** 2)

print(largest_three)  # 输出：[-15, 10, 9]

groupby示例代码

from itertools import groupby

# 示例数据，假设这是一组学生的成绩记录，每个学生有姓名和数学成绩  
students = [('Alice', 90), ('Bob', 80), ('Charlie', 85), ('David', 90), ('Eva', 85)]

# 使用 lambda 函数将学生按照数学成绩进行分组  
grouped_students = groupby(sorted(students, key=lambda x: x[1]), key=lambda x: x[1])

# 遍历每个组并打印组名（数学成绩）和组中的学生列表  
for name, group in grouped_students:
    print(f"Group name: {name}")
    for student in group:
        print(f" - {student[0]}")

示例输出

Group name: 80
 - Bob
Group name: 85
 - Charlie
 - Eva
Group name: 90
 - Alice
 - David

2.8 用bisect来管理已排序的序列

bisect 模块包含两个主要函数，bisect 和 insort，两个函数都利用二分查找算法来在有序序列中查找或插入元素

2.8.1 用bisect来搜索

Bisection 二分法

bisect(haystack, needle)

• haystack 干草垛是一个已经排好序的序列

• needle是待插入的针

• 插入完毕后的newstack依然是有序的

• bisect(haystack, needle) 查找位置 index

• haystack.insert(index,needle) 来插入新值

• insort 可以一步到位，并且速度更快一些

• bisect默认情况下遇到等值，插入到右侧(bisect = bisect_right)，bisect_left可以插入到左侧

• bisect_right(a, x, lo=0, hi=None) 完整的有4个参数，lo默认是0即第一个数，hi默认是len(a)

作者给的代码，稍作更改

import bisect
import sys
HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]
ROW_FMT = 'Needle: {0:2d} ,index: {1:2d}==> {2}{0:<2d}'
def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle) #➊
        offset = position * ' |' #➋
        print(ROW_FMT.format(needle, position, offset)) #➌
if __name__ == '__main__':
    if sys.argv[-1] == 'left': #➍
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect
    print('DEMO:', bisect_fn.__name__) #➎
    print('haystack ->')
    print('                        ',' '.join('%2d' % n for n in HAYSTACK))
    demo(bisect_fn)

作者的解释

➊ 用特定的 bisect 函数来计算元素应该出现的位置。
➋ 利用该位置来算出需要几个分隔符号。
➌ 把元素和其应该出现的位置打印出来。
➍ 根据命令上最后一个参数来选用 bisect 函数。
➎ 把选定的函数在抬头打印出来

你可能看到的输出是这样的

DEMO: bisect_right
haystack ->
                          1  4  5  6  8 12 15 20 21 23 23 26 29 30
Needle: 31 ,index: 14==>  | | | | | | | | | | | | | |31
Needle: 30 ,index: 14==>  | | | | | | | | | | | | | |30
Needle: 29 ,index: 13==>  | | | | | | | | | | | | |29
Needle: 23 ,index: 11==>  | | | | | | | | | | |23
Needle: 22 ,index:  9==>  | | | | | | | | |22
Needle: 10 ,index:  5==>  | | | | |10
Needle:  8 ,index:  5==>  | | | | |8 
Needle:  5 ,index:  3==>  | | |5 
Needle:  2 ,index:  1==>  |2 
Needle:  1 ,index:  1==>  |1 
Needle:  0 ,index:  0==> 0 

你可以执行python demo.py left 得到不一样的结果，这个代码接受参数，只不过它处理的 是最后一个参数if sys.argv[-1] == 'left':

bisect一个经典的案例，我在https://www.liujiangblog.com/course/python/57也看到过，第一次见的时候觉得还蛮厉害的，后来发现在官网就有了，https://docs.python.org/3/library/bisect.html

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
... i = bisect.bisect(breakpoints, score)
... return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

通过计算score在breakpoints中的位置，得到对应grades(必须要与breakpoints对应)的等级

虽然你可以用字典来做，但这个方法也是非常不错的案例

拓展阅读

Raymond Hettinger 写了一个排序集合模块（http://code.activestate.com/recipes/577197-sortedcollection

2.8.2 用bisect.insort插入新元素

insort(seq, item) 把变量 item 插入到序列 seq 中，并能保持 seq 的升序顺序

import bisect
import random
SIZE=7
random.seed(1729)
my_list = []
for i in range(SIZE):
    new_item = random.randrange(SIZE*2)
    bisect.insort(my_list, new_item)
    print('%2d ->' % new_item, my_list)

输出

10 -> [10]
 0 -> [0, 10]
 6 -> [0, 6, 10]
 8 -> [0, 6, 8, 10]
 7 -> [0, 6, 7, 8, 10]
 2 -> [0, 2, 6, 7, 8, 10]
10 -> [0, 2, 6, 7, 8, 10, 10]

insort的源码很简单，底层就是bisect_right或bisect_left得到索引后用a.insert来插入

def insort_right(a, x, lo=0, hi=None):
    lo = bisect_right(a, x, lo, hi)
    a.insert(lo, x)

def insort_left(a, x, lo=0, hi=None):
    lo = bisect_left(a, x, lo, hi)
    a.insert(lo, x)
insort = insort_right

insort 跟 bisect 一样，有 lo 和 hi 两个可选参数用来控制查找的范围

目前所提到的内容都不仅仅是对列表或者元组有效，还可以应用于几乎所有的序列类型上

如果是所有的序列类型，那从源码看，你得支持.insert才可以，元组其实就不支持了，你要实现必须转换下

2.9 当列表不是首选时

要存放1000 万个浮点数的话，数组（array）的效率要高得多，因为数组在背后存的并不是 float
对象，而是数字的机器翻译，也就是字节表述

如果需要频繁对序列做先进先出的操作，deque（双端队列）的速度应该会更快。

如果在你的代码里，包含操作（比如检查一个元素是否出现在一个集合中）的频率很高，用 set（集合）会更合适

用什么数据结构是应该利用数据结构的特点再结合你的应用场景而定的

下面这几个我工作中反正是几乎没用过

2.9.1 数组 array

我也是一直把Python的list当做array来处理的，其实不然

如果我们需要一个只包含数字的列表，那么 array.array 比 list 更高效

数组支持所有跟可变序列有关的操作，包括 .pop、.insert 和 .extend。另外，数组还提供从文件读取和存
入文件的更快的方法，如 .frombytes 和 .tofile。

在Python的array.array函数中，第一个参数是一个表示类型的代码，它决定了数组中元素的数据类型。以下是可以使用的类型代码：

• 'b'：布尔型（Boolean），取值为True（1）或False（0）。
• 'B'：无符号布尔型（Unsigned Byte），取值为0或1。
• 'u'：Unicode字符（Unicode Character）。
• 'i'：有符号整数（Signed Integer）。
• 'I'：无符号整数（Unsigned Integer）。
• 'l'：长整数（Long Integer）。
• 'L'：无符号长整数（Unsigned Long Integer）。
• 'f'：浮点数（Floating Point）。
• 'd'：十进制浮点数（Decimal Floating Point）。
• 'g'：十进制浮点数或定点数（General Purpose）。

这些类型代码的长度也代表了数组中元素的数据类型的长度，例如'i'代表的是有符号的整数类型，长度为当前平台下int的对齐长度，而'B'则代表的是无符号的8位整数类型。

请注意，创建的数组只能包含一种数据类型的元素。

array('b') 创建出的数组就只能存放一个字节大小的整数，范围从 -128 到127，这样在序列很大的时候，我们能节省很多空间。而且 Python 不会允许你在数组里存放除指定类型之外的数据

书中给出的代码(稍作更改)

from array import array # 1
from random import random
floats1 = array('d', (random() for i in range(10**7))) # 2
print(floats1[-1]) # 3

with open('floats.bin', 'wb') as fp1: # 4
    floats1.tofile(fp1)

floats2 = array('d') # 5
with open('floats.bin', 'rb') as fp2:
    floats2.fromfile(fp2, 10**7) # 6

print(floats2[-1]) # 7
print(floats1 == floats2) # 8

➊ 引入 array 类型。
➋ 利用一个可迭代对象来建立双精度浮点数组（类型码是 'd'），这里我们用的可迭代对象是一个生成器表达式。
➌ 查看数组的最后一个元素。
➍ 把数组存入一个二进制文件里。
➎ 新建一个双精度浮点空数组。
➏ 把 1000 万个浮点数从二进制文件里读取出来。
➐ 查看新数组的最后一个元素。
➑ 检查两个数组的内容是不是完全一样。

划下重点

1. 用 array.fromfile 从一个二进制文件里读出 1000 万个双精度浮点数只需要 0.1 秒，这比从文本文件里读取的速度要快60 倍。
2. 使用 array.tofile 写入到二进制文件，比以每行一个浮点数的方式把所有数字写入到文本文件要快 7倍
3. 1000 万个这样的数在二进制文件里只占用 80 000 000 个字节（每个浮点数占用8 个字节，不需要任何额外空间），如果是文本文件的话，我们需要 181 515 739 个字节(20多倍)

另外一个快速序列化数字类型的方法是使用 pickle（https://docs.python.org/3/library/pickle.html）模块。pickle.dump 处理浮点数组的速度几乎跟 array.tofile 一样快。不过前者可以处理几乎所有的内置数字类型，包含复数、嵌套集合，甚至用户自定义的类。前提是这些类没有什么特别复杂的实现

从 Python 3.4 开始，数组（array）类型不再支持诸如 list.sort() 这种就地排序方法

要给数组排序的话，得用 sorted 函数新建一个数组：a = array.array(a.typecode, sorted(a))

2.9.2 内存视图 memoryview

memoryview 是一个内置类，它能让用户在不复制内容的情况下操作同一个数组的不同切片

在数据结构之间共享内存。其中数据结构可以是任何形式，比如 PIL 图片、SQLite数据库和 NumPy 的数组，等等。这个功能在处理大型数据集合的时候非常重要

示例 2-21 : 通过改变数组中的一个字节来更新数组里某个元素的值

>>> numbers = array.array('h', [-2, -1, 0, 1, 2])
>>> memv = memoryview(numbers) ➊
>>> len(memv)
5
>>> memv[0] ➋
-2
>>> memv_oct = memv.cast('B') ➌
>>> memv_oct.tolist() ➍
[254, 255, 255, 255, 0, 0, 1, 0, 2, 0]
>>> memv_oct[5] = 4 ➎
>>> numbers
array('h', [-2, -1, 1024, 1, 2]) ➏

➊ 利用含有 5 个短整型有符号整数的数组（类型码是 'h'）创建一个 memoryview。
➋ memv 里的 5 个元素跟数组里的没有区别。
➌ 创建一个 memv_oct，这一次是把 memv 里的内容转换成 'B' 类型，也就是无符号字符。
➍ 以列表的形式查看 memv_oct 的内容。
➎ 把位于位置 5 的字节赋值成 4。
➏ 因为我们把占 2 个字节的整数的高位字节改成了 4，所以这个有符号整数的值就变成
了 1024。

2.9.3 NumPy和SciPy

这部分多少有点跑偏，简单瞄一眼就行了，我基本就是CTRL+C/V

凭借着 NumPy 和 SciPy 提供的高阶数组和矩阵操作，Python 成为科学计算应用的主流语言

NumPy 实现了多维同质数组（homogeneous array）和矩阵，这些数据结构不但能处理数字，还能存放其他由用户定义的记录

SciPy 是基于 NumPy 的另一个库，它提供了很多跟科学计算有关的算法，专为线性代数、数值积分和统计学而设计

SciPy 把基于C 和 Fortran 的工业级数学计算功能用交互式且高度抽象的 Python 包装起来

这些跟计算有关的部分都源自于 Netlib 库（http://www.netlib.org）

示例 2-22：NumPy 二维数组的基本操

>>> import numpy ➊
>>> a = numpy.arange(12) ➋
>>> a
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
>>> type(a)
<class 'numpy.ndarray'>
>>> a.shape ➌
(12,)
>>> a.shape = 3, 4 ➍
>>> a
array([[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11]])
>>> a[2] ➎
array([ 8, 9, 10, 11])
>>> a[2, 1] ➏
9
>>> a[:, 1] ➐
array([1, 5, 9])
>>> a.transpose() ➑
array([[ 0, 4, 8],
[ 1, 5, 9],
[ 2, 6, 10],
[ 3, 7, 11]])

➊ 安装 NumPy 之后，导入它（NumPy 并不是 Python 标准库的一部分）。
➋ 新建一个 0~11 的整数的 numpy.ndarray，然后把它打印出来。
➌ 看看数组的维度，它是一个一维的、有 12 个元素的数组。
➍ 把数组变成二维的，然后把它打印出来看看。
➎ 打印出第 2 行。
➏ 打印第 2 行第 1 列的元素

➐ 把第 1 列打印出来。
➑ 把行和列交换，就得到了一个新数组

>>> import numpy
>>> floats = numpy.loadtxt('floats-10M-lines.txt') ➊
>>> floats[-3:] ➋
array([ 3016362.69195522, 535281.10514262, 4566560.44373946])
>>> floats *= .5 ➌
>>> floats[-3:]
array([ 1508181.34597761, 267640.55257131, 2283280.22186973])
>>> from time import perf_counter as pc ➍
>>> t0 = pc(); floats /= 3; pc() - t0 ➎
0.03690556302899495
>>> numpy.save('floats-10M', floats) ➏
>>> floats2 = numpy.load('floats-10M.npy', 'r+') ➐
>>> floats2 *= 6
>>> floats2[-3:] ➑
memmap([3016362.69195522, 535281.10514262, 4566560.44373946])

➊ 从文本文件里读取 1000 万个浮点数。
➋ 利用序列切片来读取其中的最后 3 个数。
➌ 把数组里的每个数都乘以 0.5，然后再看看最后 3 个数。
➍ 导入精度和性能都比较高的计时器（Python 3.3 及更新的版本中都有这个库）。
➎ 把每个元素都除以 3，可以看到处理 1000 万个浮点数所需的时间还不足 40 毫秒。
➏ 把数组存入后缀为 .npy 的二进制文件。
➐ 将上面的数据导入到另外一个数组里，这次 load 方法利用了一种叫作内存映射的机制，
它让我们在内存不足的情况下仍然可以对数组做切片。
➑ 把数组里每个数乘以 6 之后，再检视一下数组的最后 3 个数

2.9.4 双向队列和其他形式的队列

利用 .append 和 .pop 方法，我们可以把列表当作栈或者队列来用（比如，把 .append和 .pop(0) 合起来用，就能模拟队列的“先进先出”的特点）

此处贴一下LeetCode 232 用栈实现队列的某个题解，你能很好的理解上面这句话

class MyQueue:

    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)

    def pop(self) -> int:
        peek = self.peek()
        self.B.pop()
        return peek

    def peek(self) -> int:
        if self.B: return self.B[-1]
        if not self.A: return -1
        # 将栈 A 的元素依次移动至栈 B
        while self.A:
            self.B.append(self.A.pop())
        return self.B[-1]

    def empty(self) -> bool:
        return not self.A and not self.B

但是删除列表的第一个元素（抑或是在第一个元素之前添加一个元素）之类的操作是很耗时的，因为这些操作会牵扯到移动列表里的所有元素。

常见的列表操作的复杂度

collections.deque 类（双向队列）是一个线程安全、可以快速从两端添加或者删除元素的数据类型。而且如果想要有一种数据类型来存放“最近用到的几个元素”，deque 也是一个很好的选择

示例 2-23 使用双向队列

>>> from collections import deque
>>> dq = deque(range(10), maxlen=10) ➊
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.rotate(3) ➋
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq[1]
8
>>> dq[-1]
6
>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
>>> dq.appendleft(-1) ➌
>>> dq
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.extend([11, 22, 33]) ➍
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)
>>> dq.extendleft([10, 20, 30, 40]) ➎
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

➊ maxlen 是一个可选参数，代表这个队列可以容纳的元素的数量，而且一旦设定，这个属性就不能修改了。
➋ 队列的旋转操作接受一个参数 n，当 n > 0 时，队列的最右边的 n 个元素会被移动到队列的左边。当 n < 0 时，最左边的 n 个元素会被移动到右边。
➌ 当试图对一个已满（len(d) == d.maxlen）的队列做头部appendleft添加操作的时候，它尾部的元素会被删除掉。注意在下一行里，元素 0 被删除了。
➍ 在尾部添加 3 个元素的操作会挤掉 -1、1 和 2(就是前三个)。
➎ extendleft(iter) 方法会把迭代器里的元素逐个添加到双向队列的左边，因此迭代器里的元素会逆序出现在队列里。这非常有特点

双向队列实现了大部分列表所拥有的方法，也有一些额外的符合自身设计的方法，比如说
popleft 和 rotate。但是为了实现这些方法，双向队列也付出了一些代价，从队列中间删
除元素的操作会慢一些，因为它只对在头尾的操作进行了优化。
append 和 popleft 都是原子操作，也就说是 deque 可以在多线程程序中安全地当作先进先
出的队列使用，而使用者不需要担心资源锁的问题

a_list.pop(p) 这个操作只能用于列表，双向队列的这个方法不接收参数

其他形式的队列的实现

2.10 本章小结

Python 序列类型最常见的分类就是可变和不可变序列

另外一种分类方式 扁平序列和容器序列

前者的体积更小、速度更快而且用起来更简单，但是它只能保存一些原子性的数据，比如数字、字符和字节

后者更加灵活，如果用到可变对象，还要嵌套的数据结构，尤其要注意

列表推导和生成器表达式则提供了灵活构建和初始化序列的方式

元组它既可以用作无名称的字段的记录，又可以看作不可变的列表

前者的使用中，拆包是一个典型的做法，*句法更加便利

具名元组的实例也很节省空间，同时提供了方便地通过名字来获取元组各个字段信息的方式

Python 里最受欢迎的一个语言特性就是序列切片

用户自定义的序列类型也可以选择支持 NumPy 中的多维切片和省略（...）

对切片赋值是一个修改可变序列的捷径

增量赋值 += 和 *= 会区别对待可变和不可变序列

在遇到不可变序列时，这两个操作会在背后生成新的序列。但如果被赋值的对象是可变的，那么这个序列会就地修改

序列的 sort 方法和内置的 sorted 函数，都接受一个函数作为可选参数来指定排序算法如何比较大小

这个参数名为key

如果在插入新元素的同时还想保持有序序列的顺序，那么需要用到 bisect.insort。bisect.bisect 的作用则是快速查找

返回索引

2.11 延伸阅读

ABC 里的 compounds 类型算得上是 Python 元组的鼻祖

容器”一词来自“Data Model”文档（https://docs.python.org/3/reference/datamodel.
html#objects-values-and-types）

有些对象里包含对其他对象的引用；这些对象称为容器

扁平序列因为只能包含原子数据类型，比如整数、浮点数或字符，所以不能嵌套使用

这个名字是本书作者创造的！主要是为了跟容器序列做对比

列表是可以同时容纳不同类型的元素的，但是实际上这样做并没有什么特别的好处

不推荐这么用

元组则恰恰相反，它经常用来存放不同类型的的元素

list.sort、sorted、max 和 min 函数的 key 参数是一个很棒的设计

用 key 参数能把事情变得简单且高效。

说它更简单，是因为只需要提供一个单参数函数来提取或者计算一个值作为比较大小的标准即可

说它更高效，是因为在每个元素上，key 函数只会被调用一次。

sorted 和 list.sort 背后的排序算法是 Timsort，它是一种自适应算法，会根据原始数据的顺序特点交替使用插入排序和归并排序，以达到最佳效率

https://en.wikipedia.org/wiki/Timsort

2009年起，Java 和 Android 也开始使用这个算法

Timsort 的创始人是 Tim Peters，也是“Python 之禅”（import this）的作者

本栏目推荐文章
• 2024/1/13 算法笔记
• Python学习笔记
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• HDP 笔记
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 学习进度笔记2
• 微软企业库Unity学习笔记(一)

数据结构 结构 第二章 笔记 数据数据结构 结构 第二章 数据 数据结构 结构 第二章 笔记 数据结构 算法 结构 第二章 数据结构 结构 笔记 数据 数据结构 大话 结构 笔记 线段 数据结构 结构 笔记 数据结构 区间 结构 笔记 数据结构 算法 结构 笔记 数据结构 结构 笔记 动画 多项式 数据结构 结构 笔记