序列（Sequence）是存储有序数据的线性结构. Python内置的序列类型包括以字符串（str）、数组（array）和内存视图（memoryview）为代表的, 只能存储相同数据类型的扁平序列; 以及更常用的列表（list）、元组（tuple）、双端队列（deque）等能够存储不同类型数据的容器序列.

扁平序列类似于C语言中的数组, 其特点是在连续的内存空间中直接存储数据的值, 因此适用于紧凑地存储基本数据类型; 而容器序列中存储的却是对象的引用, 因此能够在不用打包和拆包的前提下存储不同类型的数据, 但代价是在访问数据时需要进行二次寻址.

而根据是否能够修改所存储的内容又可以将序列分为可变（Mutable）和不可变（Immutable）两类. Python在解释器层面限制了对元组、字符串和字节串（bytes）等不可变序列中元素的修改, 而像列表这种可变序列就没有这种限制. 但不可变序列的好处在于能够通过hash函数计算其哈希值, 因此可以被用于充当字典的键或者存储在集合中.

大部分序列类型都继承自抽象基类collections.abc.Sequence, 因此普遍支持如下表所示的通用操作:

但也有例外, 像区间（range）这类的迭代器序列就不支持直接拼接. 相同类型的序列之间也支持字典序比较, 只有在长度以及对应元素的值相同时, 两个序列才被认为相等.

列表

列表是内置的可变容器序列, 对每个列表对象来说, 其内部存储的是对应元素的引用, 例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
vtuber = ['mea', 'aqua', 'alice']

mea, aqua, alice = 'mea', 'aqua', 'alice'
vup = [mea, aqua, alice]

# True 两个列表中的元素指向的是同一段内存 都是引用
print(all(map(lambda x, y: x is y, vtuber, vup)))

# True 列表中对应元素的值相同
print(vtuber == vup)

# False 尽管容器内元素引用相同 但却是不同的列表对象
print(vtuber is vup)

尽管在初始化vtuber列表时直接使用字符串对象作为输入, 但在列表中却只记录了这些对象的引用, 因此其内部存储结构与通过传入字符串对象引用而构造的vup列表相同, 这一结论可以通过map函数的输出结果验证. 列表中可以存储任意类型, 这类似于C语言中的void*指针数组. 在访问列表中的元素时, 首先需要通过列表名访问列表的实际内存地址, 然后通过其中记录的元素引用获得元素的内容, 这个过程就是二次寻址.

事实上在Python中, 一切可交互的实体都是对象, 而对象的名字就是其引用. 在创建变量时, 必须让其指向某个已经创建好的对象, 例如:

1
2
3
4
5
6
7
8
9
10
11
r0, r1 = range(5), range(5)
# 二者指向了不同的对象
print(r0 is r1)  # False

r2 = r0
# 二者是相同对象的引用
print(r0 is r2)  # True

v0, v1 = 3.14, 3.14
# 数字和某些字符串会被小数据池缓存
print(v0 is v1)  # True

Python在设计时考虑到了频繁创建相同对象所带来的性能损耗, 因此提供了针对数字和部分字符串的缓存优化机制, 这部分内容可以参考小数据池与缓存.

列表的内存分配方式为运行时动态分配, 这类似于C++中的向量（vector）. 初始分配给列表的内存是连续的, 当内部元素数量饱和时就扩容50%左右. 默认情况下, 列表会在当前所处的堆空间后方继续申请连续的内存, 如果这段空间被占用, 则会新开辟一段连续的内存并迁移当前数据.

在数据量很大时, 通过列表推导式（list comprehension）构建列表的速度要远超直接使用外部循环的方法, 并且带有if代码块的列表推导式能够在一定程度上替换高阶函数filter. 例如, 获得所有名字长度大于5的姓名列表:

1
2
3
4
5
vtubers = ['miko', 'watame', 'fubuki', 'pekora']
print([name for name in vtubers if len(name) > 5])

# 也可以替换为 None
print([name if len(name) > 5 else None for name in vtubers])

列表推导式的优势在于代码简洁且可读性强, 但要注意的是, 列表推导式只适合于生成新的列表, 而不适用于在原有列表中进行修改. 为了防止被滥用, 建议在逻辑较为复杂时使用函数简化代码, 或者直接用外部循环重写. 例如, 通过列表推导式配合外部循环构造幂集:

1
2
3
4
5
res = [[]]

for num in range(3):
    # 每次拼接当前数字到列表中的所有元素
    res += [r + [num] for r in res]

和其他可变序列一样, 列表中提供了如下表所示的序列编辑操作:

熟练使用这些API不仅能显著提升开发效率, 还可以方便地实现其他线性数据结构. 例如: 通过insert和pop可以实现先入先出的队列, 但受限于列表的内存结构, 在头部插入数据时会导致全部数据向后移动, 因此更推荐使用对双端操作做了特殊优化的collections.deque队列, 更多内容请参考栈与队列.

元组

元组是内置的不可变容器序列, 其构造方法类似于列表, 但要注意区分生成器表达式（generator expression）与定义元组的方式.

1
2
3
4
5
6
7
8
# 定义一个元组
('paryi', 'mea', '2018-06-28')

# 元组构造函数接收可迭代对象
tuple(x for x in range(5))

# 这是生成器表达式 不是元组
(x for x in range(5))

元组中元素不变的性质让其适合于存放字段, 但匿名存放的字段会显著降低程序的可读性, 因此在结构较为复杂时建议使用命名元组. 标准库中提供的collections.namedtuple是一个工厂函数, 它可以用来构建一个带字段名的元组和一个有名字的类, 这非常有利于处理结构化的数据, 例如: 数据库的表结构、CSV文件的列名等.

1
2
3
4
5
6
7
Vtuber = namedtuple('Vtuber', ['name', 'age', 'company'])
mea = Vtuber('mea', 18, None)

# 可以通过下标和字段名访问元素
print(mea[0] is mea.name)  # True
print(mea)
# Vtuber(name='mea', age=18, company=None)

与其他序列类型相似, 元组也支持根据位置对元素赋值. 将多个变量合并为元组的过程被称为元组打包, 而将元组拆分为数个字段的过程被称为元组拆包. 在拆包时可以通过_过滤掉不想要的字段.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 元组打包
alice = '2434', 'Alice', '2018-03-06'

# 元组拆包 忽略日期字段
company, name, _ = alice

# 字符串拆包
a, b, c = "abc"

# 指向交换就是典型的先打包再拆包
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Python中函数的默认参数和可变参数都是以元组的形式传递, 而关键字参数则是以字典的方式传递. 实现可变参数的关键原理在于元组拆包时支持通过星号表达式重新打包任意数量的字段. 这种灵活的参数传递方式完全覆盖了函数重载的需求.

1
2
3
4
5
6
7
def drop_first_last(grades):
    # 等价于 middle = grades[1:-1]
    first, *middle, last = grades
    return avg(middle)

record = ('ACME', 50, 123.45, (12, 18, 2012))
name, *_, (*_, year) = record  # 嵌套元组拆包

在函数定义中使用*能够接受任意数量的位置参数, 使用**则能够接收任意数量的关键字参数, 所有未在默认参数列表中并以key=value形式赋值的参数都会被视为关键字参数, 此外, 如果位置参数有剩余则会自动按顺序赋值给默认参数.

1
2
3
4
5
6
7
def func(var1, *args, **kwargs):
    return var1, args, kwargs

print(func(*range(5), poi='poi'))
# (0, (1, 2, 3, 4), {'poi': 'poi'})
print(func(1, poi='poi'))
# (1, (), {'poi': 'poi'})

默认参数自动根据位置填充的性质可能会造成代码逻辑混乱, 因为你既可以通过关键字形式给默认参数赋值, 也可以直接根据位置赋值. 为了提升代码的可读性, 可以通过在位置参数中插入星号来让后续参数强制转变为关键字参数.

1
2
3
4
5
6
7
def recv(maxsize, tag='socket', *, block):
    return maxsize, tag, block

print(recv(1024, block=True))
# (1024, 'socket', True)
print(recv(4096, 'files', block=False))
# (4096, 'files', False)

元组的打包与拆包也可以在循环中使用. Python中提供了zip函数用于生成多个序列中对应下标元素的组合, 处理过程会自动截掉过长的序列元素. 需要注意的是, zip的输出结果是迭代器, 这意味着生成的序列组合不能被重复使用.

1
2
3
4
5
6
7
8
9
10
11
12
zipped = zip(names, ages)

# 迭代拆包
for name, _ in zipped:
    print(name)

# 生成的 zip 对象是一次性的
next(zipped)
# 迭代器为空 抛出异常

# 利用zip解包转置矩阵
list(zip(*matrix))

而标准库中的itertools.zip_longest函数则会根据参数fillvalue的值来补齐较短序列的缺失元素, 这意味着生成的可迭代对象长度取决于输入序列中最长的那个. 更多内容请参见标准库文档.

对可变序列执行增量赋值操作+=时相当于调用__iadd__方法, 而对元组和字符串这类的不可变序列来说, 增量赋值并不会修改序列所包含的元素, 操作过程仅调用了普通加法__add__方法, 并会生成新的对象. 因此, 应尽量避免频繁地拼接不可变序列. 关于增量赋值操作还有一个比较特殊的例子:

1
2
3
4
5
6
7
8
9
t = (1, 2, [30, 40])

try:
    t[2] += [50, 60]
except TypeError as e:
    print(e)
    # 'tuple' object does not support item assignment

print(t)  # (1, 2, [30, 40, 50, 60])

可以看出, 尽管捕捉到了错误, 元组中的元素仍然被修改了. 上述代码的执行过程可以被简要描述为:

• t[2]所指向的内存被当作栈帧（frame）插入栈顶（Top of Stack, TOS）
• 计算TOS += [50, 60], 这一步已经修改了元素的值
• 重新赋值t[2] = TOS, 这步抛出异常

由于解释器默认不支持事务操作, 这个错误的元素修改结果就被保留了下来. 因此在实际开发中要尽量避免将可变对象作为元组中的元素.

字符串

字符串（String）是由任意数量的字符所构成的有限序列. 在现代高级编程语言中, 字符串一般被当做存储文本的数据结构, 可记为:

\begin{equation} string=c_0c_1c_2…c_{n-1} \end{equation}

在C语言中并不存在原生的字符串类型, 因此采用以’\0’为结束标记的字符型数组作为替代. 这种实现方式的优点在于能够通过下标索引直接原地修改字符串的内容, 但缺点在于无法将字符串所包含的内容作为哈希表的键, 只能使用字符串的首地址作为替代. 值得注意的是, char类型只占用1个字节, 因此只能表示ASCII字符; 而wchar类型的字符占用2个字节, 因此可以存储Unicode编码的字符.

而在Python中, 内置的字符串类型str被定义为存储不可变序列的数据结构, 这意味着字符串将被当作常量处理, 任何修改字符串的方法都会生成新的字符串常量:

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> s = "a"
>>> id0 = id(s)
>>> s+="b"
# 字符串是常量 因此会生成新的字符串 "ab"
>>> s
'ab'
>>> id1 = id(s)
>>> id0==id1  # s指向了新生成的字符串对象
False
>>> s[1]="c"  # 常量不支持直接修改
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

尽管基于引用计数（Reference Counting）的垃圾回收机制可以保证拼接过程中丢弃的字符串常量不会造成内存泄漏, 但生成与销毁字符串的成本却不容小觑. 例如, 在拼接$10^7$次的前提下, 使用join()方法要比直接使用加号快20%左右.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def func_timer(func):
    def insider(*args):
        st = time.perf_counter()
        func(*args)
        print(time.perf_counter() - st)
    return insider

@func_timer
def str_add(base, adder, times):
    for i in range(times):
        base += adder

@func_timer
def join_add(base, adder, times):
    base.join(adder for i in range(times))

A, N = "nginx" * 16, 10**7

# 0.7467752849988756
str_add("", A, N)
# 0.6037130299991986
join_add("", A, N)

但要注意的是, 由于CPython解释器具有常数折叠（Constant Folding）机制, 少量的静态字符串拼接操作会在转换为字节码时自动优化为单个字符串常量, 因此在实际使用中可能感受不到各种拼接方式之间的性能差异. 此外, 通过构建io.StringIO实例可以实现类似于Java所提供的StringBuilder风格的字符串编辑.

字符串类型不仅继承了切片、计数、索引等通用序列操作, 还额外提供了许多用于文本编辑的API, 而对于更复杂的字符串匹配则建议使用re或fnmatch模块, 详细内容请参考标准库中的文本处理服务.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
'a,b,c'.split(',')  # 只能匹配一个分隔符/分隔串
re.split(r'[;,\s]\s*', line)  # 可以匹配多个分隔符

'def func()'.startswith('def')  # 前缀匹配
'gog.com'.startswith(('http:', 'https:'))  # 必须以元组形式传入多个前缀
'setup.py'.endswith(('.py', '.sh'))  # 后缀匹配

'top-k'.find('k')  # 返回第一个匹配元素的下标 没有就返回 -1
'nginx'.index('9')  # 返回第一个匹配元素的下标 没有就报错

# 忽略大小写匹配所有结果
re.findall('python', text, flags=re.IGNORECASE)
# 忽略大小写替换所有结果
re.sub('python', 'snake', text, flags=re.IGNORECASE)

熟悉这些基本操作能帮助你快速解决字符串相关问题, 例如检查单词是否为句中其他单词的前缀:

1
2
3
4
5
6
7
def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
    # 按空格将句子分隔为单词
    for i, word in enumerate(sentence.split(), 1):
        # 判断是否为前缀
        if word.startswith(searchWord):
            return i
    return -1  # 都不是就返回 -1

字符串的另一个重要用法就是模板与格式化. 在Web开发中, 经常需要根据业务逻辑拼接对应的HTTP请求头或地址, 使用format可以轻松实现字符串变量动态替换的功能. 更多相关内容将在WSGI与网络框架专题介绍.

1
2
3
4
5
6
7
8
9
10
11
# 传入一个参数字典
env = {'frame': 'Nginx', 'version': '3.0.1'}

# 渲染字符串
text = '{frame} is {version}.'  # 定义一个模板
text.format(frame='Nginx', version=37) # 'Nginx is 3.0.1.'

# 如果在变量作用域中 可以直接提交 vars()
frame, version = 'Flask', '0.22'
# format_map 会自动匹配需要的变量
text.format_map(vars())

而格式化则有助于让字符串中的内容以更清晰的方式呈现, 当然, 输出内容的格式化也可以使用标准库中的pprint和textwrap模块实现.

1
2
3
4
name, price = 'akg', 159
f'Ear: {name:>8}'  # 'Ear:      akg'
f'Ear: {name:1<6}'  # 'Ear: akg111'
f'Price:{price:$^10.2f}'  # 'Price:$$159.00$$'

Python中并没有强制区分单引号和双引号所定义的字符串之间的区别, 并且解释器会自动拼接同一行内由空格分隔的多个字符串. 而使用三重引号定义的字符串可以跨越多行, 这种定义方式一般被用于注释. 此外, str类中还提供了许多判断字符类型和大小写处理有关的API, 更多内容请参考文本序列类型与常见的字符串操作.

数组

在大多数语言中, 数组（Array）被定义为在连续地址空间中存储相同数据类型的可变序列. 令数组$a$的首地址为$p_0$, 存储的每个元素所占用的空间为$s$, 则通过索引$i$就可以计算出第$i$个元素的地址$p_i$:

\begin{equation} address(a[i]) = p_i = p_0 + i * s \end{equation}

这使得数组能够以$O(1)$的时间复杂度轻松应对需要频繁通过索引来对元素进行随机访问的应用场景, 例如: 二分查找、快速排序、哈希表等. 但在使用数组前必须要根据数据类型$T$及数量$N$来计算需要初始化的空间$S$:

\begin{equation} S = sizeof(T) * N = s * N \end{equation}

在C语言中, 使用变量类型加数组名的方式定义的数组会被分配到栈空间, 由操作系统管理其生命周期; 而使用数组指针加运行时内存分配方式定义的数组会被分配到堆空间, 在不用时需要手动释放.

1
2
3
4
5
6
7
8
N = 1024;  // C99 支持使用变量初始化数组

// 在编译阶段能够确定大小的数组会被分配到栈上
int arr[N] = {0};

// 数组指针指向 malloc 系统调用动态分配的堆内存
int  *parr = (int*)malloc(sizeof(int) * N);
free(parr);  // 释放

值得注意的是, 在数组中插入或删除元素时, 为了保证其他元素仍以紧凑且连续的方式存储在内存中, 需要移动对所操作元素的后续所有元素, 因此这些操作的时间复杂度为$O(n)$.

尽管在标准库中提供了array模块, 但由于Numpy在性能和易用程度方面的出色表现, 在执行数组相关的操作时一般都直接采用numpy模块. 从实现细节来看, Numpy是一个C语言扩展库, 并且内部通过BLAS和LAPACK实现了能够充分利用CPU资源的高性能向量计算, 一般情况下, 用Numpy进行矩阵或向量计算的效率要远超直接使用循环的方式, 但这也要求开发者拥有较为深厚的线性代数知识储备, 例如批量计算图像质心:

1
2
3
4
5
6
7
8
9
10
def probability_density_center(masks):
    N, H, W = masks.shape  # N 个高 H 宽 W 的图像
    masks_sum = np.sum(masks, axis=(1, 2))

    # 符号 @ 表示计算点积
    x_sum = np.sum(masks, axis=1) @ np.arange(W)
    y_sum = np.sum(masks, axis=2) @ np.arange(H)

    points = np.stack((x_sum, y_sum), axis=1)
    return points/masks_sum.reshape(-1, 1)

上例中的masks是三维嵌套数组,也被称为张量（Tensor）, 其本质仍是一维数组, 可以一些用特殊的方法来抻平（flatten）这个结构. 例如求有序矩阵中第K小的元素:

1
2
3
4
5
6
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    arr = sum(matrix, start=[])  # 重构
    arr = reduce(operator.add, matrix)  # 等价于 sum
    arr = np.ravel(matrix)  # 返回视图

    return heapq.nsmallest(k, arr)[-1]  # 小顶堆

相比于灵活的列表类型, 数组的最显著优势在于能够快速处理二进制数据. array模块中提供了用于读写二进制文件的API, 不仅调用方便, 其处理速度也远超结构化读写的方式. 而数组本身内存紧凑的特点也让其可以配合内存视图（memoryview）实现零拷贝数据操作. 有些时候我们只需要获得当前数据的另一种表现形式, 例如上例中的ravel方法就是查看张量的一维视图, 其数据本身并没有被更改, 因此速度要远快于生成新结构的方法. 更多与数组相关的实用方法请参见标准库文档.

参考内容

• 数组与字符串
• 列表常用操作
• 字符串常用操作

• Previous
  高性能程序设计（四）
• Next
  深入理解数据结构（二）