8核CPU下提高多个有序链表合并的吞吐量
哪些公司问过
答案要点
- 单线程基线:小顶堆或败者树做 k 路归并,O(N log k)
- 分治两两合并可并行,但后几轮并行度下降,存在尾部瓶颈
- 按值域抽样选分割点,各线程负责一段独立归并,最后顺序拼接
- 各线程处理不相交的数据,减少锁竞争,注意分段负载均衡
- 链表缓存不友好,必要时转数组提升局部性
易错点
- 只说开 8 个线程,没说明如何划分任务和合并结果
- 多个线程共享一个堆并加锁,竞争严重反而更慢
- 忽略分段不均导致部分线程空闲
面试官常见追问
- 败者树相比堆有什么好处?
- 分割点怎么选才均衡?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场