简介《Implementing Useful Algorithms in C》由Dmytro Kedyk撰写面向希望系统提升C算法设计与实现能力的中高级开发者及计算机专业学生。全书从算法正确性证明、渐进记法、机器模型与随机化算法切入延伸到数据结构选择、内存管理、代码优化、递归深度控制、多算法取舍及并行化并把软件工程周期、测试、代码评审与维护纳入实践语境适合边读边做项目、逐步补齐工程化思维。压缩包内仅含1个PDF文件大小约485.74MB便于离线阅读、检索与长期查阅目前已有185人学习下载。书中每章末附推荐课程、学习策略、项目实践与参考资料目录覆盖背景知识、工程要点、职业与面试建议、计算机法律、基础数据结构等模块可帮助读者建立从理论分析到可运行实现的完整路径并据此查漏补缺、深入专题。1. 算法实现的隐性成本为什么同一个大O能跑出十倍的差距同一份 C 算法实现换个编译器、换批数据耗时能差十倍——这大概是我见过最多的“玄学”现象。理论上两个 O(n log n) 的排序应该差不多快可一个把数据摊在连续内存里另一个每处理一个元素就追一次指针光是缓存未命中就足以拉开一个数量级。渐进记法描述的是增长趋势的上界它从不负责常数项、分配次数和内存局部性而这些恰恰决定了程序在真实机器上的速度。这本《Implementing Useful Algorithms in C》没停在“给出伪代码”这一步它把每个数据结构和算法重新放回机器模型上审视随机化算法该选哪种随机源、vector 扩容按什么因子、递归改迭代要付什么代价、并行化后哪些假设会失效。这些才是“为什么这么设计、为什么能 work”的答案。2. 机器模型为什么渐进记法算不准常数项2.1 大 O 只描述上界被它丢掉的成本清单度量的起点是一个容易混淆的问题O(f(n)) 定义的是一族函数的上界它连系数都不管更不会告诉你“两个 O(n) 谁先跑完”。举个常见的翻车场景在 n 只有几千的时候一个 O(n) 的哈希表查询可能比 O(log n) 的有序数组还慢因为哈希要算一遍、要跳一次桶、还可能踩到冲突链而有序数组的二分全程在一条连续内存里几乎不触发缓存未命中。所以这本书在第 1 章讲渐近记号紧接着就讲机器模型和“度量效率”顺序不是随手排的。渐近分析回答的是“n 趋于无穷时谁主导”机器模型回答的是“n 是今天这个数时谁更快”。两者缺一你都没法真正选对算法。被大 O 忽略掉的东西大致有这么几类常数因子一次除法、一次取模、一次函数调用、一次虚函数分派都会落到指令条数上内存访问模式顺序访问、跳跃访问、随机访问对应的时间差可以达到两个数量级分配与释放每次new背后是分配器的一次查找频繁小块分配会把一个 O(1) 操作放大出几十条指令分支与流水线可预测的分支和随机的分支代价不同数据规模下的并行度现代 CPU 一条指令能处理的独立操作数取决于数据之间的依赖关系。这些量都不是抽象的它们有具体数值。理解了它们你才能判断“书上说线性探测比链式哈希快”到底是为什么而不是背下来。2.2 内存层级与缓存行一次 miss 相当于多少条指令把 CPU 的存取想成一层层的缓存。寄存器最贵也最快往下是 L1、L2、L3最后才是主存。数量级大致是这样的L1 命中在个位数周期L2 在十几个周期主存在一两百个周期。而一次简单的加法指令只要一个周期。也就是说一次主存未命中你“等”的那段时间够执行上百条别的指令。更关键的是数据不是按需逐个从内存取出来的而是一次取一整条缓存行常见是 64 字节。这就直接解释了为什么两种 O(n) 遍历的实测差距能到五倍以上struct Node { int value; Node* next; }; // 节点分散在堆上 long sum_linked(const Node* head) { long s 0; for (const Node* p head; p; p p-next) s p-value; // 每次 next 几乎都指向新的缓存行 return s; } long sum_array(const int* data, std::size_t n) { long s 0; for (std::size_t i 0; i n; i) s data[i]; // 一条缓存行装 16 个 int return s; }sum_array每读一条缓存行能拿到 16 个值sum_linked每个节点就是一条缓存行指针 8 字节加整数 4 字节再加上分配器对齐实测常常是 16 或 32 字节一个节点。同样的加法次数内存事务数差了十几倍这就是差距的来源。写算法的人如果只在纸面上数操作次数永远看不到这一层。还有一个容易被忽略的细节硬件预取器只认“有规律的地址序列”。顺序遍历时它会提前把下一条缓存行拉进来你甚至感觉不到延迟指针追逐式的遍历预取器基本无能为力。所以链表这种结构不是“慢一点”而是“慢在一种很难优化掉的方式上”。提示判断一个数据结构该不该用连续内存先看访问模式有没有规律而不是先看渐近复杂度。2.3 算法实验怎么测出一个结论是“真的”既然常数项如此重要测量本身就必须当成算法的一部分来做。随手写一个clock()计时然后下结论是最容易翻车的环节。常见的实现思路是固定一套测量流程重复多次、取中位数、让结果逃逸出编译器视野。template class F double median_time_ms(F f, int repeats 11) { std::vectordouble samples; for (int r 0; r repeats; r) { auto t0 std::chrono::steady_clock::now(); volatile long long sink f(); // 结果逃逸防止整段计算被优化掉 (void)sink; auto t1 std::chrono::steady_clock::now(); samples.push_back( std::chrono::durationdouble, std::milli(t1 - t0).count()); } // 取中位数而不是平均数调度抖动、页面缺页都是长尾 std::nth_element(samples.begin(), samples.begin() repeats / 2, samples.end()); return samples[repeats / 2]; }volatile那行是为了防止编译器发现f()的结果没人用直接把整个循环消掉——这是最经典的“测出来 0 毫秒”事故。repeats一般取 9 到 21奇数方便取中位数长尾样本比如刚好碰上系统调度会把平均数抬高中位数更稳。如果需要测的是缓存冷启动的代价那还得刻意在每次运行前冲刷一次缓存否则第一次的结果会显著偏慢。还有一点值得强调输入分布要和真实场景对齐。用有序数据测快速排序你会得到一个漂亮但没意义的中位数因为真实数据往往带有局部的有序性。这本书在“算法实验”这个标题下反复强调的就是这件事——测量不是跑一次而是设计一组能暴露差异的实验。3. 数据结构的内存布局Vector、块数组与链表的分岔点3.1 Vector 的摊销成本倍增因子不是随便选的动长数组几乎是一切容器的基础。它的核心问题只有一个容量不够时怎么办。最朴素的做法是每次加一个元素就扩一个位置这样 n 次插入要搬 n(n-1)/2 次元素退化成平方级。解决办法是按比例扩容最典型的是翻倍。void push_back(const T value) { if (size_ capacity_) { // 容量按倍数增长而不是固定加一 std::size_t new_capacity capacity_ 0 ? 1 : capacity_ * 2; T* new_data static_castT*(::operator new(new_capacity * sizeof(T))); // 逐元素搬移对非平凡类型必须走移动构造memcpy 会跳过资源管理 for (std::size_t i 0; i size_; i) new (new_data i) T(std::move(data_[i])); for (std::size_t i 0; i size_; i) data_[i].~T(); ::operator delete(data_); data_ new_data; capacity_ new_capacity; } new (data_ size_) T(value); size_; }按倍数增长时n 次插入总共搬移的元素数是 n n/2 n/4 … ≈ 2n摊到每次插入上是常数。这就是“摊销 O(1)”的来源单次插入最坏是 O(n)但平摊下来是 O(1)。倍增因子为什么常取 2或者有些实现取 1.5取 2 的代价是在最坏情况下扩容瞬间需要分配约两倍于当前数据的内存峰值内存压力大。取 1.5 的代价是索引计算中出现了乘法且扩容更频繁但峰值内存更低而且释放的旧块更容易被后续扩容复用。这是一个纯粹的内存与时间取舍没有唯一正确答案。还有一个必须点明的实现细节搬移元素时对“可平凡复制”的类型可以用memcpy批量搬对带资源管理的类型必须逐个移动构造再析构旧的。用错了就是未定义行为而且往往在小规模测试里看不出来。3.2 块数组稳定指针与随机访问想兼得时Vector 有个结构性缺陷扩容后所有元素的地址都变了之前保存的指针和迭代器全部失效。对图结构、索引表这类“元素之间互相持有引用”的场景这是致命的。链表解决了地址稳定性但随机访问变成 O(n)遍历也失去了内存局部性。块数组就是这两者之间的折中。它把一维逻辑下标拆成“块号 块内偏移”块本身是固定大小的连续数组块指针集中放在一个顶层数组里。// 块大小取 2 的幂除法和取模就能退化成移位和按位与 T block_array::operator[](std::size_t i) { std::size_t block i block_shift_; // i / block_size std::size_t offset i (block_size_ - 1); // i % block_size return blocks_[block][offset]; }这个公式本身就是它的全部设计。扩容时只动顶层指针数组已有的块原地不动所以元素地址是稳定的——只要那个块没被搬走指针就一直有效。块内访问仍然是连续内存局部性比链表好得多。代价有两个。第一是多一次间接寻址要先读blocks_[block]拿到块指针再读blocks_[block][offset]在缓存里这是两次访问而不是一次。第二是块内碎片如果块大小是 1024 个元素而实际只用了 3 个剩下的空间就浪费了。常见的调法是让块大小在几百到几千字节之间既能装下典型的连续访问又不至于浪费太多。指数计算用移位和掩码而不是/和%是因为后者在老的或者弱的编译器上会真的走除法指令几十个周期的开销放在最热的循环里就很可观。这也是一种“知道机器模型之后才做得出的优化”。3.3 侵入式链表与自由链表节点回收到底省了什么标准库的std::list每个节点是一次独立分配节点里存着前后指针和元素本身。这在两种场景下很不划算元素本身很小指针占的空间比数据还大或者元素已经在内存里了、你只是想让它们串起来。侵入式链表把链接指针直接放进元素类型里struct Task { Task* next; // 侵入式链接不额外分配节点 int priority; // ... 其余数据 }; void push_front(Task* head, Task* task) { task-next head; // 直接改元素里的指针 head task; }省掉的是一次分配以及“元素到节点”的那次指针跳转。代价是元素类型被污染了它只能属于一个链表而且调用方要自己保证元素的生命周期。这就是典型的用通用性换性能。另一层是回收。频繁增删的场景里每次都把节点还给分配器会让分配器成为热点。常见的实现思路是维护一个“自由链表”删除的节点不释放而是串到一条空闲链上下次需要时直接摘下来复用。Task* alloc_task() { if (free_list_) { // 优先复用已回收的节点 Task* t free_list_; free_list_ t-next; return t; } return static_castTask*(::operator new(sizeof(Task))); } void release_task(Task* t) { t-next free_list_; // 挂回自由链表不归还给分配器 free_list_ t; }这本质上是一个简单的对象池。它把分配的开销降到了指针操作但也带来一个副作用内存不会自动归还给系统进程的常驻内存会停在历史峰值上。所以真正的实现里通常还要有周期性的清理或者换用能压缩空闲块的结构。4. 随机数生成为什么“看着随机”离“能用”还差得远4.1 xorshift 的三次移位状态、周期与全零陷阱随机化算法里第一件容易翻车的事是把随机数生成器当成理所当然的东西。一个短小的 xorshift32 就足够说明问题// xorshift32整个生成器的状态只有一个 32 位整数 std::uint32_t xorshift32(std::uint32_t state) { std::uint32_t x state; x ^ x 13; // 低位左移后混入高位 x ^ x 17; // 高位右移后压回低位 x ^ x 5; // 再混一轮 state x; return x; }三次“移位再异或”看起来简单到可疑但它是有限域 GF(2) 上的线性变换只要三个移位量选得对这个变换对应的矩阵的阶数就能达到 2³²−1也就是周期接近 2³²。它极快状态只有一个字适合做大量不追求高质量随机的场景。等的就是这句话状态不能是全零。零经过三次移位异或产生的还是零生成器会永久卡死在 0。这就是所谓的“全零陷阱”也是 xorshift 最经典的初始化条件——种子必须非零。顺带一提xorshift 的低位质量通常不如高位做区间截断时尽量用高位。xorshift 不是万能药。它的状态太小周期短而且不同线程共享同一个状态会产生数据竞争输出也会变得不可复现。多线程场景里每个线程一份独立状态是基本要求。在这本书里xorshift 只是起点。后面还有 Mersenne Twister周期极长状态有六百多个字质量好但内存占用不小和 MRG32k3a适合并行蒙特卡洛多流之间独立性好。选哪一个取决于你要的是速度、周期长度还是内存占用——三者很难同时最优。4.2 有界区间采样取模偏差是从哪来的有了均匀随机数最自然的想法是取模rand() % n。问题在于如果生成器输出的范围是 [0, 2³²)而 n 不能整除 2³²那么某些余数的出现次数就比另一些多一次。举个极端的例子如果 n 接近 2³¹那么一半的余数出现两次一半出现一次偏差接近两倍。在小 n 时这个偏差不明显但在模拟和抽样里它可能显著扭曲结果——尤其是你在做需要可复现性的实验偏差会被误认为算法本身的效果。正确的做法是拒绝采样把 32 位输出截断到不小于 n 的最大的 2 的幂范围内落在 [n, 2ᵏ) 的样本丢弃重来。// 从 [0, n) 均匀取值截断到 2 的幂再拒绝消掉取模偏差 std::uint32_t uniform_bounded(std::uint32_t n, std::uint32_t state) { std::uint32_t mask n - 1; mask | mask 1; mask | mask 2; mask | mask 4; mask | mask 8; mask | mask 16; std::uint32_t x; do { x xorshift32(state) mask; // 落在 [0, 2^k) } while (x n); // 超标的样本直接丢弃 return x; }期望的拒绝次数小于 2所以平均成本仍然接近常数。这是随机化算法里一个反复出现的原则用“可能重试”换“严格正确”比用“一次到位但有偏差”更值得。4.3 从均匀分布到目标分布逆变换与拒绝法各自的代价均匀随机数只是原料真正要用的是正态分布、指数分布、泊松分布。常用的路线有两条。逆变换法适合累积分布函数有解析反函数的情形。指数分布就是典型// F(x) 1 - e^{-λx}所以 F^{-1}(u) -ln(1-u)/λ double exponential(double lambda, double u) { // u ∈ [0, 1) return -std::log1p(-u) / lambda; // log1p 在 u 很小时更精确 }这里用log1p而不是log(1-u)是因为 u 很接近 0 时1-u会出现有效位丢失导致结果在小值区间失真。数值细节往往就是这样决定成败的。拒绝法的形式更简单但接受率是它的命门。从一个形状复杂的分布采样时先从一个容易采的包围分布取点再按高度决定是否接受。二维时可能还有一半的接受率到了高维接受率会随维度指数衰减最后变成“几乎每个样本都拒绝”。这就是为什么高维采样不能靠简单的拒绝法而要换成马尔可夫链蒙特卡洛这类方法。蒙特卡洛积分是一个值得单独说一句的应用它的误差按 O(1/√n) 收敛这个收敛速度和维度无关。所以低维积分用确定性的求积公式往往更准高维积分则几乎只能用蒙特卡洛。这个取舍也是“看维度选算法”的典型例子。5. 常见问题与排查算法实现里最容易翻车的五个地方5.1 类型与数值溢出和浮点比较现象一批大输入跑下来累加结果是负数或者排序后最大值跑到了最前面。原因int通常是 32 位累加超过约 21 亿就会溢出而有符号溢出在标准里是未定义行为——编译器完全可以假设它不会发生从而做出你意料之外的优化。很多“只在 Release 下出现”的 bug问题就出在这里。解决累加器直接用 64 位类型或者在输入阶段就把规模限制住如果必须用无符号类型做回绕就明确写出来不要让读者去猜。还有一种更隐蔽的情况中间结果用int存然后转成long long前面的溢出已经发生了。第二条踩坑浮点等值比较。现象理论上应该相等的两个浮点数用比较返回 false分支走错后误差一路放大。原因IEEE 754 的很多十进制小数根本没有精确的二进制表示加上运算顺序不同会带来不同的舍入所以“算出来差不多”和“存下来完全相等”是两回事。解决用相对误差加绝对误差混合比较容差按量级来定比如fabs(a-b) eps * std::max(fabs(a), fabs(b))。当两者的量级差很远时这个式子退化成绝对误差正好覆盖接近零的情形。5.2 内存与生命周期迭代器失效和递归深度第三条踩坑在遍历vector的过程中调用push_back。现象遍历到后面突然崩溃或者读到的数据明显是旧的。原因push_back触发扩容时旧缓冲区被整体释放所有迭代器、指针和引用同时失效。对损坏的内存再解引用行为是完全不确定的。解决能提前知道规模就先reserve拿不准就用下标而不是迭代器或者干脆换成前面说的块数组。这条规则对std::vector、std::string都成立不只是手写容器。第四条踩坑递归深度失控。现象对已经排好序的数组跑快速排序数据量刚过几万就栈溢出或者性能退化到不可接受。原因每次划分都极不平衡递归深度退化成 n即使没溢出堆栈空间的消耗也是实打实的。解决枢轴用三数取中或者随机化选取递归只处理较小的一侧较大的一侧改用循环再设一个深度阈值超过就切换成堆排序这就是 introsort 的思路。递归深度是有上限的资源和内存一样需要显式管理。5.3 分布与哈希取模偏差与对抗性输入第五条踩坑哈希表在特定输入下从 O(1) 退化成 O(n)。现象本地测试一切正常上线后某个数据集让查询耗时翻了几十倍。原因确定的哈希函数意味着冲突是可以被构造的。如果攻击者或者某种规律性数据恰好让大量键落在同一个桶里链式哈希表的每条链就会退化成链表。解决给哈希函数引入运行时随机种子让冲突模式无法被预知桶的数量和扩容策略也要避免极端负载因子。这就是所谓的通用哈希universal hashing思路——不是为了每次都更快而是为了最坏情况不会失控。6. 设计取舍什么时候该为“通用”付出性能代价写到这里回头看那些看起来零散的选择其实都指向同一个问题你愿意为通用性付出多少性能。标准容器选择了最通用的接口任意类型、任意规模、异常安全、跨编译单元可用。代价是它不能针对“元素很小、数量很多”做特化不能保证指针稳定也不能假设调用方会预先知道规模。手写的专用结构可以把这些假设全部写死换来几倍的性能但换来的结构只能服务一个场景。这本书的写法很克制它不告诉你“应该用哪个”而是把每个结构的成本和收益摊开。块数组比vector多一次间接寻址换来地址稳定侵入式链表省掉一次分配换来类型污染xorshift 极快换来短周期和全零陷阱Mersenne Twister 质量好换来几 KB 的状态。没有一项是免费的。一个粗略的对照结构随机访问地址稳定性每次插入的分配典型失分点VectorO(1)扩容时全部失效摊销接近 0扩容瞬间的峰值内存块数组O(1) 一次间接基本稳定每块一次块内碎片与两次访问侵入式链表O(n)永远稳定0遍历失去局部性选型的第一步不是比较复杂度而是先问清楚这个场景里什么资源最贵。是内存带宽是分配次数是指针稳定性还是最坏情况的延迟答案不同同一个结构的好坏结论就会反过来。我自己的习惯是在给一个数据结构写“通用接口”之前先强制走一遍这个问题清单调用方会不会在遍历时插入、元素会不会很小、最坏情况能不能接受、这个结构会不会被用在多线程里。大多数时候答案会让“通用”这个词退到第二位。从那以后我每次设计容器接口都会先写下三条明确的使用假设再让接口去匹配它们——而不是反过来。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/4 14:38:31 · 阅读 1.2k 超越大O：C++算法实现的缓存、内存布局与随机数取舍
简介《Implementing Useful Algorithms in C》由Dmytro Kedyk撰写面向希望系统提升C算法设计与实现能力的中高级开发者及计算机专业学生。全书从算法正确性证明、渐进记法、机器模型与随机化算法切入延伸到数据结构选择、内存管理、代码优化、递归深度控制、多算法取舍及并行化并把软件工程周期、测试、代码评审与维护纳入实践语境适合边读边做项目、逐步补齐工程化思维。压缩包内仅含1个PDF文件大小约485.74MB便于离线阅读、检索与长期查阅目前已有185人学习下载。书中每章末附推荐课程、学习策略、项目实践与参考资料目录覆盖背景知识、工程要点、职业与面试建议、计算机法律、基础数据结构等模块可帮助读者建立从理论分析到可运行实现的完整路径并据此查漏补缺、深入专题。1. 算法实现的隐性成本为什么同一个大O能跑出十倍的差距同一份 C 算法实现换个编译器、换批数据耗时能差十倍——这大概是我见过最多的“玄学”现象。理论上两个 O(n log n) 的排序应该差不多快可一个把数据摊在连续内存里另一个每处理一个元素就追一次指针光是缓存未命中就足以拉开一个数量级。渐进记法描述的是增长趋势的上界它从不负责常数项、分配次数和内存局部性而这些恰恰决定了程序在真实机器上的速度。这本《Implementing Useful Algorithms in C》没停在“给出伪代码”这一步它把每个数据结构和算法重新放回机器模型上审视随机化算法该选哪种随机源、vector 扩容按什么因子、递归改迭代要付什么代价、并行化后哪些假设会失效。这些才是“为什么这么设计、为什么能 work”的答案。2. 机器模型为什么渐进记法算不准常数项2.1 大 O 只描述上界被它丢掉的成本清单度量的起点是一个容易混淆的问题O(f(n)) 定义的是一族函数的上界它连系数都不管更不会告诉你“两个 O(n) 谁先跑完”。举个常见的翻车场景在 n 只有几千的时候一个 O(n) 的哈希表查询可能比 O(log n) 的有序数组还慢因为哈希要算一遍、要跳一次桶、还可能踩到冲突链而有序数组的二分全程在一条连续内存里几乎不触发缓存未命中。所以这本书在第 1 章讲渐近记号紧接着就讲机器模型和“度量效率”顺序不是随手排的。渐近分析回答的是“n 趋于无穷时谁主导”机器模型回答的是“n 是今天这个数时谁更快”。两者缺一你都没法真正选对算法。被大 O 忽略掉的东西大致有这么几类常数因子一次除法、一次取模、一次函数调用、一次虚函数分派都会落到指令条数上内存访问模式顺序访问、跳跃访问、随机访问对应的时间差可以达到两个数量级分配与释放每次new背后是分配器的一次查找频繁小块分配会把一个 O(1) 操作放大出几十条指令分支与流水线可预测的分支和随机的分支代价不同数据规模下的并行度现代 CPU 一条指令能处理的独立操作数取决于数据之间的依赖关系。这些量都不是抽象的它们有具体数值。理解了它们你才能判断“书上说线性探测比链式哈希快”到底是为什么而不是背下来。2.2 内存层级与缓存行一次 miss 相当于多少条指令把 CPU 的存取想成一层层的缓存。寄存器最贵也最快往下是 L1、L2、L3最后才是主存。数量级大致是这样的L1 命中在个位数周期L2 在十几个周期主存在一两百个周期。而一次简单的加法指令只要一个周期。也就是说一次主存未命中你“等”的那段时间够执行上百条别的指令。更关键的是数据不是按需逐个从内存取出来的而是一次取一整条缓存行常见是 64 字节。这就直接解释了为什么两种 O(n) 遍历的实测差距能到五倍以上struct Node { int value; Node* next; }; // 节点分散在堆上 long sum_linked(const Node* head) { long s 0; for (const Node* p head; p; p p-next) s p-value; // 每次 next 几乎都指向新的缓存行 return s; } long sum_array(const int* data, std::size_t n) { long s 0; for (std::size_t i 0; i n; i) s data[i]; // 一条缓存行装 16 个 int return s; }sum_array每读一条缓存行能拿到 16 个值sum_linked每个节点就是一条缓存行指针 8 字节加整数 4 字节再加上分配器对齐实测常常是 16 或 32 字节一个节点。同样的加法次数内存事务数差了十几倍这就是差距的来源。写算法的人如果只在纸面上数操作次数永远看不到这一层。还有一个容易被忽略的细节硬件预取器只认“有规律的地址序列”。顺序遍历时它会提前把下一条缓存行拉进来你甚至感觉不到延迟指针追逐式的遍历预取器基本无能为力。所以链表这种结构不是“慢一点”而是“慢在一种很难优化掉的方式上”。提示判断一个数据结构该不该用连续内存先看访问模式有没有规律而不是先看渐近复杂度。2.3 算法实验怎么测出一个结论是“真的”既然常数项如此重要测量本身就必须当成算法的一部分来做。随手写一个clock()计时然后下结论是最容易翻车的环节。常见的实现思路是固定一套测量流程重复多次、取中位数、让结果逃逸出编译器视野。template class F double median_time_ms(F f, int repeats 11) { std::vectordouble samples; for (int r 0; r repeats; r) { auto t0 std::chrono::steady_clock::now(); volatile long long sink f(); // 结果逃逸防止整段计算被优化掉 (void)sink; auto t1 std::chrono::steady_clock::now(); samples.push_back( std::chrono::durationdouble, std::milli(t1 - t0).count()); } // 取中位数而不是平均数调度抖动、页面缺页都是长尾 std::nth_element(samples.begin(), samples.begin() repeats / 2, samples.end()); return samples[repeats / 2]; }volatile那行是为了防止编译器发现f()的结果没人用直接把整个循环消掉——这是最经典的“测出来 0 毫秒”事故。repeats一般取 9 到 21奇数方便取中位数长尾样本比如刚好碰上系统调度会把平均数抬高中位数更稳。如果需要测的是缓存冷启动的代价那还得刻意在每次运行前冲刷一次缓存否则第一次的结果会显著偏慢。还有一点值得强调输入分布要和真实场景对齐。用有序数据测快速排序你会得到一个漂亮但没意义的中位数因为真实数据往往带有局部的有序性。这本书在“算法实验”这个标题下反复强调的就是这件事——测量不是跑一次而是设计一组能暴露差异的实验。3. 数据结构的内存布局Vector、块数组与链表的分岔点3.1 Vector 的摊销成本倍增因子不是随便选的动长数组几乎是一切容器的基础。它的核心问题只有一个容量不够时怎么办。最朴素的做法是每次加一个元素就扩一个位置这样 n 次插入要搬 n(n-1)/2 次元素退化成平方级。解决办法是按比例扩容最典型的是翻倍。void push_back(const T value) { if (size_ capacity_) { // 容量按倍数增长而不是固定加一 std::size_t new_capacity capacity_ 0 ? 1 : capacity_ * 2; T* new_data static_castT*(::operator new(new_capacity * sizeof(T))); // 逐元素搬移对非平凡类型必须走移动构造memcpy 会跳过资源管理 for (std::size_t i 0; i size_; i) new (new_data i) T(std::move(data_[i])); for (std::size_t i 0; i size_; i) data_[i].~T(); ::operator delete(data_); data_ new_data; capacity_ new_capacity; } new (data_ size_) T(value); size_; }按倍数增长时n 次插入总共搬移的元素数是 n n/2 n/4 … ≈ 2n摊到每次插入上是常数。这就是“摊销 O(1)”的来源单次插入最坏是 O(n)但平摊下来是 O(1)。倍增因子为什么常取 2或者有些实现取 1.5取 2 的代价是在最坏情况下扩容瞬间需要分配约两倍于当前数据的内存峰值内存压力大。取 1.5 的代价是索引计算中出现了乘法且扩容更频繁但峰值内存更低而且释放的旧块更容易被后续扩容复用。这是一个纯粹的内存与时间取舍没有唯一正确答案。还有一个必须点明的实现细节搬移元素时对“可平凡复制”的类型可以用memcpy批量搬对带资源管理的类型必须逐个移动构造再析构旧的。用错了就是未定义行为而且往往在小规模测试里看不出来。3.2 块数组稳定指针与随机访问想兼得时Vector 有个结构性缺陷扩容后所有元素的地址都变了之前保存的指针和迭代器全部失效。对图结构、索引表这类“元素之间互相持有引用”的场景这是致命的。链表解决了地址稳定性但随机访问变成 O(n)遍历也失去了内存局部性。块数组就是这两者之间的折中。它把一维逻辑下标拆成“块号 块内偏移”块本身是固定大小的连续数组块指针集中放在一个顶层数组里。// 块大小取 2 的幂除法和取模就能退化成移位和按位与 T block_array::operator[](std::size_t i) { std::size_t block i block_shift_; // i / block_size std::size_t offset i (block_size_ - 1); // i % block_size return blocks_[block][offset]; }这个公式本身就是它的全部设计。扩容时只动顶层指针数组已有的块原地不动所以元素地址是稳定的——只要那个块没被搬走指针就一直有效。块内访问仍然是连续内存局部性比链表好得多。代价有两个。第一是多一次间接寻址要先读blocks_[block]拿到块指针再读blocks_[block][offset]在缓存里这是两次访问而不是一次。第二是块内碎片如果块大小是 1024 个元素而实际只用了 3 个剩下的空间就浪费了。常见的调法是让块大小在几百到几千字节之间既能装下典型的连续访问又不至于浪费太多。指数计算用移位和掩码而不是/和%是因为后者在老的或者弱的编译器上会真的走除法指令几十个周期的开销放在最热的循环里就很可观。这也是一种“知道机器模型之后才做得出的优化”。3.3 侵入式链表与自由链表节点回收到底省了什么标准库的std::list每个节点是一次独立分配节点里存着前后指针和元素本身。这在两种场景下很不划算元素本身很小指针占的空间比数据还大或者元素已经在内存里了、你只是想让它们串起来。侵入式链表把链接指针直接放进元素类型里struct Task { Task* next; // 侵入式链接不额外分配节点 int priority; // ... 其余数据 }; void push_front(Task* head, Task* task) { task-next head; // 直接改元素里的指针 head task; }省掉的是一次分配以及“元素到节点”的那次指针跳转。代价是元素类型被污染了它只能属于一个链表而且调用方要自己保证元素的生命周期。这就是典型的用通用性换性能。另一层是回收。频繁增删的场景里每次都把节点还给分配器会让分配器成为热点。常见的实现思路是维护一个“自由链表”删除的节点不释放而是串到一条空闲链上下次需要时直接摘下来复用。Task* alloc_task() { if (free_list_) { // 优先复用已回收的节点 Task* t free_list_; free_list_ t-next; return t; } return static_castTask*(::operator new(sizeof(Task))); } void release_task(Task* t) { t-next free_list_; // 挂回自由链表不归还给分配器 free_list_ t; }这本质上是一个简单的对象池。它把分配的开销降到了指针操作但也带来一个副作用内存不会自动归还给系统进程的常驻内存会停在历史峰值上。所以真正的实现里通常还要有周期性的清理或者换用能压缩空闲块的结构。4. 随机数生成为什么“看着随机”离“能用”还差得远4.1 xorshift 的三次移位状态、周期与全零陷阱随机化算法里第一件容易翻车的事是把随机数生成器当成理所当然的东西。一个短小的 xorshift32 就足够说明问题// xorshift32整个生成器的状态只有一个 32 位整数 std::uint32_t xorshift32(std::uint32_t state) { std::uint32_t x state; x ^ x 13; // 低位左移后混入高位 x ^ x 17; // 高位右移后压回低位 x ^ x 5; // 再混一轮 state x; return x; }三次“移位再异或”看起来简单到可疑但它是有限域 GF(2) 上的线性变换只要三个移位量选得对这个变换对应的矩阵的阶数就能达到 2³²−1也就是周期接近 2³²。它极快状态只有一个字适合做大量不追求高质量随机的场景。等的就是这句话状态不能是全零。零经过三次移位异或产生的还是零生成器会永久卡死在 0。这就是所谓的“全零陷阱”也是 xorshift 最经典的初始化条件——种子必须非零。顺带一提xorshift 的低位质量通常不如高位做区间截断时尽量用高位。xorshift 不是万能药。它的状态太小周期短而且不同线程共享同一个状态会产生数据竞争输出也会变得不可复现。多线程场景里每个线程一份独立状态是基本要求。在这本书里xorshift 只是起点。后面还有 Mersenne Twister周期极长状态有六百多个字质量好但内存占用不小和 MRG32k3a适合并行蒙特卡洛多流之间独立性好。选哪一个取决于你要的是速度、周期长度还是内存占用——三者很难同时最优。4.2 有界区间采样取模偏差是从哪来的有了均匀随机数最自然的想法是取模rand() % n。问题在于如果生成器输出的范围是 [0, 2³²)而 n 不能整除 2³²那么某些余数的出现次数就比另一些多一次。举个极端的例子如果 n 接近 2³¹那么一半的余数出现两次一半出现一次偏差接近两倍。在小 n 时这个偏差不明显但在模拟和抽样里它可能显著扭曲结果——尤其是你在做需要可复现性的实验偏差会被误认为算法本身的效果。正确的做法是拒绝采样把 32 位输出截断到不小于 n 的最大的 2 的幂范围内落在 [n, 2ᵏ) 的样本丢弃重来。// 从 [0, n) 均匀取值截断到 2 的幂再拒绝消掉取模偏差 std::uint32_t uniform_bounded(std::uint32_t n, std::uint32_t state) { std::uint32_t mask n - 1; mask | mask 1; mask | mask 2; mask | mask 4; mask | mask 8; mask | mask 16; std::uint32_t x; do { x xorshift32(state) mask; // 落在 [0, 2^k) } while (x n); // 超标的样本直接丢弃 return x; }期望的拒绝次数小于 2所以平均成本仍然接近常数。这是随机化算法里一个反复出现的原则用“可能重试”换“严格正确”比用“一次到位但有偏差”更值得。4.3 从均匀分布到目标分布逆变换与拒绝法各自的代价均匀随机数只是原料真正要用的是正态分布、指数分布、泊松分布。常用的路线有两条。逆变换法适合累积分布函数有解析反函数的情形。指数分布就是典型// F(x) 1 - e^{-λx}所以 F^{-1}(u) -ln(1-u)/λ double exponential(double lambda, double u) { // u ∈ [0, 1) return -std::log1p(-u) / lambda; // log1p 在 u 很小时更精确 }这里用log1p而不是log(1-u)是因为 u 很接近 0 时1-u会出现有效位丢失导致结果在小值区间失真。数值细节往往就是这样决定成败的。拒绝法的形式更简单但接受率是它的命门。从一个形状复杂的分布采样时先从一个容易采的包围分布取点再按高度决定是否接受。二维时可能还有一半的接受率到了高维接受率会随维度指数衰减最后变成“几乎每个样本都拒绝”。这就是为什么高维采样不能靠简单的拒绝法而要换成马尔可夫链蒙特卡洛这类方法。蒙特卡洛积分是一个值得单独说一句的应用它的误差按 O(1/√n) 收敛这个收敛速度和维度无关。所以低维积分用确定性的求积公式往往更准高维积分则几乎只能用蒙特卡洛。这个取舍也是“看维度选算法”的典型例子。5. 常见问题与排查算法实现里最容易翻车的五个地方5.1 类型与数值溢出和浮点比较现象一批大输入跑下来累加结果是负数或者排序后最大值跑到了最前面。原因int通常是 32 位累加超过约 21 亿就会溢出而有符号溢出在标准里是未定义行为——编译器完全可以假设它不会发生从而做出你意料之外的优化。很多“只在 Release 下出现”的 bug问题就出在这里。解决累加器直接用 64 位类型或者在输入阶段就把规模限制住如果必须用无符号类型做回绕就明确写出来不要让读者去猜。还有一种更隐蔽的情况中间结果用int存然后转成long long前面的溢出已经发生了。第二条踩坑浮点等值比较。现象理论上应该相等的两个浮点数用比较返回 false分支走错后误差一路放大。原因IEEE 754 的很多十进制小数根本没有精确的二进制表示加上运算顺序不同会带来不同的舍入所以“算出来差不多”和“存下来完全相等”是两回事。解决用相对误差加绝对误差混合比较容差按量级来定比如fabs(a-b) eps * std::max(fabs(a), fabs(b))。当两者的量级差很远时这个式子退化成绝对误差正好覆盖接近零的情形。5.2 内存与生命周期迭代器失效和递归深度第三条踩坑在遍历vector的过程中调用push_back。现象遍历到后面突然崩溃或者读到的数据明显是旧的。原因push_back触发扩容时旧缓冲区被整体释放所有迭代器、指针和引用同时失效。对损坏的内存再解引用行为是完全不确定的。解决能提前知道规模就先reserve拿不准就用下标而不是迭代器或者干脆换成前面说的块数组。这条规则对std::vector、std::string都成立不只是手写容器。第四条踩坑递归深度失控。现象对已经排好序的数组跑快速排序数据量刚过几万就栈溢出或者性能退化到不可接受。原因每次划分都极不平衡递归深度退化成 n即使没溢出堆栈空间的消耗也是实打实的。解决枢轴用三数取中或者随机化选取递归只处理较小的一侧较大的一侧改用循环再设一个深度阈值超过就切换成堆排序这就是 introsort 的思路。递归深度是有上限的资源和内存一样需要显式管理。5.3 分布与哈希取模偏差与对抗性输入第五条踩坑哈希表在特定输入下从 O(1) 退化成 O(n)。现象本地测试一切正常上线后某个数据集让查询耗时翻了几十倍。原因确定的哈希函数意味着冲突是可以被构造的。如果攻击者或者某种规律性数据恰好让大量键落在同一个桶里链式哈希表的每条链就会退化成链表。解决给哈希函数引入运行时随机种子让冲突模式无法被预知桶的数量和扩容策略也要避免极端负载因子。这就是所谓的通用哈希universal hashing思路——不是为了每次都更快而是为了最坏情况不会失控。6. 设计取舍什么时候该为“通用”付出性能代价写到这里回头看那些看起来零散的选择其实都指向同一个问题你愿意为通用性付出多少性能。标准容器选择了最通用的接口任意类型、任意规模、异常安全、跨编译单元可用。代价是它不能针对“元素很小、数量很多”做特化不能保证指针稳定也不能假设调用方会预先知道规模。手写的专用结构可以把这些假设全部写死换来几倍的性能但换来的结构只能服务一个场景。这本书的写法很克制它不告诉你“应该用哪个”而是把每个结构的成本和收益摊开。块数组比vector多一次间接寻址换来地址稳定侵入式链表省掉一次分配换来类型污染xorshift 极快换来短周期和全零陷阱Mersenne Twister 质量好换来几 KB 的状态。没有一项是免费的。一个粗略的对照结构随机访问地址稳定性每次插入的分配典型失分点VectorO(1)扩容时全部失效摊销接近 0扩容瞬间的峰值内存块数组O(1) 一次间接基本稳定每块一次块内碎片与两次访问侵入式链表O(n)永远稳定0遍历失去局部性选型的第一步不是比较复杂度而是先问清楚这个场景里什么资源最贵。是内存带宽是分配次数是指针稳定性还是最坏情况的延迟答案不同同一个结构的好坏结论就会反过来。我自己的习惯是在给一个数据结构写“通用接口”之前先强制走一遍这个问题清单调用方会不会在遍历时插入、元素会不会很小、最坏情况能不能接受、这个结构会不会被用在多线程里。大多数时候答案会让“通用”这个词退到第二位。从那以后我每次设计容器接口都会先写下三条明确的使用假设再让接口去匹配它们——而不是反过来。希望帮到你。本文还有配套的精品资源点击获取