第三届中国 Rust 开发者大会 安全高效的二进制序列化 Daniel Wang @ NEAR Borsh • 运行、编码效率 • 确定性 • 跨平台兼容性 二进制序列化的问题 Binary Object Representation Serializer for Hashing • 字节级别确定性 • 执行速度快 Borsh • 轻量级 • 每一个对象与其二进制表示之间都存在一个双射映射 中， borsh 并没有使用 serde • 全部逻辑原生实现 • 序列化、反序列化速度大幅领先其他解决方案 执行速度 执行速度 benchmark 执行速度 benchmark 执行速度 benchmark 执行速度 benchmark • 编译后的体积更小 • borsh 序列化后的二进制更精简 轻量级 序列化结果体积对比 Borsh 基本用法 Case Study NEAR NEAR 智能合约 Case Study Solana 智能合约 Case Study • non self-describing • 保证序列化后的二进制唯一性和确定性 • 主要序列化规则 Borsh 规范 • 整数采用低字节序（ little endian) 存储 • 对于动态长度的集合，先用一个 u32 存储集合 size • 对于原本无序的集合（如 hashmap ），存储时使用

attention.”从这个意义上看，这本 书并非完全“免费”。为了不辜负你为本书所付出的宝贵“注意力”，我会竭尽所能，投入最大的“注意力” 来完成本书的创作。 本人自知学疏才浅，书中内容虽然已经过一段时间的打磨，但一定仍有许多错误，恳请各位老师和同学批评 指正。 本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‑algo 仓库。 动画在 PDF 内的展示效果受限，可访问 18 2.2 迭代与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 空间复杂度 . . 参与创作。 前置条件 你需要至少具备任一语言的编程基础，能够阅读和编写简单代码。 0.1.2 内容结构 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。

attention.”从这个意义上看，这本 书并非完全“免费”。为了不辜负你为本书所付出的宝贵“注意力”，我会竭尽所能，投入最大的“注意力” 来完成本书的创作。 本人自知学疏才浅，书中内容虽然已经过一段时间的打磨，但一定仍有许多错误，恳请各位老师和同学批评 指正。 本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‑algo 仓库。 动画在 PDF 内的展示效果受限，可访问 18 2.2 迭代与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 空间复杂度 . . 参与创作。 前置条件 你需要至少具备任一语言的编程基础，能够阅读和编写简单代码。 0.1.2 内容结构 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。

attention.”从这个意义上看，这本 书并非完全“免费”。为了不辜负你为本书所付出的宝贵“注意力”，我会竭尽所能，投入最大的“注意力” 来完成本书的创作。本人自知学疏才浅，书中内容虽然已经过一段时间的打磨，但一定仍有许多错误，恳请 各位老师和同学批评指正。 本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‑algo 仓库。动画在 PDF 内的 展示效果受限，可访问 18 2.2 迭代与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 空间复杂度 . . 作。 � 前置条件 你需要至少具备任一语言的编程基础，能够阅读和编写简单代码。 0.1.2 内容结构 本书的主要内容如图 0‑1 所示。 ‧ 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 13.2. 使用迭代器处理元素序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 中，这些错误只能通过广泛的测 试和经验丰富的开发者的仔细审核代码来捕捉。在 Rust 中，编译器充当了守门员的角色，拒 绝编译包含这些难以察觉的错误的代码，包括并发错误。通过与编译器合作，团队可以将时间 集中在程序逻辑上，而不是追踪 bug。 Rust 也为系统编程世界带来了现代化的开发工具： • Cargo 是内置的依赖管理器和构建工具，它能轻松增加、编译和管理依赖，并使依赖在 Rust 生态系统中保持一致。 target/debug 下生成可执行文件。这些优化可以让 Rust 代码运行的更快，不 过启用这些优化也需要消耗更长的编译时间。这也就是为什么会有两种不同的配置：一种是为 了开发，你需要快速且频繁地重新构建；另一种是为用户构建最终程序，它们不会经常重新构 建，并且希望程序运行得越快越好。如果你在基准测试代码的运行时间，请确保运行 cargo build --release 并使用 target/release 下的可执行文件进行测试。

6 宏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.7 练习：考拉兹序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.7.1 解答 . . . . . . . . . 11 第 1 部分 授课 本页供课程讲师使用。 以下是有关 Google 内部开展课程的一些相关背景。 上课时间通常是从上午 9:00 到下午 4:00，中间有 1 小时的午餐休息时间。这样上午和下午就各有 3 小时 上课时间。上下午上课时间段内都有多次休息时间和学生做练习的时间。 在授课之前，你需要完成以下事项： 1. 熟悉课程资料。页面提供了演讲者注释以突出重点（请帮忙多多贡献演讲者备注！）。演讲时，请确保 有序，更好地向全班学员展示课程内容。 2. 决定培训日期。由于课程为期四天，建议将时间安排在两周内。课程学员曾表示，他们认为在课程保 留一些间隙有助于更好地进行理解。 3. 找一间足以容纳全体线下学员的教室。建议的班级人数为 15-25 人。这样少的人数可以让大家能够 更轻松地提问，也可以让仅有一位的讲师有足够时间回答问题。确保教室里有讲师和学生用的桌子， 并能够坐下来使用笔记本电脑。特别地，讲

闭包：可以捕获其环境的匿名函数 ............................................................................ 319 13.2. 使用迭代器处理元素序列 ........................................................................................... 329 13 中，这些错误只能通过广泛的测试 和经验丰富的开发者的仔细审核代码来捕捉。在 Rust 中，编译器充当了守门员的角色，拒绝 编译包含这些难以察觉的错误的代码，包括并发错误。通过与编译器合作，团队可以将时间集 中在程序逻辑上，而不是追踪 bug。 Rust 也为系统编程世界带来了现代化的开发工具： • Cargo 是内置的依赖管理器和构建工具，它能轻松增加、编译和管理依赖，并使依赖在 Rust 生态系统中保持一致。 target/debug 下生成可执行文件。这些优化可以让 Rust 代码运行的更 快，不过启用这些优化也需要消耗更长的编译时间。这也就是为什么会有两种不同的配置：一 种是为了开发，你需要经常快速重新构建；另一种是为用户构建最终程序，它们不会经常重新 构建，并且希望程序运行得越快越好。如果你在测试代码的运行时间，请确保运行 cargo build --release 并使用 target/release 下的可执行文件进行测试。

的字符串类型，就不得不先提 go 的字符串类型。 2.4.2.9.1 Golang 中的字符串类型 Go 没有专门的字符类型，存储字符直接使用 byte 来存储，字符串就是一串固 定长度的字符连接起来字符序列。与其他编程语言不同之处在于，Go 的字符串 是字节组成，而其他的编程语言是字符组成。 Go 的字符串可以把它当成字节数组来用，并且是不可变的。 Rust 的字符串底层也是 Vec动态数组，这点和 s 是特定位 置字符串的引用，这就是为什么 s 是&str 类型。 str 生命周期是 static，但是引用是有生命周期限制的。 可以在字符串字面量前加上 r 来避免转义 //没有转义序列 let d: &'static str = r"abc \n abc"; //等价于 let c: &'static str = "abc \\n abc"; 2.4.2.9.2.2 Owner: 资源的所有者 a 2.Borrower: 资源的借用者 x 3.Scope: 作用域，资源被借用/引用的有效期 无论是资源的所有者还是资源的借用/引用，都存在在一个有效的存活时间或区 间，这个时间区间称为生命周期， 也可以直接以 Scope 作用域去理解。 例子： fn main() { let a = 100_i32; { let x

4.1.3 陣列典型應用 陣列是一種基礎且常見的資料結構，既頻繁應用在各類演算法之中，也可用於實現各種複雜資料結構。 ‧ 隨機訪問：如果我們想隨機抽取一些樣本，那麼可以用陣列儲存，並生成一個隨機序列，根據索引實現 隨機抽樣。 ‧ 排序和搜尋：陣列是排序和搜尋演算法最常用的資料結構。快速排序、合併排序、二分搜尋等都主要在 陣列上進行。 ‧ 查詢表：當需要快速查詢一個元素或其對應關係時，可 多次雜湊是開放定址的一種，開放定址法都有不能直接刪除元素的缺陷，需要透過標記刪除。標記為已刪除 的空間可以再次使用。當將新元素插入雜湊表，並且透過雜湊函式找到標記為已刪除的位置時，該位置可以 被新元素使用。這樣做既能保持雜湊表的探測序列不變，又能保證雜湊表的空間使用率。 Q：為什麼線上性探查中，查詢元素的時候會出現雜湊衝突呢？ 查詢的時候透過雜湊函式找到對應的桶和鍵值對，發現 key 不匹配，這就代表有雜湊衝突。因此，線性探查 Vec { // 初始化佇列，加入根節點 let mut que = VecDeque::new(); que.push_back(root.clone()); // 初始化一個串列，用於儲存走訪序列 let mut vec = Vec::new(); while let Some(node) = que.pop_front() { // 隊列出隊 vec.push(node.borrow()

6 巨集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.7 練習：考拉茲序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.7.1 解決方案 . . . . . . . . minutes break 和 continue 4 minutes 區塊 (block) 和範疇 (scope) 5 minutes 函式 3 minutes 巨集 2 minutes 練習：考拉茲序列 15 minutes 6.1 if 表達式 你可以像在其他語言中使用 if 陳述式那樣地使用 if 表達式： fn main() { let x = 10; if x == 0 { println 本節的重點在於，上述的便利性不僅常見，而且確實存在，學員需瞭解如何運用。至於為何將便利性定義為 巨集，以及巨集展開後會變成什麼內容，則沒有那麼重要。 本課程不會探討如何定義巨集，但後續章節將說明衍生巨集的用法。 6.7 練習：考拉茲序列 The Collatz Sequence is defined as follows, for an arbitrary n 1 greater than zero: • If *n i