知识卡片
双指针求有序列表交集
倒排列表按文档 ID 排序后,可用两个指针求交集:相等时记录该 ID 并前进;不等时前进较小值所在列表的指针。每轮至少推进一个指针,扫描成本随两表长度之和增长,避免双重循环逐项配对。多词查询可逐次求交集,但耗时仍取决于倒排列表长度和命中分布。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《架构师之路》第54章《深入浅出搜索架构引擎、方案与细节(上)》(源文件:_epub-src/OEBPS/Text/54.html)
- 结论依据:原文把有序倒排列表交集称为拉链法,描述双指针遇相等取结果、否则移动较小值,且每个元素最多比较一次。
- 原始内容:两个指针指向首元素,比较元素的大小: (1)如果相同,放入结果集,随意移动一个指针 (2)否则,移动值较小的一个指针,直到队尾 这种方法的好处是: