查找和为x的两个数组元素:两种O(n log n)实现效率差25倍的原因
两段代码效率差25倍的核心原因
本质是同为O(n log n)时间复杂度的操作,实际运行的常数因子差了一个数量级以上。大O记号只描述输入规模增长时的耗时趋势,完全忽略基础操作的实际开销,根本反映不了真实运行速度,具体差异拆解开就是这几点:
- 最大的开销差来自
std::map的实现特性- 慢代码使用的
std::map是基于红黑树实现的关联容器,每次查找、插入虽然理论上是O(log n),但单步操作的常数因子极高:每个树节点要存储父指针、左右子指针、节点颜色,内存完全分散不连续,CPU缓存命中率极低;每次操作要顺着树的分支逐层寻址,频繁跨内存页,这种操作的单步耗时是连续内存操作的10~20倍都是常态。 - 慢代码里每个元素实际触发了两次独立的红黑树查找:先调用
count()判断目标值是否存在,再用[]运算符取对应的值,等于同一次查找逻辑跑了两遍,平白把map的操作开销翻了一倍。
- 慢代码使用的
- 输入输出的基础速度差
- 快代码开头加了
ios::sync_with_stdio(false); cin.tie(0);,直接关掉了C++流和C标准IO的同步,把cin的实际读取速度拉到和scanf同级别;而慢代码没加这行配置,cin默认状态下的读取速度本身就比关同步后慢3~5倍。
- 快代码开头加了
- 额外的内存中转开销
- 慢代码先把所有元素读进
vector<int> a存一遍,再二次遍历数组把元素插入map,等于数组多了一次全量的顺序读操作;而快代码读入的时候直接把数值和原始下标存在连续的pair数组里,没有额外的vector中转环节。
- 慢代码先把所有元素读进
关于你之前的疑惑——觉得快代码多了一次全数组排序,按理应该更慢——实际情况是,标准库std::sort的常数因子极低:它是内省排序实现,全程在连续内存上操作,CPU缓存命中率极高,哪怕做一次全数组排序,整体耗时都比把n个元素插入红黑树的耗时低一个数量级。举个实际的量级参考:n=2e5的规模下,全数组排序的耗时可能只要10ms,而把2e5个元素逐一插入红黑树的耗时可能就到200ms以上,根本不是一个量级。
内容的提问来源于stack exchange,提问作者antho
相关产品推荐
相关产品推荐

