性能优化 之 无分支编程 Branchless Programming by 彭于斌（ @archibate ） 两种代码写法：分支 vs 三目运算符 两种使用方式：排序 vs 不排序 测试结果（均为 gcc -O3 ） 测试结果可视化 图表比较：分支 vs 无分支 分支 无分支 0 0.01 0.02 0.03 耗时（越低越好） 乱序 有序 • 传统的分支方法实现的 或者更满足“对称强迫症”的： • (cond) * a + !(cond) * b // 方法 2 • 还有一种“摆烂”的做法： • (cond ? a : b) // 方法 3 • 三目运算符通常会变成和 if-else 一样的分 支，同样会生成条件跳转指令，理应一样 低效。但是有时候编译器会检测到，可以 帮你自动优化成无分支版本的。 “ 妙用加减乘”进行无分支优化的通用公式 • 为什么采用需要三个分支的 clamp 做测试？ • 优化级别在 -O1 以上时，对于只有两个分支的 if-else ，编译器往往会自动检测到可以优化，帮你 应用“妙用加减乘”了，无法体现手动优化的意义。 不同写法的性能测试 • 我们照常编写了测试用例，禁止内联优化，同样生成 10^7 个随机数（ -512 到 512 区间）。 • 至于为什么采用需要三个分支的 clamp 做测试？

比如右边这段代码会得到 4 。 • size_t size() const noexcept; vector 容器： operator[] • 要访问 vector 里的元素，只需用 [] 运算符 ： • 例如 a[0] 访问第 0 个元素（人类的第一 个） • 例如 a[1] 访问第 1 个元素（人类的第二 个） • int &operator[](size_t i) noexcept; noexcept; • int const &operator[](size_t i) const noexcept; vector 容器： operator[] • 值得注意的是， [] 运算符在索引超出数组大 小时并不会直接报错，这是为了性能的考虑。 • 如果你不小心用 [] 访问了越界的索引，可能 会覆盖掉别的变量导致程序行为异常，或是访 问到操作系统未映射的区域导致奔溃。 • int 元素全为 0 的数组。 • vector(initializer_list list); • explicit vector(size_t n); vector 容器 • 添加一个运算符重载用于打印 vector 类 型。 vector 容器：构造函数 • vector 的这个显式构造函数，默认会把所有元 素都初始化为 0 （不必手动去 memset ）。 • 如果是其他自定义类，则会调用元素的默认构造

。 • 例如：一个同学问小彭老师在干嘛？ • 小彭老师说“我在吃答辩。”那么同学认为这个答辩指的是三体动画，小彭老师在看三体动画。 而不会认为小彭老师真的在吃答辩。 • 小彭老师说“我在拉答辩。”那么同学认为这个答辩指的是答辩（物理），小彭老师在上厕所。 而不会认为小彭老师在制作三体动画。 • 所以这位同学是人类思维，相当于 Python 的精分 API 。而如果另一个同学是硬核的计算 __getitem__ 。 • 也就是说 Python 的 [] 其实是调用了两个不同的运算符重载： • m[key] = val 实际上是 m.__setitem__(key, val) 。 • val = m[key] 实际上是 val = m.__getitem__(key) 。 • C++ 的 [] 就不论读取还是写入都是同一个运算符重载，他只是返回引用，无法区分你是读是写： • value_type 值坑了他。所以他们又另起炉灶，发明了越界时不会自动创建零值，而是能抛出异常的 at 函数。 C++ 和 Python 用法对比 C++ 和 Python 用法对比（运算符重载展开成普通函数后） 简单粗暴的 Java 用法 • 与 Python 和 C++ 不同， Java 放弃了花里胡哨的运算符重载，索性都采用成员函数 get put 来表示，非常明确。主要是为了把 get 和 put 作为接口函数，可以对应多个具体 实现。

具有了『匿名函数』的『闭包』特性，而这一特性几乎在现代的编程语言（诸如 Python/Swift/. . . ）中已经司空见惯，右值引用的出现解决了 C++ 长期以来被人诟病的临时对象效率问题等等。 C++17 则是近三年依赖 C++ 社区一致推进的方向，也指出了 现代 C++ 编程的一个重要发展方 向。尽管它的出现并不如 C++11 的分量之重，但它包含了大量小而美的语言与特性（例如结构化绑定）， 这些特性的出现再一次修正了我们在 unique_ptr。 • register 关键字被弃用，可以使用但不再具备任何实际含义。 • bool 类型的 ++ 操作被弃用。 • 如果一个类有析构函数，为其生成拷贝构造函数和拷贝赋值运算符的特性被弃用了。 • C 语言风格的类型转换被弃用（即在变量前使用 (convert_type)），应该使用 static_cast、 reinterpret_cast、const_cast 来进行类型转换。 强行实例化 extern template class std::vector; // 不在该当前编译文件中实例化模板 尖括号 “>” 在传统 C++ 的编译器中，>> 一律被当做右移运算符来进行处理。但实际上我们很容易就写出了嵌 套模板的代码： std::vector> matrix; 这在传统 C++ 编译器下是不能够被编译的，而 C++11

本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书 能够帮助到你！ i 目 录 第 0 章 前言 1 0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 目 录 hello‑algo.com ii 第 8 章 堆 173 8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 目 录 hello‑algo.com iii 第 15 章 贪心 344 15.1 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . .

强烈推荐算法初学者阅读。” ——邓俊辉，清华大学计算机系教授 “如果我当年学数据结构与算法的时候有《Hello 算法》，学起来应该会简单 10 倍！” ——李沐，亚马逊资深首席科学家 i 目 录 0. 前言 1 0.1. 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1. 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 目 录 hello‑algo.com ii 8.2. 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 15.2. 分数背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 目 录 hello‑algo.com iii 15.3. 最大容量问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

本书旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通 过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本书 能够帮助到你！ i 目 录 第 0 章 前言 1 0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 目 录 www.hello‑algo.com ii 第 8 章 堆 173 8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 目 录 www.hello‑algo.com iii 第 15 章 贪心 344 15.1 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . .

强烈推荐算法初学者阅读！” ——邓俊辉，清华大学计算机系教授 “如果我当年学数据结构与算法的时候有《Hello 算法》，学起来应该会简单 10 倍！” ——李沐，亚马逊资深首席科学家 i 目 录 第 0 章 前言 1 0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 目 录 hello‑algo.com ii 第 8 章 堆 173 8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 目 录 hello‑algo.com iii 第 15 章 贪心 346 15.1 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . .

hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完 成（按照首字母顺序排列）。感谢他们付出的时间与精力，正是他们确保了各语言代码的规范与统一。 i 目 录 第 0 章 前言 1 0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 目 录 hello‑algo.com ii 第 8 章 堆 170 8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 目 录 hello‑algo.com iii 第 15 章 贪心 349 15.1 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . .

arm 的指令集处理无符号 8 位整数更高效”，所以擅自把 char 魔改成无 符号的…… • 顺便一提， C++ 标准保证 char ， signed char ， unsigned char 是三个完全 不同的类型， std::is_same_v 分别判断他们总会得到 false ，无论 x86 还是 arm 。 • 但是奇葩的 C 语言却规定 short ， int ， long ， long std::string 应运而生 • string 可以从 const char * 隐式构造： • string s = “hello”; • string 具有 + 、 += 、 == 等直观的运算符重载： • string(“hello”) + string(“world”) == string(“helloworld”) • string 符合 vector 的接口，例如 begin/end/size/resize…… • 因此 string 类从 C 字符串构造时，可以额外指定一个长度： • string(“hello”, 3) 会得到 “ hel” • ↑ len 为 3 ， ptr 指向 ’ h’ ，只保留前三个字符 • string(“hello”, 12) 会得到 “ hello\0[ 数据删除 ]” • ↑ len 为 12 ， ptr 指向 ’ h’ ，超出了 6 个字符，内存读越界（出错） • string(“hello\0world