目录

上一个主题

3.2. 探索模块‌

下一个主题

4. 函数式编程

>>> from env_helper import info; info()
页面更新时间： 2022-03-22 23:29:28
运行环境：
    Linux发行版本: Debian GNU/Linux 11 (bullseye)
    操作系统内核: Linux-5.10.0-11-amd64-x86_64-with-glibc2.31
    Python版本: 3.9.2

3.3. 数据结构模块

在Python中，短语“开箱即用”（batteries included）最初是由Frank Stajano提出的，指的是Python丰富的标准库。安装Python后，你就免费获得了大量很有用的模块。鉴于有很多方式可以获取有关这些模块的详细信息，这里不打算提供完整的参考手册，而只是描述几个我喜欢的标准模块，以激发你的探索兴趣。

堆和双端队列

有用的数据结构有很多。Python支持一些较常用的，其中的字典（散列表）和列表（动态数 组）是Python语言的有机组成部分。还有一些虽然不那么重要，但有时也能派上用场。

堆

一种著名的数据结构是堆（heap），它是一种优先队列。优先队列让你能够以任意顺序添 加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min， 这样做的效率要高得多。

实际上，Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。这个模块名为 heapq（其中的q表示队列），它包含6个函数（如表10-5所示），其中前4个与堆操作直接相关。必 须使用列表来表示堆对象本身。

表10-5 模块heapq中一些重要的函数

函 数

描 述

heappush(heap, x)

将x压入堆中

heappop(heap)

从堆中弹出最小的元素

heapify(heap)

让列表具备堆特征

heapreplace(heap, x)

弹出最小的元素，并将x压入堆中

nlargest(n, iter)

返回iter中n个最大的元素

nsmallest(n, iter)

返回iter中n个最小的元素

函数heappush用于在堆中添加一个元素。请注意，不能将它用于普通列表，而只能用于使用 各种堆函数创建的列表。原因是元素的顺序很重要（虽然元素的排列顺序看起来有点随意，并没 有严格地排序）。

>>> from heapq import *
>>> from random import shuffle
>>> data = list(range(10))
>>> shuffle(data)
>>> heap = []
>>> for n in data:
>>>     heappush(heap, n)
>>> heap
[0, 1, 2, 4, 3, 8, 6, 9, 5, 7]

>>> heappush(heap, 0.5)
>>> heap
[0, 0.5, 2, 4, 1, 8, 6, 9, 5, 7, 3]

元素的排列顺序并不像看起来那么随意。它们虽然不是严格排序的，但必须保证一点：位置 i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。 这是底层堆算法的基础，称为堆特征（heap property）。

函数heappop弹出最小的元素（总是位于索引0处），并确保剩余元素中最小的那个位于索引0 处（保持堆特征）。虽然弹出列表中第一个元素的效率通常不是很高，但这不是问题，因为heappop 会在幕后做些巧妙的移位操作。

>>> heappop(heap)
>>> heappop(heap)
>>> heappop(heap)
1

>>> heap
[2, 3, 5, 4, 7, 8, 6, 9]

函数heapify通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。如果你的 堆并不是使用heappush创建的，应在使用heappush和heappop之前使用这个函数。

>>> heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2]
>>> heapify(heap)
>>> heap
[0, 1, 5, 3, 2, 7, 9, 8, 4, 6]

函数heapreplace用得没有其他函数那么多。它从堆中弹出最小的元素，再压入一个新元素。 相比于依次执行函数heappop和heappush，这个函数的效率更高。

>>> heapreplace(heap, 0.5)
0

>>> heap
[0.5, 1, 5, 3, 2, 7, 9, 8, 4, 6]

>>> heapreplace(heap, 10)
0.5

>>> heap
[1, 2, 5, 3, 6, 7, 9, 8, 4, 10]

双端队列

在需要按添加元素的顺序进行删除时，双端队列很有用。在模块collections中，包含类型deque以及其他几个集合（collection）类型。 与集合（set）一样，双端队列也是从可迭代对象创建的，它包含多个很有用的方法。

>>> from collections import deque
>>> q = deque(range(5))
>>> q.append(5)
>>> q.appendleft(6)
>>> q
deque([6, 0, 1, 2, 3, 4, 5])

>>> q.pop()
5

>>> q.popleft()
6

>>> q.rotate(3)
>>> q
deque([2, 3, 4, 0, 1])

>>> q.rotate(-1)
>>> q
deque([3, 4, 0, 1, 2])

其他有趣的标准模块

虽然本章介绍的内容很多，但这只是标准库的冰山一角。为激发你深入探索的兴趣，下面简单说说其他几个很棒的库。

  • argparse：在UNIX中，运行命令行程序时常常需要指定各种选项（开关），Python解释器 就是这样的典范。这些选项都包含在sys.argv中，但要正确地处理它们绝非容易。模块 argparse使得提供功能齐备的命令行界面易如反掌。

  • cmd：这个模块让你能够编写类似于Python交互式解释器的命令行解释器。你可定义命令， 让用户能够在提示符下执行它们。或许可使用这个模块为你编写的程序提供用户界面？

  • csv：CSV指的是逗号分隔的值（comma-seperated values），很多应用程序（如很多电子表 格程序和数据库程序）都使用这种简单格式来存储表格数据。这种格式主要用于在不同 的程序之间交换数据。模块csv让你能够轻松地读写CSV文件，它还以非常透明的方式处 理CSV格式的一些棘手部分。

  • datetime：如果模块time不能满足你的时间跟踪需求，模块datetime很可能能够满足。 datetime支持特殊的日期和时间对象，并让你能够以各种方式创建和合并这些对象。相比 于模块time，模块datetime的接口在很多方面都更加直观。

  • difflib：这个库让你能够确定两个序列的相似程度，还让你能够从很多序列中找出与指 定序列最为相似的序列。例如，可使用difflib来创建简单的搜索程序。

  • enum：枚举类型是一种只有少数几个可能取值的类型。很多语言都内置了这样的类型，如 果你在使用Python时需要这样的类型，模块enum可提供极大的帮助。

  • functools：这个模块提供的功能是，让你能够在调用函数时只提供部分参数（部分求值，partial evaluation），以后再填充其他的参数。在Python 3.0中，这个模块包含filter和reduce。

  • hashlib：使用这个模块可计算字符串的小型“签名”（数）。计算两个不同字符串的签名 时，几乎可以肯定得到的两个签名是不同的。你可使用它来计算大型文本文件的签名， 这个模块在加密和安全领域有很多用途①。

  • itertools：包含大量用于创建和合并迭代器（或其他可迭代对象）的工具，其中包括可 以串接可迭代对象、创建返回无限连续整数的迭代器（类似于range，但没有上限）、反复 遍历可迭代对象以及具有其他作用的函数。

  • logging：使用print语句来确定程序中发生的情况很有用。要避免跟踪时出现大量调试输 出，可将这些信息写入日志文件中。这个模块提供了一系列标准工具，可用于管理一个 或多个中央日志，它还支持多种优先级不同的日志消息。

  • statistics：计算一组数的平均值并不那么难，但是要正确地获得中位数，以确定总体标准偏差和样本标准偏差之间的差别，即便对于偶数个元素来说，也需要费点心思。在这种情况下，不要手工计算，而应使用模块statistics！

  • timeit、profile和trace：模块timeit（和配套的命令行脚本）是一个测量代码段执行时 间的工具。这个模块暗藏玄机，度量性能时你可能应该使用它而不是模块time。模块 profile（和配套模块pstats）可用于对代码段的效率进行更全面的分析。模块trace可帮 助你进行覆盖率分析（即代码的哪些部分执行了，哪些部分没有执行），这在编写测试代 码时很有用。