当前位置：首页 > ai >正文

CppCon 2014 学习:EFFICIENCY PERFORMANCE ALGORITHMS DATA STRUCTURES

ai 2025/7/15 4:49:12

你这段内容主要讲的是“做更少的工作，避免浪费努力（Do Less Work By Not Wasting Effort）”，通过更高效的算法### 子串搜索(Sub-string Searching)

最初： 最基础的算法是 O(n²)，比如暴力搜索，每次都从头开始比较。
改进： Knuth-Morris-Pratt (KMP) 算法，使用一个“跳表”，跳过不必要的匹配。
更进一步： Boyer-Moore 算法，利用“针（needle）”的末尾信息跳过更多字符，极大减少比较次数。
核心思想： 减少不必要的比较，做到“少做事，快完成”。

代码示例：避免浪费努力

1. `std::vector` 动态扩容带来的额外开销

std::vector<X> f(int n) {std::vector<X> result;for (int i = 0; i < n; ++i)result.push_back(X(…));return result;
}

这里 result 未提前预分配空间，每次扩容都可能导致重新分配和复制，浪费时间。
改进为：

std::vector<X> f(int n) {std::vector<X> result;result.reserve(n);  // 提前分配好容量，避免多次扩容for (int i = 0; i < n; ++i)result.push_back(X(…));return result;
}

2. 缓存查找优化

X *getX(std::string key, std::unordered_map<std::string, std::unique_ptr<X>> &cache) {if (cache[key])return cache[key].get();cache[key] = std::make_unique<X>(…);return cache[key].get();
}

这里每次 cache[key] 都访问两次，且访问会触发哈希查找两次。
改成：

X *getX(std::string key, std::unordered_map<std::string, std::unique_ptr<X>> &cache) {std::unique_ptr<X> &entry = cache[key];  // 只访问一次哈希表if (entry)return entry.get();entry = std::make_unique<X>(…);return entry.get();
}

总结

做更少的工作 = 避免重复计算、避免不必要的操作
避免浪费努力 = 提前规划，减少资源浪费（比如内存重分配，重复查找）
这是一种性能优化的思维方式，贯穿算法设计与代码实现的各个层面。

“拒绝链表（Linked Lists）”，因为现代CPU和内存架构导致链表性能很差，别用链表了！”

重点解析：

现代CPU超快，但访问内存的速度却没那么快！

CPU频率高达 3GHz，约 1,000,000,000 个周期每秒
多核心、多执行端口，理论执行指令数高达 36,000,000,000 条每秒
但实际上大量时间都在等待内存数据（估计50%时间）

CPU缓存层级（cache hierarchy）访问时间（大致数值）：

操作	时间	说明
CPU周期（3 GHz处理器）	1 ns	最快
L1缓存访问	0.5 ns	CPU内部一级缓存最快访问
分支错误预测惩罚	5 ns	跳转错误带来惩罚
L2缓存访问	7 ns	二级缓存，比L1慢14倍
互斥锁（Mutex）开锁/解锁	25 ns	线程同步成本
主内存访问	100 ns	远远慢于缓存，L1的200倍
Snappy压缩1K字节	3,000 ns	CPU计算操作开销
1Gbps网络发送1K字节	10,000 ns	网络传输
SSD随机读4K	150,000 ns	远比内存慢
内存顺序读1MB	250,000 ns	大块数据顺序读
数据中心内部往返延迟	500,000 ns	网络延迟
SSD顺序读1MB	1,000,000 ns	SSD比内存慢4倍
磁盘寻址	10,000,000 ns	远比SSD慢
磁盘顺序读1MB	20,000,000 ns	磁盘访问非常慢
跨大洲数据包往返延迟（加州到荷兰）	150,000,000 ns	极慢，150 ms级延迟

为什么说“拒绝链表”？

链表访问不是顺序访问，缓存命中率极低。
链表节点分散在内存不同位置，访问时大量缓存未命中，导致访问延迟高达几十倍甚至上百倍。
现代CPU高速执行和深层缓存机制要求访问模式尽可能连续，链表这种跳跃式访问严重拖慢性能。
用 数组（vector）或连续内存结构 代替链表，提升缓存利用率，减少内存访问等待。

结论：

现代性能瓶颈往往是内存访问延迟，不是CPU计算能力。
链表数据结构在现代高性能场景下通常不是好选择。
应该选择缓存友好的数据结构，比如连续内存的数组、哈希表等。

`std::list`（双向链表）在性能上不理想：

std::list 的特点和性能瓶颈：

双向链表结构：每个节点有指向前后节点的指针。
每个节点独立分配内存：分散在堆的不同地址。
遍历操作需要不断跳转指针：每访问一个节点都跳到内存中新的、不连续的位置。
绝大多数遍历步骤都会产生缓存未命中（cache miss）：CPU缓存机制极大依赖数据局部性，链表遍历完全打破了这一点。
适用场景有限：
- 不常遍历链表，
- 频繁插入/删除操作，特别是在中间位置修改元素时。

总结：

如果程序主要是遍历访问，std::list 性能非常差，因为缓存未命中导致CPU等待。
如果程序是大量随机插入删除，但很少遍历，链表可能还合适。
一般情况，推荐用连续内存结构（如 std::vector 或 std::deque）替代 std::list，提升缓存效率和整体性能。

推荐用 `std::vector` 替代很多传统的数据结构，比如栈、队列、甚至映射（在某些场景下），原因主要有：

为什么“Just use std::vector”？

std::vector 是一个动态数组，内存连续，缓存友好，遍历快。
栈（stack）：std::vector 自带的 push_back 和 pop_back 方法完美支持栈操作，性能极佳。
队列（queue）：
- 如果队列大小有限或者生命周期短，用 std::vector + 一个“前端索引”管理队列头很有效。
- 不断增长的 vector，用索引指向“队首”，避免频繁移动元素。
映射（maps）：
- 在某些情况下，如果键空间有限或有序且访问模式简单，用 vector + 二分查找能替代。
- 特别是小规模数据，vector 的线性遍历有时比树结构更快。

总结

std::vector 的缓存友好和简单高效的接口让它成为多数场景的首选。
传统链表、复杂容器在缓存不友好或者频繁内存分配时开销大。
利用索引技巧，vector 也可以实现队列功能。

为什么说使用 `std::map` 是“让代码变慢”的行为？

std::map 本质是一个平衡二叉树（通常是红黑树），节点通过指针连接。
因此它具有链表结构的一些缺点：
- 内存不连续，频繁指针跳转导致缓存不友好，遍历容易缓存失效（cache miss）。
- 插入、删除操作涉及树的部分遍历和重平衡，这些操作复杂且成本较高。
虽然 std::map 有提示（hint）功能帮助插入时减少遍历，但重平衡依然需要访问节点。
这意味着相比简单的连续内存结构，std::map 速度较慢。