第三届中国 Rust 开发者大会 Rust 与 算法 谢波 …………………………………………………………………………. …………………………………………………………………………… ...... …………………………………………………………………………… ……………… …………………………………………………………………………… ………………………. …………………………………………………………………………… …………………………………………………………………………… …………………………….. 1 6 11 15 21 • 背景介绍 • 算法相关知识 • Rust 实现数据结构 • Rust 实现算法 • 总结及学习资源 背景介绍 • 个人信息 • 写作动机 • 可参考点 • 为什么 背景介绍 # 个人职业 # 与 Rust 结缘 # 前 GPT 时代作品 个人信息 结算及大数据系统研发工程师 费曼学习法 ) 。 写作本书给我的启示 基础、排序、查找、树、图 代码框、颜色、图片绘制均由 Latex 完成 可参考点 为什么 为什么讲这个话题？ 为什么要讲数据结构和算法两部分？ 算法相关知识 算法相关知识 • 抽象数据类型 • 时空复杂度 • 复杂度计算 • 基本数据结构复杂度 抽象数据类型 什么是抽象数据类型？ 为什么需要抽象数据类型？ 时空复杂度 • 时间复杂度更被看重

客户 资产 合约 员工 手机号 设备 商品 商品 查询 / 操作 生活中无处不在的图 图分析技术分类 图查询 • 使用图数据库的查询语言进行点边搜索 图算法 • 中心性算法 • 社区算法 • 路径算法 • … 图深度学习 • 图嵌入 • 图卷积 • 图注意力网络 • 图自编码器 图查询及其应用场景 图查询 • 使用图数据库的查询语言进行点边的关联查询，可以快速完成传统数据库难以完成的 效利用硬件资源，高可用，高 可靠，故障自愈，低成本运维 HTAP Hybrid Transactional/Analytical Processing ，高性能图计算引 擎，预置 20 余种图计算算法 ，可扩展的分析引擎支持更复 杂的数据挖掘和机器学习场景 MPP Massively Parallel Processing 架构，大规模集群 分布式存储及并行计 算， Shared Nothing 高可用技术方案 基于 Chain Replication （ CRAQ ） 算法实现，进行数据副本处理，头 结点写，多结点读，支持读写分离 ，提供更好的并发查询能力 数据高可用实现 Chain Replication 数据高可用方案 服务高可用实现 系统中 Meta ， TS 服务采用主备架 构，基于 Raft 算法实现租约，进行 服务多活，保证图库不会出现单点 故障。 Raft 服务高可用方案

到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 今天，双核或者四核机器在多线程应用方面，其性能不见得的是单核机器的两倍或者四倍。 这一问题一直伴随 CPU 发展至今。 并发和并行的区别 • 运用多线程的方式和动机，一般分为两种。 • 并发：单核处理器，操作系统通过时间片调 度算法，轮换着执行着不同的线程，看起来 就好像是同时运行一样，其实每一时刻只有 一个线程在运行。目的：异步地处理多个不 同的任务，避免同步造成的阻塞。 • 并行：多核处理器，每个处理器执行一个线 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency ） • 在“小学二年级”算法课里，我们学过复杂度的概念，意思是算法执行所花费的时间取决于数据量 的大小 n ，比如 O(n²) 表示花费时间和数据量的平方成正比。 • 对于并行算法，复杂度的评估则要分为两种： • 时间复杂度：程序所用的总时间（重点） • 工作复杂度：程序所用的计算量（次要） •

万能的 map 容器全家桶及其妙用举例 ( 本期 ) 5. 函子 functor 与 lambda 表达式知多少 6. 通过实战案例来学习 STL 算法库 7. C++ 标准输入输出流 & 字符串格式化 8. traits 技术，用户自定义迭代器与算法 9. allocator ，内存管理与对象生命周期 10. C++ 异常处理机制的前世今生 我们都要认真鞋习哦 我们都要认真鞋习哦 第一章：读取与写入 = { 1, 4, 2, 8, 5, 7 }; • std::find(a.begin(), a.end(), 5); • 这个 std::find 就是标准库帮我们实现的线性数组中查找元素的算法，让我们用动画演示一 下他的工作原理吧。 1 4 2 8 5 7 内存 地址 a a+1 a+2 a+3 a+4 a+5 vector 查找为什么低效 • 我们要找的数是 5 ，首先从数组第一个元素开始，判断第一个元素是否等于 最坏的情况需要判断多少次？最坏不会超过树的深度，而一棵有着 n 个元素的平衡二叉树，深 度只有 ceil(log(n+1)) 层。也就是说我们最多只需要 ceil(log(n+1)) 次大小判断，就能找到任 意一个数！因为算法复杂度可以忽略 +1 -1 这些小东西，所以 set 查找的最坏复杂度是 O(logn) ！ 2 1 4 5 8 7 4 要找的数 ceil(log(6+1)) = 3 层 4 <

到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 for_each 这个算法模板呢？ 我知道可以用 accumulate 啦！但是为了引出 lambda 表达式…… 近现代： C++11 引入了 lambda 表达式 现代： C++14 的 lambda 允许用 auto 自动推断类型 当代： C++17 CTAD / compile-time argument deduction / 编 译期参数推断 当代： C++17 引入常用数值算法 未来： 决这种需求，几乎总是在用 shared_ptr 的模式，于是 Java 和 Python 干 脆简化：一切非基础类型的对象都是浅拷贝，引用计数由垃圾回收机制自动管理。 • 因此，以系统级编程、算法数据结构、高性能计算为主要业务的 C++ ，才发展出了这些思 想，并将拷贝 / 移动 / 指针 / 可变性 / 多线程等概念作为语言基本元素存在。这些在我们的 业务里面是非常重要的，所以不可替代。

• ± 1.mmmmmmm 2^e • 类似于人类的科学计数法，不过是二进制。 著名的“快速浮点平方根算法” • 这个算法是 99 年被人从一个游戏源码中扒 出来的，作者号称是游戏界的大神卡马克 ，但是追根溯源，貌似这个算法存在的还 要更久远，原始作者已不可考，暂且称为 卡马克算法。 • 实际上就是把指数位除以了 2 ，作为牛顿 迭代的初始猜测值而已。看他的 i >> 1 这 里，就是把指数和底数都移动了

的爱恨纠葛 4. 万能的 map 容器全家桶及其妙用举例 5. 函子 functor 与 lambda 表达式知多少 6. 通过实战案例来学习 STL 算法库 7. C++ 标准输入输出流 & 字符串格式化 8. traits 技术，用户自定义迭代器与算法 9. allocator ，内存管理与对象生命周期 set 和 vector 的区别 • 都是能存储一连串数据的容器 。 • 区别 1 ： end(); ++p) { • int value = *p; • } • begin 和 end 返回了迭代器类，这个类具有运算符重载， 使得他能模仿指针的行为，从而尽可能在不同容器之间重 用算法（例如 std::find 和 std::reverse ），而不必修改算 法的代码本身，是 STL 库解耦思想的体现。 set 的遍历 • 为了减少重复打代码的痛 苦， C++17 引入了个语

https://github.com/parallel101/course C++ 标准库五大件：容器（ container ） C++ 标准库五大件：迭代器（ iterator ） C++ 标准库五大件：算法（ algorithm ） C++ 标准库五大件：仿函数（ functor ） C++ 标准库五大件：分配器（ allocator ） 侯捷 STL 侯捷 STL vector 容器 vector 链表的 curr = curr->next 上。 • 这样一个用起来就像普通的指针，但内部却通 过运算符重载适配不同容器的特殊类，就是迭 代器 (iterator) ，迭代器是 STL 中容器和算法 之间的桥梁。 迭代器模式：首迭代器＋尾迭代器 • 如果让小彭老师来写 list 容器和他的迭代器，他的 内部具体实现可能是这样的。 • 迭代器的这些运算符，都是约定俗成的，其根本目 的在于模仿指针的行为，方便来自 pos, initializer_list lst); vector 容器： insert 函数，插入另一个 vector 需通过他的两个迭代 器 • 记得 C++ 的迭代器思想是，容器和算法之间的交互不是 通过容器对象本身，而是他的迭代器，因此 insert 设计 时就决心不支持直接接受 vector 作参数，而是接受他的 两个迭代器组成的区间！好处有： 1. 可以批量插入从来自另一个不同类型的容器，例如

到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 - 谷歌单元测试框架 8. google/benchmark - 谷歌性能评估框架 9. glfw/glfw - OpenGL 窗口和上下文管理 10.libigl/libigl - 各种图形学算法大合集 fmt - 使用这个神奇的格式化库 • fmt::format 的用法和 Python 的 str.format 大致相似： CMake - 引用系统中预安装的第三方库 • 可以通过

到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 的代码，转换成一个利用 SIMD 指令的 ，处理矢量 float 的代码，从而增强你程序的吞吐能力！ • 通常认为利用同时处理 4 个 float 的 SIMD 指令可以加速 4 倍。但是如果你的算法不 适合 SIMD ，则可能加速达不到 4 倍；也有因为 SIMD 让访问内存更有规律，节约了指 令解码和指令缓存的压力等原因，出现加速超过 4 倍的情况。 第 1 章：化简 编译器优化：代数化简