数据结构与算法：Rust语言描述 (梦寰)（Z-Library）

Problem-solving with algorithms and data structures using Rust Shieber 2021.02.11

序 晶体管的出现引发了集成电路和芯片革命，人类有了中央处理器，大容量存储器和便捷 的通讯设施。Multics [1] 的失败催生了 Unix [2]，而后出现的 Linux内核 [3] 及发行版 [4] 则将 开源与网络技术紧密结合起来，使得信息技术得到飞速发展。技术的进步为社会提供了实践 想法的平台和工具，社会的进步则创造了新的需求和激情，继而又推动技术再进步。尽管计 算机世界的上层诞生了互联网、区块链、云计算、物联网，但在底层，其基本原理保持不变。 变化的特性往往有不变的底层原理作为支撑，就像各种功能的蛋白质也只是几十种氨基酸组 成的肽链的曲折变化一样。计算机世界的底层是基本硬件及其抽象数据类型（数据结构）和 操作（算法）的组合，这是变化的上层技术取得进步的根本。 不管是普通计算机，超级计算机亦或将来的量子计算机 [5]，其功能都要建立在某种数据 结构和算法的抽象之上。数据结构和算法作为抽象数据类型在计算机科学中具有重要地位， 是完成各种计算任务的核心工具。本书重点关注抽象数据类型的设计、实现和使用。通过学 习设计抽象数据类型有助于编程实现，而通过编程实现则可加深对抽象数据类型的理解。 本书的算法实现往往不是最优或最通用的工程实现，因为工程实现冗长，抓不住重点，这 对于学习原理是有害的。本书代码对不同问题采取不同简化措施，有的直接用泛型，有的则 使用具体类型。这些实现措施一是为简化代码，二是确保每段代码都可单独编译通过并得到 运行结果。本书使用 Rust 1.58，紫红色文字为网页链接，点击即可通过浏览器自动打开。 基本要求 虽然理解抽象数据类型概念不涉及到具体的形式，但代码实现却必须要考虑具体的形式， 这就要求本书读者具有一定的 Rust 基础。虽然每个人对 Rust 的熟悉程度和编码习惯有所 不同，但基本要求却是相通的。要阅读本书，读者最好具有以下能力和兴趣： • 能使用 Rust 实现完整的程序，包括使用 Cargo、rustc、test 等。 • 能使用基本的数据类型和结构，包括结构体、枚举体、循环、匹配等。 • 能使用 Rust 泛型，生命周期、所有权系统、指针、非安全代码、宏等。 • 能使用内置库（crate）、外部库，会设置 Cargo.toml。 如果你不会这些，那么可以翻到第一章末尾，从推荐的学习材料里找一些书籍和资料来 学习 Rust 这门语言，之后再回到本书，从头开始学习。本书代码均按照章节和名称保存在 github code 和 gitee code 仓库，欢迎下载使用及指出错误。 1

序 全书结构 为让读者对全书结构有较好的把握以及便于高级用户选择阅读的章节，下面将全书内容 做一个总结。全书分为九章，前两章介绍计算机科学的概念以及算法分析，是整本书的基础。 第二到第六章是简单数据结构和算法的设计和实现。第七和八章是较复杂的树及图数据结构， 树和图是许多大型软件的底层实现，这两章是基于前几章的更高级主题。最后一章是利用前 面所学内容进行的实战项目，通过实战将所学数据结构和算法用于解决实际问题。当然，全 书的章节不是死板的，你可以选择先学某些章节再学其他内容。但总的来说，前两章要先看， 中间的章节及最后的实战也建议按顺序阅读。 第一章：计算机科学。通过学习计算科学定义和概念能指导个人如何分析问题。其中包 括如何建立抽象数据类型模型，设计、实现算法及结果检验。抽象数据类型是对数据操作的 逻辑描述，隐藏了实现细节，有助于更好地抽象出问题本质。本章的最后是 Rust 基础知识 回顾和学习资源总结。 第二章：算法分析。算法分析是理解程序执行时间和空间性能的方法。由算法分析能得 到算法执行效率，比如时间、内存消耗。大 O 分析法是算法分析的一种标准方法。 第三章：基本数据结构。计算机是个线性的系统，对于内存来说也不例外。基本数据结 构保存在内存中，所以也是线性的。Rust中基于这种线性内存模型建立的基本数据结构有数 组、切片、Vec 以及衍生的栈、队列等。本章学习用 Vec 这种基本数据结构来实现栈、队列、 双端队列、链表。 第四章：递归。递归是一种算法技巧，是迭代的另一种形式，必须满足递归三定律。尾 递归是对递归的一种优化。动态规划是一类高效算法的代表，通常利用递归或迭代来实现。 第五章：查找。查找算法用于在某类数据集合中找到某个元素或判断元素是否存在，是 使用最广泛的算法。根据数据集合是否排序可以粗略地分为顺序查找和非顺序查找。非顺序 查找算法包括二分查找和哈希查找等算法。 第六章：排序。前一章的顺序查找算法要求数据有序，而数据一般是无序的，所以需要 排序算法。常见的排序算法有十类，包括冒泡排序、快速排序、插入排序、希尔排序、归并 排序、选择排序、堆排序、桶排序、计数排序、基数排序。蒂姆排序算法是结合归并和插入 排序的排序算法，效率非常高，已经是 Java、Python、Rust 等语言的默认排序算法。 第七章：树。计算机是线性系统，但在线性系统上，通过适当的方法也能构造出非线性 的数据结构。树，正是一种非线性数据结构，它通过指针或引用来指向子树。树中最基础的 是二叉树，由它衍生了二叉堆、二叉查找树、平衡二叉树、八叉树。当然，还有 B 树、B+ 树、红黑树等更复杂的树。 第八章：图。树的连接从根到子，且数量少。如果将这些限制取消，那么就得到了图数 据结构。图是一种解决复杂问题的非线性数据结构，连接方向可有可无，没有父子结点的区 别。虽然是非线性数据结构，但其存储形式也是线性的，包括邻接表和邻接矩阵。图用于处 理含有大量结点和连接关系的问题，例如网络流量、交通流量、路径搜索等问题。 第九章：实战。在前面八章的基础上，本章通过运用所学知识来解决实际问题，实现一 些有用的数据结构和算法。包括距离算法、字典树、过滤器、缓存淘汰算法、一致性哈希算 法以及区块链。通过这些实战项目，读者定能加深对数据结构的认识并提升 Rust 编码水平。 2

序 致谢 高效、安全以及便捷的工程管理工具使得 Rust 成为了一门非常优秀的语言，也是未来 可能替代部分 C/C++工作的最佳语言（目前 Rust正逐步加入 Linux内核）。市面上已经出 版了许多 Rust 书籍，但关于算法的书籍要么是作者没看到，要么就是没有。因为没有 Rust 算法书籍，所以作者自己在学习过程中也不断碰壁。在这样的情况下，一部简单便捷的 Rust 书籍对新人学习算法和数据结构来说必然大有帮助。经过一段时间的资料查阅 [6]、思考、整 理并结合自己的学习经历，作者完成了这本书。虽然 Rust 学习曲线陡峭，但只要找准方向， 有好的资源，就一定能学好，希望本书能做点微小的贡献。 编写这本书主要是为了学习推广 Rust，以及回馈整个开源社区，是开源社区的各种资 源让作者学习和成长。感谢 PingCap 开发的 TiDB 以及其运营的开源社区和线上课程。感 谢 Rust 语言中文社区的 Mike Tang 等成员对 Rust 会议的组织、社区的建设维护。感谢令 胡壹冲在 Bilibili 弹幕网分享的 Rust 学习视频。感谢张汉东等前辈对 Rust 语言的推广，包 括他写的优秀书籍《Rust 编程之道》以及 RustMagazine 中文月刊。当然还要感谢 Mozilla、 AWS、Facebook、谷歌、微软、华为公司为 Rust 设立基金会 [7]，正是这个基金会使得作者 断定 Rust 的未来一片光明，还缺少学习资源，也才有了去写本书的动力。 最后，要感谢电子科技大学提供的学习资源和环境，感谢导师和 KC404 的众位师兄弟 姐妹的关心和帮助。在这里，作者学到了各种技术、文化，得到了成长，更找准了人生前行 的方向。 Shieber 成都 3

目录 序 1 1 计算机科学 7 1.1 本章目标 . . . . . . . . . . . . 7 1.2 快速开始 . . . . . . . . . . . . 7 1.3 什么是计算机科学 . . . . . . . 7 1.4 什么是编程 . . . . . . . . . . . 9 1.5 为什么学习数据结构 . . . . . . 9 1.6 为什么学习算法 . . . . . . . . . 10 1.7 Rust 基础 . . . . . . . . . . . . 10 1.7.1 安装 Rust . . . . . . . . 10 1.7.2 Rust 工具链 . . . . . . . 11 1.7.3 Rust 回顾 . . . . . . . . 11 1.7.4 Rust 学习资料 . . . . . 12 1.8 总结 . . . . . . . . . . . . . . . 13 2 算法分析 14 2.1 本章目标 . . . . . . . . . . . . 14 2.2 什么是算法分析 . . . . . . . . . 14 2.3 大 O 分析法 . . . . . . . . . . . 17 2.4 乱序字符串检查 . . . . . . . . . 19 2.4.1 穷举法 . . . . . . . . . . 19 2.4.2 检查法 . . . . . . . . . . 20 2.4.3 排序和比较法 . . . . . . 21 2.4.4 计数和比较法 . . . . . . 22 2.5 Rust 数据结构的性能 . . . . . . 24 2.5.1 标量和复合类型 . . . . . 24 2.5.2 集合类型 . . . . . . . . 25 2.6 总结 . . . . . . . . . . . . . . . 26 3 基本数据结构 27 3.1 本章目标 . . . . . . . . . . . . 27 3.2 线性数据结构 . . . . . . . . . . 27 3.3 栈 . . . . . . . . . . . . . . . . 28 3.3.1 栈的抽象数据类型 . . . 29 3.3.2 Rust 实现栈 . . . . . . . 29 3.3.3 括号匹配 . . . . . . . . 31 3.3.4 进制转换 . . . . . . . . 36 3.3.5 前中后缀表达式 . . . . . 39 3.3.6 中缀转前后缀表达式 . . 41 3.4 队列 . . . . . . . . . . . . . . . 47 3.4.1 队列的抽象数据类型 . . 48 3.4.2 Rust 实现队列 . . . . . 49 3.4.3 烫手山芋 . . . . . . . . 50 3.5 双端队列 . . . . . . . . . . . . 52 3.5.1 双端队列的抽象数据 类型 . . . . . . . . . . . 53 3.5.2 Rust 实现双端队列 . . . 54 3.5.3 回文检测 . . . . . . . . 56 3.6 链表 . . . . . . . . . . . . . . . 57 3.6.1 链表的抽象数据类型 . . 58 3.6.2 Rust 实现链表 . . . . . 59 3.6.3 链表栈 . . . . . . . . . . 64 3.7 Vec . . . . . . . . . . . . . . . . 66 3.7.1 Vec 的抽象数据类型 . . 66 3.7.2 Rust 实现 Vec . . . . . 67 3.8 总结 . . . . . . . . . . . . . . . 71 4

目录 目录 4 递归 72 4.1 本章目标 . . . . . . . . . . . . 72 4.2 什么是递归 . . . . . . . . . . . 72 4.2.1 递归三定律 . . . . . . . 74 4.2.2 到任意进制的转换 . . . 75 4.2.3 汉诺塔 . . . . . . . . . . 77 4.3 尾递归 . . . . . . . . . . . . . . 79 4.3.1 递归和迭代 . . . . . . . 80 4.4 动态规划 . . . . . . . . . . . . 81 4.4.1 什么是动态规划 . . . . . 84 4.4.2 动态规划与递归 . . . . . 87 4.5 总结 . . . . . . . . . . . . . . . 88 5 查找 89 5.1 本章目标 . . . . . . . . . . . . 89 5.2 查找 . . . . . . . . . . . . . . . 89 5.3 顺序查找 . . . . . . . . . . . . 90 5.3.1 Rust 实现顺序查找 . . . 90 5.3.2 顺序查找复杂度 . . . . . 92 5.4 二分查找 . . . . . . . . . . . . 94 5.4.1 Rust 实现二分查找 . . . 94 5.4.2 二分查找复杂度 . . . . . 97 5.4.3 内插查找 . . . . . . . . 97 5.4.4 指数查找 . . . . . . . . 99 5.5 哈希查找 . . . . . . . . . . . . 100 5.5.1 哈希函数 . . . . . . . . 101 5.5.2 解决冲突 . . . . . . . . 103 5.5.3 Rust 实现 HashMap . . 105 5.5.4 HashMap 复杂度 . . . . 109 5.6 总结 . . . . . . . . . . . . . . . 109 6 排序 110 6.1 本章目标 . . . . . . . . . . . . 110 6.2 什么是排序 . . . . . . . . . . . 110 6.3 冒泡排序 . . . . . . . . . . . . 111 6.4 快速排序 . . . . . . . . . . . . 118 6.5 插入排序 . . . . . . . . . . . . 120 6.6 希尔排序 . . . . . . . . . . . . 123 6.7 归并排序 . . . . . . . . . . . . 125 6.8 选择排序 . . . . . . . . . . . . 127 6.9 堆排序 . . . . . . . . . . . . . . 129 6.10 桶排序 . . . . . . . . . . . . . . 132 6.11 计数排序 . . . . . . . . . . . . 135 6.12 基数排序 . . . . . . . . . . . . 137 6.13 蒂姆排序 . . . . . . . . . . . . 139 6.14 总结 . . . . . . . . . . . . . . . 140 7 树 142 7.1 本章目标 . . . . . . . . . . . . 142 7.2 什么是树 . . . . . . . . . . . . 142 7.2.1 树的定义 . . . . . . . . 145 7.2.2 树的表示 . . . . . . . . 146 7.2.3 分析树 . . . . . . . . . . 150 7.2.4 树的遍历 . . . . . . . . 151 7.3 基于二叉堆的优先队列 . . . . . 155 7.3.1 二叉堆定义 . . . . . . . 155 7.3.2 Rust 实现二叉堆 . . . . 156 7.3.3 二叉堆分析 . . . . . . . 167 7.4 二叉查找树 . . . . . . . . . . . 167 7.4.1 二叉查找树操作 . . . . . 167 7.4.2 Rust 实现二叉查找树 . 168 7.4.3 二叉查找树分析 . . . . . 176 7.5 平衡二叉树 . . . . . . . . . . . 177 7.5.1 AVL 平衡二叉树 . . . . 177 7.5.2 Rust 实现平衡二叉树 . 178 7.5.3 平衡二叉树分析 . . . . . 187 7.6 总结 . . . . . . . . . . . . . . . 188 8 图 189 8.1 本章目标 . . . . . . . . . . . . 189 8.2 什么是图 . . . . . . . . . . . . 189 8.2.1 图定义 . . . . . . . . . . 190 8.3 图的存储形式 . . . . . . . . . . 190 8.3.1 邻接矩阵 . . . . . . . . 191 8.3.2 邻接表 . . . . . . . . . . 191 8.4 图的抽象数据类型 . . . . . . . 192 8.5 图的实现 . . . . . . . . . . . . 193 8.5.1 图解决字梯问题 . . . . . 201 5

目录 目录 8.6 广度优先搜索 . . . . . . . . . . 204 8.6.1 实现广度优先搜索 . . . 204 8.6.2 广度优先搜索分析 . . . 209 8.6.3 骑士之旅 . . . . . . . . 210 8.6.4 图解决骑士之旅 . . . . . 210 8.7 深度优先搜索 . . . . . . . . . . 213 8.7.1 实现深度优先搜索 . . . 214 8.7.2 深度优先搜索分析 . . . 218 8.7.3 拓扑排序 . . . . . . . . 218 8.8 强连通分量 . . . . . . . . . . . 220 8.9 最短路径问题 . . . . . . . . . . 222 8.9.1 Dijkstra 算法 . . . . . . 223 8.9.2 实现 Dijkstra 算法 . . . 224 8.9.3 Dijkstra 算法分析 . . . 227 8.10 总结 . . . . . . . . . . . . . . . 227 9 实战 228 9.1 本章目标 . . . . . . . . . . . . 228 9.2 编辑距离 . . . . . . . . . . . . 228 9.2.1 汉明距离 . . . . . . . . 228 9.2.2 莱文斯坦距离 . . . . . . 230 9.3 字典树 . . . . . . . . . . . . . . 235 9.4 过滤器 . . . . . . . . . . . . . . 238 9.4.1 布隆过滤器 . . . . . . . 238 9.4.2 布谷鸟过滤器 . . . . . . 242 9.5 缓存淘汰算法 LRU . . . . . . . 248 9.6 一致性哈希算法 . . . . . . . . . 254 9.7 Base58 编码 . . . . . . . . . . . 259 9.8 区块链 . . . . . . . . . . . . . . 267 9.8.1 区块链及比特币原理 . . 267 9.8.2 基础区块链 . . . . . . . 268 9.8.3 工作量证明 . . . . . . . 273 9.8.4 区块链存储 . . . . . . . 276 9.8.5 交易 . . . . . . . . . . . 280 9.8.6 账户 . . . . . . . . . . . 283 9.8.7 梅根哈希 . . . . . . . . 286 9.8.8 矿工及挖矿 . . . . . . . 288 9.8.9 比特币奖励 . . . . . . . 294 9.8.10 回顾 . . . . . . . . . . . 295 9.9 总结 . . . . . . . . . . . . . . . 296 6

Chapter 1 计算机科学 1.1 本章目标 • 了解计算机科学的思想 • 了解抽象数据类型的概念 • 回顾 Rust 编程语言基础知识 1.2 快速开始 在计算机技术领域，每个人都要花相当多时间来学习该领域的基础知识，希望有足够的 能力把问题弄清楚并想出解决方案。但是对有些问题，你发现要编写代码却很困难。问题的 复杂性和解决方案的复杂性往往会掩盖与解决问题过程相关的思想。一个问题，往往存在多 种解决方案，每种方案都由其问题陈述结构和逻辑所限定。然而，你可能会将解决 A 问题的 陈述结构和解决 B问题的逻辑结合起来，然后自己给自己制造麻烦。本章首先回顾计算机科 学、算法和数据结构，特别是研究这些主题的原因，并希望借此帮助我们看清解决问题的陈 述结构和逻辑。其次，本章还回顾了 Rust 编程语言，给出了一些学习资料。 1.3 什么是计算机科学 计算机科学往往难以定义，这可能是由于在名称中使用了“计算机”一词。如你所知，计 算机科学不仅仅是对计算机的研究，虽然计算机作为一个工具在其中发挥着最为重要的作用， 但它只是个工具。计算机科学是对问题、解决方案及产生方案的过程的研究。给定某个问题， 计算机科学家的目标是开发一个算法，一系列指令列表，用于解决可能出现的该类问题的任 何实例。遵循这套算法，在有限的时间内就能解决类似问题。计算机科学可以认为是对算法 的研究，但必须认识到，某些问题可能没有解决的算法。这些问题可能是 NPC问题 [8]，目前 不能解决，但对其的研究却是很重要的，因为解决这些难题意味着技术的突破。就像“歌德 7

1.3. 什么是计算机科学 CHAPTER 1. 计算机科学 巴赫猜想 [9]”一样，单是对其的研究就发展出不少工具。或许可以这么定义计算机科学：一 门研究可解决问题方案和不可解决问题思想的科学。 在描述问题和解决方案时，如果存在算法能解决这个问题，那么就称该问题是可计算的。 计算机科学的另一个定义是“针对那些可计算和不可计算的问题，研究是不是存在解决方案”。 你会注意到“计算机”一词根本没有出现在此定义中。解决方案独立于机器，是一整套思想， 和是否用计算机无关。 计算机科学涉及问题解决过程的本身，也就是抽象。抽象使人类能够脱离物理视角而采 用逻辑视角来观察问题并思考解决方案。假设你开车上学或上班。作为老司机，你为了让汽 车载你到目的地，会和汽车有些互动。你进入汽车，插入钥匙，点火，换挡，制动，加速和 转向。从抽象的角度来说，你看到的是汽车的逻辑面，你正在使用汽车设计师提供的功能将 你从一个位置运输到另一个位置，这些功能有时也被称为接口。另一方面，汽车修理师则有 一个截然不同的视角。他不仅知道如何开车，还知道汽车内部所有必要的细节。他了解发动 机是如何工作的，变速箱如何变速，温度如何控制，雨刷如何转动等等。这些问题都属于物 理面，细节都发生在“引擎盖下”。 普通用户使用计算机也是基于这样的视角。大多数人使用计算机写文档、收发邮件、看 视频、浏览新闻、听音乐等，但用户并不知道让这些程序工作的细节。他们从逻辑或用户视 角看计算机。计算机科学家、程序员、技术支持人员和系统管理员看计算机的角度则截然不 同，他们必须知道操作系统工作细节，如何配置网络协议，以及如何编写各种控制功能脚本， 他们必须能够控制计算机的底层。 这两个例子的共同点就是用户态的抽象，有时也称为客户端。用户不需知道细节，只要 知道接口工作方式就能与底层沟通。比如 Rust 的数学计算函数 sin，你可以直接使用。 1 // sin_function.rs 2 fn main() { 3 let x: f32 = 2.0; 4 let y = x.sin(); 5 println!("sin(2) is {y}"); // 0.9092974 6 } 这就是抽象。我们不一定知道如何计算正弦值，但只要知道函数是什么以及如何使用它 就行了。如果正确地输入，就可以相信该函数将返回正确的结果。我们知道一定有人实现了 计算正弦的算法，但细节我们不知道，所以这种情况也被称为“黑箱”。只要简单地描述下接 口：函数名称、参数、返回值，我们就能够使用，细节都隐藏在黑箱里面，如图（1.1）所示。 x x.sin() y 图 1.1: sin 函数 8

1.4. 什么是编程 CHAPTER 1. 计算机科学 1.4 什么是编程 编程是将算法（解决方案）编码为计算机指令的过程。虽然有许多编程语言和不同类型 的计算机存在，但第一步是需要有解决方案，没有算法就没有程序。计算机科学不是研究编 程，然而编程是计算机科学家的重要能力。编程通常是为解决方案创建的表现形式，是问题 及解决思路的陈述，这种陈述主要提供给计算机，其实编程就是梳理自己头脑中问题的陈述 结构的过程。 算法描述了依据问题实际数据所产生的解决方案和产生预期结果所需的一套步骤。编程 语言必须提供一种表示方法来表示过程和数据。为此，编程语言必须提供控制方法和各种数 据类型。控制方法允许以简洁而明确的方式表示算法步骤。至少，算法需要执行顺序处理、决 策选择和重复迭代。只要语言提供这些基本语句，它就可用于算法表示。 计算机中的所有数据项都以二进制形式表示。为了赋予二进制形式数据具体含义，就需 要有数据类型。数据类型提供了对二进制数据的解释方法和呈现形式。数据类型是对物理世 界的抽象，用于表示问题所涉及的实体。这些底层的数据类型（有时称为原始数据类型）为 算法开发提供了基础。例如，大多数编程语言提供整数、浮点数数据类型。内存中的二进制 数据可以解释为整数、浮点数，并且和现实世界的数字（例如-3、2.5）相对应。此外，数据 类型还描述了数据可能存在的操作。对于数字，诸如加减乘除法的操作是最基本的。通常遇 到的困难是问题及其解决方案非常复杂，编程语言提供的简单结构和数据类型虽然足以表示 复杂的解决方案，但通常不便于使用。要控制这种复杂性，需要采用更合理的数据管理方式 （数据结构）和操作流程（算法）。 1.5 为什么学习数据结构 为了管理问题的复杂性和获取解决问题的具体步骤，计算机科学家通过抽象以使自己能 够专注于大问题而不会迷失在细节中。通过创建问题域模型，计算机能够更有效地解决问题。 这些模型允许以更加一致的方式描述算法要处理的数据。 用户 内核Shell 接口 操作 图 1.2: 系统层级图 先前，我们将解决方案抽象称为隐藏特定细节的过程，以允许用户或客户端从高层使用。 9

1.6. 为什么学习算法 CHAPTER 1. 计算机科学 现在转向类似的思想，即对数据的抽象。抽象数据类型（Abstract Data Type，ADT）是对 如何查看数据和操作数据的逻辑描述。这意味着只用关心数据表示什么，而不关心它最终形 式。通过提供这种级别的抽象，就给数据创建了一个封装，隐藏了实现细节。上图展示了抽 象数据类型是什么以及如何操作。用户与接口的交互是抽象的操作，用户和 shell 是抽象数 据类型。 抽象数据类型的实现要求从物理视图使用原始数据类型来构建新的数据类型，我们又称 其为数据结构。通常有许多不同的方法来实现抽象数据类型，但不同的实现要有相同的物理 视图，允许程序员在不改变交互方式的情况下改变实现细节，用户则继续专注于问题。 1.6 为什么学习算法 在计算机世界中，使用一个更快，或者占用更少内存的算法是我们的目标，因为这具有 很多显而易见的好处。在最坏的情况下，可能有一个难以处理的问题，没有什么算法在可预 期的时间内能给出答案。但重要的是能够区分具有解决方案的问题和不具有解决方案的问题， 以及存在解决方案但需要大量时间或其他资源的问题。作为计算机科学家需要一遍又一遍比 较，然后决定某个方案是否是一个好的方案并决定采用的最终方案。 通过看别人解决问题来学习是一种高效的学习方式。通过接触不同问题的解决方案，看 不同的算法设计如何帮助我们解决具有挑战性的问题。通过思考各种不同的算法，我们能发 现其核心思想，并开发出一套具有普适性的算法，以便下一次出现类似的问题时能够很好地 解决。同样的问题，不同人给出的算法实现常彼此不同。就像前面看到的计算 sin的例子，完 全可能存在许多种不同的实现版本。如果一种算法可以使用比另一种更少的资源，比如另一 个算法可能需要 10 倍的时间来返回结果。那么即使两个算法都能完成计算 sin 函数，但时 间少的显然更好。 1.7 Rust 基础 1.7.1 安装 Rust Mac OS，Linux 等类 Unix 系统请使用如下命令安装 Rust，Windows 下的安装方式请 读者到官网查看。 $ curl –proto ‘=https’ –tlsv1.2 -sSf https://sh.rustup.rs | sh 安装好后还需设置环境变量，让系统能够找到 rustc 编译器等工具的位置。对于 Linux 来说，将如下三行加入 ~/.bashrc 末尾。 1 # Rust 语言环境变量 2 export RUSTPATH=$HOME/.cargo/bin 3 export PATH=$PATH:$RUSTPATH 保存退出后再执行 source ~/.bashrc 就可以了。如果嫌麻烦，可以到本书源码第一章下 载 install_rust.sh，执行该脚本就可以完成安装。 10

1.7. RUST 基础 CHAPTER 1. 计算机科学 1.7.2 Rust 工具链 上面的指令会安装 rustup这个工具来管理 Rust工具链。Rust工具链包括编译器 rustc、 项目管理工具 cargo、管理工具 rustup、文档工具 rustdoc、格式化工具 rustfmt、调试工具 rust-gdb。 平时写写简单代码可以使用 rustc 编译，但涉及大项目时还是需要使用 cargo 工具来管 理，这是一个非常好的工具，尤其是管理过 C++ 工程的程序员肯定会欢呼这个工具的伟大。 cargo 工具集项目构建、测试、编译、发布于一体。当然，cargo 内部是调用 rustc 来编译的， 本书项目多不复杂，所以大部分时候也使用 rustc 编译器而不是 Cargo。 rustup 管理着 Rust 工具的安装、升级、卸载。注意，Rust 语言包括稳定版和 nightly 版。nightly 版包括最新特性，更新也更快，首次安装时默认是没有的，可用如下命令安装。 $ rustup default nightly 安装好后可用 rustup 查看。 $ rustup toolchain list stable-x86_64-unknown-linux-gnu nightly-x86_64-unknown-linux-gnu (default) 要切换回 stable 版使用如下命令。 $ rustup default stable 1.7.3 Rust 回顾 Rust 是一门类似 C/C++ 的底层编程语言，这意味着你在那两门语言中学习的很多概 念都能用于帮助理解 Rust。然而 Rust 也提出了自己独到的见解，特别是可变、所有权、借 用、生命周期这几大概念，是 Rust 的优点，也是其难点。 1 // rust_basic.rs 2 fn sum_of_val(nums: &[i32], num: i32) -> i32 { 3 let mut sum: i32 = 0; 4 for n in nums { 5 sum += n; 6 } 7 sum + num 8 } 9 10 fn main() { 11 let num = 10; 12 let nums = [1,2,3,4,5,6,7,8]; 13 let sum = sum_of_val(&nums, num); 14 println!("sum is {sum}"); 15 } 11

1.7. RUST 基础 CHAPTER 1. 计算机科学 上述代码表明 Rust 需要 main 函数，展示了 println 的格式化输出，使用 fn 来定义下 划线风格的函数以及用 -> 表示返回值，最后一行用无分号来表示返回（return）。 下面是 Rust 目前在用的（未来可能增加）关键字，共 39 个，还是比较多的，所以学习 要困难一些，特别注意 Self 和 self。 1 Self enum match super 2 as extern mod trait 3 async false move true 4 await fn mut type 5 break for pub union 6 const if ref unsafe 7 continue impl return use 8 crate in self where 9 dyn let static while 10 else loop struct 1.7.4 Rust 学习资料 书籍文档 入门：《Rust 程序设计语言》、《深入浅出 Rust》、《Rustlings》、《通过例子学 Rust》 、《Rust Primer》、《Rust Cookbook》、《Rust in Action》、《Rust 语言圣经》 进阶：《Cargo 教程》、《Rust 编程之道》、《通过链表学 Rust》、《Rust 设计模式》 高阶：《rustc 手册》、《Rust 宏小册》、《Rust 死灵书》、《Rust 异步编程》 特定领域 Wasm：https://wasmer.io、https://wasmtime.dev、https://wasmedge.org HTTP/3: https://github.com/cloudflare/quiche coreutils: https://github.com/uutils/coreutils 算法：https://github.com/TheAlgorithms/Rust 游戏：https://github.com/bevyengine/bevy 工具：https://github.com/rustdesk/rustdesk 区块链：https://github.com/w3f/polkadot 数据库：https://github.com/tikv、https://github.com/tensorbase/tensorbase 编译器：https://github.com/rust-lang/rustc_codegen_gcc 操作系统：https://github.com/Rust-for-Linux、https://github.com/rcore-os Web 前端：https://github.com/yewstack/yew、https://github.com/denoland/deno Web后端：https://actix.rs/、https://github.com/tokio-rs/axum、https://github.com/poem- web/poem 12

1.8. 总结 CHAPTER 1. 计算机科学 资源网站 Rust 官网：https://www.rust-lang.org Rust 源码：https://github.com/rust-lang/rust Rust 文档：https://doc.rust-lang.org/stable Rust 参考：https://doc.rust-lang.org/reference Rust 杂志：https://rustmagazine.github.io/rust_magazine_2021 Rust 库/箱：https://crates.io、https://lib.rs Rust 中文社区：https://rustcc.cn Rust 乐酷论坛：https://learnku.com/rust Rust 资料搜集：https://www.yuque.com/zhoujiping/programming/rust-materials Rust LeetCode：https://rustgym.com/leetcode Awesome Rust：https://github.com/rust-unofficial/awesome-rust Rust Cheat Sheet：https://cheats.rs 芽之家：https://budshome.com/books.html 令狐壹冲：https://space.bilibili.com/485433391 1.8 总结 本章介绍了计算机科学的思想和抽象数据类型的概念，明确了算法和数据结构的定义和 作用。其次，回顾了 Rust 基础知识并总结了部分学习资源。 13

Chapter 2 算法分析 2.1 本章目标 • 理解算法分析的重要性 • 能够使用大 O 符号分析算法执行时间 • 理解 Rust 数组等数据结构的大 O 分析结果 • 理解 Rust 数据结构的实现是如何影响算法分析的 • 学习对简单的 Rust 程序做性能基准测试 2.2 什么是算法分析 正如我们在第一章中所说，算法是一个通用的，解决某种问题的指令列表。它是用于解 决一类问题任何实例的方法，给定特定输入会产生期望的结果。另一方面，程序是使用某种 编程语言编码的算法。由于程序员知识水平各异且所使用的编程语言各有不同，存在描述相 同算法的不同程序。 一个普遍的现象是，刚接触计算机的学生会将自己的程序和其他人的相比较。你可能注 意到，这些程序看起来很相似。那么当两个看起来不同的程序解决同样的问题时，哪一个更 好呢? 要探讨这种差异，请参考如下的函数 sum_of_n，该函数计算前 n 个整数的和。 1 // sum_of_n.rs 2 fn sum_of_n(n: i32) -> i32 { 3 let mut sum: i32 = 0; 4 for i in 1..=n { 5 sum += i; 6 } 7 sum 8 } 14

2.2. 什么是算法分析 CHAPTER 2. 算法分析 该算法使用初始值为 0 的累加器变量。然后迭代 n 个整数，将每个值依次加到累加器。 现在再看看下面的函数，你可以看到这个函数本质上和前一个函数在做同样的事情。不直观 的原因在于编码习惯不好，代码中没有使用良好的标识符名称，所以代码不易读，且在迭代 步骤中使用了一个额外的赋值语句，这个语句其实是不必要的。 1 // foo.rs 2 fn foo(tom: i32) -> i32 { 3 let mut fred = 0; 4 for bill in 1..=tom { 5 let barney = bill; 6 fred = fred + barney; 7 } 8 fred 9 } 先前提出了一个的问题：哪个函数更好？答案其实取决于读者的评价标准。如果你关注 可读性，函数 sum_of_n 肯定比 foo 好。你可能已经在各种介绍编程的书或课程中看到过类 似例子，其目的之一就是帮助你编写易于阅读和理解的程序。然而，在本书中，我们对算法 本身的陈述更感兴趣（干净的写法当然重要，但那不属于算法和数据结构的知识）。 算法分析是基于算法使用的资源量来进行比较的。说一个算法比另一个算法好就在于它 在使用资源方面更有效率，或者说使用了更少的资源。从这个角度来看，上面两个函数看起 来很相似，它们都使用基本相同的算法来解决求和问题。在资源计算这点上，重要的是要找 准真正用于计算的资源。评价算法使用资源往往要从时间和空间两方面来看。 算法使用的空间指的是内存消耗，解决方案所需的内存通常由问题本身的规模和性质决 定。但有时，部分算法会有一些特殊的空间需求，这种情况下需要非常仔细地审查。 算法使用的时间就是指算法执行所有步骤经过的时间，这种评价方式也被称为算法的执 行时间，可以通过基准分析来测量函数 sum_of_n 的执行时间。 在 Rust 中，可以记录函数运行前后的系统时间来计算代码运行时间。在 std::time 中 有获取系统时间的 SystemTime 函数，它可在被调用时返回系统时间并在之后给出经过的时 间。通过在开始和结束的时候调用该函数，就可以得到函数执行时间。 1 // static_func_call.rs 2 use std::time::SystemTime; 3 fn sum_of_n(n: i64) -> i64 { 4 let mut sum: i64 = 0; 5 for i in 1..=n { 6 sum += i; 7 } 8 sum 9 } 15

2.2. 什么是算法分析 CHAPTER 2. 算法分析 10 11 fn main() { 12 for _i in 0..5 { 13 let now = SystemTime::now(); 14 let _sum = sum_of_n(500000); 15 let duration = now.elapsed().unwrap(); 16 let time = duration.as_millis(); 17 println!("func used {time} ms"); 18 } 19 } 执行这个函数 5 次，每次计算前 500,000 个整数的和，得到了如下结果: func used 10 ms func used 6 ms func used 6 ms func used 6 ms func used 6 ms 我们发现时间是相当一致的，执行这个函数平均需要 6 毫秒。第一执行耗时 10 毫秒是 因为函数要初始化准备，而后面四次执行不需要，此时执行得到的耗时才是比较准确的，这 也是为什么需要执行多次。如果我们运行计算前 1,000,000 个整数的和，其结果如下： func used 17 ms func used 12 ms func used 12 ms func used 12 ms func used 12 ms 可以看到，第一次的耗时还是更长，后面的时间都一样，且恰好是计算前 500,000个整数 耗时的二倍，这说明算法的执行时间和计算规模成正比。现在考虑如下的函数，它也是计算前 n 个整数的和，只是不同于上一个 sum_of_n 函数的思路，它利用数学公式 ∑n i=0 = n(n+1) 2 来计算，效率更高。 1 // static_func_call2.rs 2 fn sum_of_n2(n: i64) -> i64 { 3 n * (n + 1) / 2 4 } 修改 static_func_call.rs 中的 sum_of_n 函数，然后再做同样的基准测试，使用 3 个不 同的 n （100,000、500,000、1,000,000），每个计算 5 次取均值，得到了如下结果： func used 1396 ns func used 1313 ns func used 1341 ns 16

2.3. 大 O 分析法 CHAPTER 2. 算法分析 在这个输出中有两点要重点关注，首先上面记录的执行时间是纳秒，比之前任何例子都 短，这 3 个计算时间都在 0.0013 毫秒左右，和上面的 6 毫秒可是差着几个数量级。其次是 执行时间和 n 无关，n 增大了，但计算时间不变，看起来此时计算几乎不受 n 的影响。 这个基准测试告诉我们，使用迭代的解决方案 sum_of_n 做了更多的工作，因为一些程 序步骤被重复执行，这是它需要更长时间的原因。此外，迭代方案执行所需时间随着 n递增。 另外要意识到，如果在不同计算机上或者使用不用的编程语言运行类似函数，得到的结果也 不同，你的电脑计算值可能不是 1341纳秒（我使用的电脑是联想拯救者 R7000P，CPU是 16 核的 AMD R7-4800H）。如果使用老旧的计算机，则需要更长时间才能执行完 sum_of_n2。 我们需要一个更好的方法来描述这些算法的执行时间。基准测试计算的是程序执行的实 际时间，但它并不真正地提供给我们一个有用的度量，因为执行时间取决于特定的机器，且 毫秒，纳秒间也涉及到数量级转换。我们希望有一个独立于所使用的程序或计算机的度量，这 个度量能独立地判断算法，并且可以用于比较不同算法实现的效率，就像加速度这个度量值 能明确指出速度每秒的改变值一样。在算法分析领域，大 O 分析法就是一种很好度量方法。 2.3 大 O 分析法 要独立于任何特定程序或计算机来表征算法的效率（复杂度），重要的是要量化算法所 需操作的数量。对于先前的求和算法，一个比较好的度量单位是对执行语句进行计数。在 sum_of_n 中，赋值语句的计数为 1 (the_sum = 0 的次数)，the_sum += i 计数为 n。 使用函数 T 表示总的次数：T(n)=1 + n 。参数 n 通常称为问题的规模，T(n) 是解决 问题规模为 n的问题所花费的时间。在上面的求和函数中，使用 n来表示问题大小是有意义 的。我们可以说对 100,000 个整数求和比对 1000 个整数求和的规模大，因此所需时间也更 长。我们的目标是表示出算法的执行时间是如何相对问题规模的大小而改变的。 将这种分析技术进一步扩展，确定操作步骤所有数量不如确定 T(n) 最主要的部分来得 重要。换句话说，当问题规模变大时，T(n)函数某些部分的分量会远远超过其他部分。函数的 数量级表示随着 n增加而增加最快的那些部分。数量级通常用大 O符号表示，写作 O(f(n))， 用于表示对计算中的实际步数的近似。函数 f(n) 表示 T(n) 最主要部分。 在上述示例中，T(n) = n + 1。当 n 变大时，常数 1 对于最终结果变得越来越不重要。 如果我们找的是 T(n) 的近似值，可以删除 1，运行时间就是 O(T(n)) = O(n + 1) = O(n)。 要注意，1 对于 T(n) 肯定是重要的，但当 n 变大时，有没有它 O(n) 近似都是准确的。比如 对于 T (n) = n3 + 1，n 为 1 时，T(n) = 2，如果此时舍掉 1 就不合理，因为这样就相当于 丢掉了一半的运行时间。但是当 n 等于 10 时，T(n) = 1001，此时 1 已经不重要了，即便舍 掉了，T(n) = 1000 依然是一个很准确的指标。 假设对于一些算法，确定的步数是 T (n) = 5n2 +27n+1005。当 n 很小时，例如 1 或 2 ，常数 1005 似乎是函数的主要部分。然而，随着 n 变大，n2 这项变得越来越重要。事实上， 当 n 很大时，其他两项在最终结果中所起的作用变得不重要。当 n 变大时，为了近似 T(n)， 我们可以忽略其他项，只关注 5n2 。系数 5 也变得不重要。我们说 T(n) 具有的复杂度数量 级为 n2，或者 O(n2) 。 17

2.3. 大 O 分析法 CHAPTER 2. 算法分析 但有时算法的复杂度取决于数据的确切值，而不是问题规模的大小。对于这类算法，需 要根据最佳情况，最坏情况或平均情况来表征它们的性能。最坏情况是指导致算法性能特别 差的特定数据集。而相同的算法，不同数据集可能具有非常不同的性能。大多数情况下，算 法执行效率处在最坏和最优两个极端之间（平均情况）。对于程序员而言，重要的是了解这些 区别，使它们不被某一个特定的情况误导。 在学习算法时，一些常见的数量级函数将会反复出现，见下表。为了确定这些函数中哪 个是最主要的部分，我们需要看到当 n 变大时它们相互关系如何。 表 2.1: 不同数量级的函数 T(n) O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) 性能 常数 对数 线性 线性对数 平方指数 立方指数 幂指数 下图画出了各种函数的增长情况，当 n 很小时，函数彼此间不能很好的定义。很难判断 哪个是主导的。随着 n 的增长，就有一个很明确的关系，很容易看出它们之间的大小关系。 注意在 n = 10 时，2n 会大于 n3，图中没有画出完整的情况。 2nn3 n2 nlog2n n log2n 图 2.1: 复杂度曲线 通过上图可以得出这些不同数量级的区别，在一般情况下（n > 10），存在 O(2n) > O(n3) > O(n2) > O(nlogn) > O(n) > O(logn) > O(1)。这对于我们设计算法很有帮助，因 为对于每个算法，我们都能计算其复杂度，如果得到类似 O(2n) 复杂度的算法，我们知道这 一定不实用，然后可以对其进行优化以取得更好的性能。 下面的代码只做了些加减乘除，但我们可以用它来试试新学的算法复杂度分析。 18