的存在是出于兼容性和性能的考虑。 << 取决于内存的随机值 编译器默认生成的构造函数：无参数（ POD 陷阱解决方案） • 不过我们可以手动指定初始化 weight 为 0 。 • 通过 {} 语法指定的初始化值，会在编译器自 动生成的构造函数里执行。 编译器默认生成的构造函数：无参数（ POD 陷阱解决方案，续） • 不过我们可以手动指定初始化 weight 为 0 。 • 通过 {} 语法指定的初始化值，不仅会在编译 您必须同时定义或删除拷贝构造函数和拷贝赋值函 数，否则出错。” 解决方案：要么删除 • 最简单的办法是，直接禁止用户拷贝这个 类的对象，在 C++11 中可以用 = delete 表示这个函数被删除，让编译器不要自动 生成一个默认的（会导致指针浅拷贝的） 拷贝构造函数了。 • 这样就可以在编译期提前发现错误： 解决方案：要么定义 • 如果需要允许用户拷贝你的 Vector 类对象 double free ）的问题。 解决方案 1 ：获取原始指针（ C * 这种类型的指针） • 解决这个问题需要分两种情况讨论。 • 第一种是，你的 func() 实际上并不需要 “夺走”资源的占有权（ ownership ）。比如 刚才这个例子， func() 只是调用了 p 的 某个成员函数而已，并没有接过掌管对象 生命周期的大权。 解决方案 2 ： unique_ptr 不能拷贝，但可以移动

么手动提取不变量到循环体外。 调用不在另一个文件的函数： SIMD 优化失败 因为编译器看不到那个文件的 other 函数里是什么，哪怕 other 在定义他的文件里是个空函数，他也不敢优化掉。 解决方案：放在同一个文件里 结论：避免在 for 循环体里调用外部函数，把他们移到 同一个文件里，或者放在头文件声明为 static 函数。 将 other 放到 和 func 同一个 .cpp 文件里，这样编译器看得到 SOA 是针对这个案例最高效的数据排布格式 第 7 章： STL 容器 std::vector ：也有指针别名问题 __restrict ：能否用于 std::vector ？ 没用！ 解决方案： pragma omp simd 或 pragma GCC ivdep C/C++ 的缺点：指针的自由度过高，允许多个 immutable reference 指向同一个对象，而 Rust 章：数学运算 数学优化：除法变乘法 相当于变成了 a * 0.5f 编译器放弃的优化：分离公共除数 为什么放弃优化？因为编译器害怕 b = 0 。 解决方案 1 ：手动优化 乘法比除法更快！提前计算好 b 的 倒数避免重复求除法。 解决方案 2 ： -ffast-math -ffast-math 选项让 GCC 更大胆地尝试浮点 运算的优化，有时能带来 2 倍左右的提升。 作为代价，他对

结构， 拼装积木的步骤则对应算法。 17 第 2 章 复杂度分析 Abstract 复杂度分析犹如浩瀚的算法宇宙中的时空向导。 它带领我们在时间与空间这两个维度上深入探索，寻找更优雅的解决方案。 第 2 章 复杂度分析 hello‑algo.com 18 2.1 算法效率评估 在算法设计中，我们先后追求以下两个层面的目标。 1. 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。 Unicode 码点同时出现在一个文本中时，系统如 何解析字符？例如给定一个长度为 2 字节的编码，系统如何确认它是一个 2 字节的字符还是两个 1 字节的字 符？ 对于以上问题，一种直接的解决方案是将所有字符存储为等长的编码。如图 3‑7 所示，“Hello”中的每个字 符占用 1 字节，“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 将“Hello 算法”中的所有字符都 编码为 4 章 数组与链表 hello‑algo.com 69 图 4‑3 数组插入元素示例 值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个 问题的解决方案留在“列表”章节中讨论。 // === File: array.cpp === /* 在数组的索引 index 处插入元素 num */ void insert(int *nums, int

方式等代表数据结构， 拼装积木的步骤则对应算法。 17 第 2 章 复杂度分析 � 复杂度分析犹如浩瀚的算法宇宙中的时空向导。 它带领我们在时间与空间这两个维度上深入探索，寻找更优雅的解决方案。 第 2 章 复杂度分析 hello‑algo.com 18 2.1 算法效率评估 在算法设计中，我们先后追求以下两个层面的目标。 1. 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。 Unicode 码点同时出现在一个文本中时，系统如 何解析字符？例如给定一个长度为 2 字节的编码，系统如何确认它是一个 2 字节的字符还是两个 1 字节的字 符？ 对于以上问题，一种直接的解决方案是将所有字符存储为等长的编码。如图 3‑7 所示，“Hello”中的每个字 符占用 1 字节，“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 将“Hello 算法”中的所有字符都 编码为 4 章 数组与链表 hello‑algo.com 69 图 4‑3 数组插入元素示例 值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个 问题的解决方案留在“列表”章节中讨论。 // === File: array.cpp === /* 在数组的索引 index 处插入元素 num */ void insert(int *nums, int

问题就会越深入，问题就能被解决得更优雅。 17 第 2 章 复杂度分析 Abstract 复杂度分析犹如浩瀚的算法宇宙中的时空向导。 它带领我们在时间与空间这两个维度上深入探索，寻找更优雅的解决方案。 第 2 章 复杂度分析 www.hello‑algo.com 18 2.1 算法效率评估 在算法设计中，我们先后追求以下两个层面的目标。 1. 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。 Unicode 码点同时出现在一个文本中时，系统如 何解析字符？例如给定一个长度为 2 字节的编码，系统如何确认它是一个 2 字节的字符还是两个 1 字节的字 符？ 对于以上问题，一种直接的解决方案是将所有字符存储为等长的编码。如图 3‑7 所示，“Hello”中的每个字 符占用 1 字节，“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 将“Hello 算法”中的所有字符都 编码为 数组与链表 www.hello‑algo.com 69 图 4‑3 数组插入元素示例 值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个 问题的解决方案留在“列表”章节中讨论。 // === File: array.cpp === /* 在数组的索引 index 处插入元素 num */ void insert(int *nums, int

接方式代表数据结构，拼 装积木的步骤则对应算法。 16 第 2 章 复杂度分析 � 复杂度分析犹如浩瀚的算法宇宙中的时空向导。 它带领我们在时间与空间这两个维度上深入探索，寻找更优雅的解决方案。 第 2 章 复杂度分析 hello‑algo.com 17 2.1 算法效率评估 在算法设计中，我们先后追求以下两个层面的目标。 1. 找到问题解法：算法需要在规定的输入范围内，可靠地求得问题的正确解。 Unicode 码点同时出现在同一个文本中时，系统 如何解析字符？例如给定一个长度为 2 字节的编码，系统如何确认它是一个 2 字节的字符还是两个 1 字节的 字符？ 对于以上问题，一种直接的解决方案是将所有字符存储为等长的编码。如图 3‑7 所示，“Hello”中的每个字 符占用 1 字节，“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 ，将“Hello 算法”中的所有字符 都编码为 4 章 数组与链表 hello‑algo.com 66 图 4‑3 数组插入元素示例 值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素的“丢失”。我们将这 个问题的解决方案留在列表章节中讨论。 // === File: array.cpp === /* 在数组的索引 index 处插入元素 num */ void insert(int *nums, int size

Unicode 码点同时出现在同一个文本中时，系统 如何解析字符？例如，给定一个长度为 2 字节的编码，系统如何确认它是一个 2 字节的字符还是两个 1 字节 的字符？ 对于以上问题，一种直接的解决方案是将所有字符存储为等长的编码。如下图所示，“Hello”中的每个字符 占用 1 字节，“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 ，将“Hello 算法”中的所有字符都 编码为 245 13. 回溯 13.1. 回溯算法 「回溯算法 Backtracking Algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态 出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择 都无法找到解为止。 回溯算法通常采用「深度优先搜索」来遍历解空间。在二叉树章节中，我们提到前序、中序和后序遍历都属 于深度优先 问题、解、状态等概念是通用的，在分治、回溯、动态规划、贪心等算法中都有涉及。 13.1.5. 优势与局限性 回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的 优势在于它能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。 然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。 ‧ 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。

m_block ，造成数据竞争。所 以有的指针被重复分配了两遍，写入了那个地址却没有实际被存到 m_data 这个指针数组里。因此结果不对，还造成了内存泄露。 解决：使用互斥量和原子变量 暴力解决方案就是用 std::mutex 避免多个线程同时访问。 然而这样会严重影响性能，锁和原子多了，就根本并行不起来。 教科书式的解决：二次判断法 这样如果 block 已经非空，则可以不用上锁，减少上锁次数。 为空，则上锁；再次检测是否为空，空则分配内存， 非空说明其他线程已经帮我分配好了，直接退出。 结果反而还变慢了……所以有时候教科书（如 Concurrency in Action ）不一定就是完美解决方案，要根据实际情况判断。 真正的解决： tbb::spin_mutex 其实主要的瓶颈在于 std::mutex 会切换到操作系统内核中去调度 ，非常低效。而 tbb::spin_mutex 则是基于硬件原子指令的，完全

，自动搜集需要的文件后缀名 进一步： GLOB_RECURSE 了解一下！能自动包含所有子文件夹下的文件 GLOB_RECURSE 的问题：会把 build 目录里生成的临时 .cpp 文件也 加进来 解决方案：要么把源码统一放到 src 目录下，要么要求使用者不要把 build 放到和源码同一个目录里，我个人的建议是把源码放到 src 目录下 。 第 2 章：项目配置变量 CMAKE_BUILD_TYPE RPATH ， CMake 会让生成出来可执行文件的 RPATH 字段指向他链 接了的 .so 文件所在目录，运行时会优先从 RPATH 里找链接库，所以即使不在同目录也 能找到。 • 所以还有第三种解决方案：微软，我卸卸你全家（指卸载）。然后安装 Arch Linux 系统 。 • 需要手动修改或查看一个 ELF 文件的 RPATH ，可以用 chrpath 或 patchelf 命令。 yyds

的数据量比较大，禁不起这样切换来切换去…… • 一个 SM 可同时运行多个板块，这时多个板块共用同一块共享内存（每块分到的就少了） 。 • 而板块内部的每个线程，则是被进一步调度到 SM 上的每个 SP 。 无原子的解决方案： sum 变成数组 • 刚刚的数组求和例子，其实可以不需要原子操作。 • 首先，声明 sum 为比原数组小 1024 倍的数组。 • 然后在 GPU 上启动 n / 1024 个线程，每个负责原数组 以切换到另一个线程继续执行计算任务，等这个线程陷入内存等 待时，原来那个线程说不定就好了呢？（记得上节课说过内存延 迟是阻碍 CPU 性能提升的一大瓶颈， GPU 也是如此。 CPU 解决方案是超线程技术，一个物理核提供两个逻辑核，当一个逻 辑核陷入内存等待时切换到另一个逻辑核上执行，避免空 转。 GPU 的解决方法就是单个 SM 执行很多个线程，然后在遇 到内存等待时，就自动切换到另一个线程）