第6章 Set Intersection：有序集合交

从倒排索引的双指针归并出发，用相互分割与倍增搜索适配悬殊表长，再以两级块索引和差分压缩改善外存访问。

学习目标

能解释“6 Set Intersection”如何根据集合规模比在归并、相互分割、倍增搜索与块索引间切换
能逐项核对Merge-Based Approach、Mutual Partitioning、Doubling Search、Two-Level Storage Approach，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“work = O(m log(n/m))，m ≤ n”手算一个最小样例，并找到输出或成本的首个分叉
能注入“忽略重复键或越过倍增搜索边界，产生漏报、重复输出或越界访问”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“6 Set Intersection”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“6 Set Intersection”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“根据集合规模比在归并、相互分割、倍增搜索与块索引间切换”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：6 Set Intersection

6.1 Merge-Based Approach：在本页正文中以“根据集合规模比在归并、相互分割、倍增搜索与块索引间切换”的对象、状态、复杂度或工程边界核对。
6.2 Mutual Partitioning：在本页正文中以“根据集合规模比在归并、相互分割、倍增搜索与块索引间切换”的对象、状态、复杂度或工程边界核对。
6.3 Doubling Search：在本页正文中以“根据集合规模比在归并、相互分割、倍增搜索与块索引间切换”的对象、状态、复杂度或工程边界核对。
6.4 Two-Level Storage Approach：在本页正文中以“根据集合规模比在归并、相互分割、倍增搜索与块索引间切换”的对象、状态、复杂度或工程边界核对。

从搜索引擎的 AND 查询开始

文本搜索引擎用保存每个词出现在哪些文档。查询 “abaco AND mathematics” 不必重扫文档集合，只需取两个词的 docID posting lists 并计算共同编号。

先预测两种查询的最佳策略。若两个 posting list 都有一百万项，双指针虽然要处理约两百万个整数，却能连续读取并充分利用每个页面；若短表只有10项、长表仍有一百万项，完整扫描长表显然浪费，此时应让10个候选驱动定位。但若简单对每项都从长表中央重新二分，又会重复触碰相同缓存线和磁盘页。后续算法的目标正是同时利用“短表很短”和“两表都已递增”：已经证明不可能匹配的长表前缀永不再看，并尽量把跳跃控制在可顺序处理的局部块内。因此查询优化器至少要掌握列表长度、压缩块大小和缓存层级，才能在执行前选择合理路径。

若两表无序，逐项两两比较需要 nm 次；常见词的列表可含数百万项，这个代价无法接受。预处理时把每个 posting list 按 docID 严格递增排列，问题变成 set intersection。

先明确语义：严格递增意味着输入是真集合，不含重复 docID。若输入允许重复，就必须选择集合交还是 multiset intersection；后者输出次数是两侧计数的较小值，算法和测试契约都不同。

归并式求交：每次丢掉一个不可能值

merge-based approach从两表左端开始：

A[i] 小于 B[j] 时，A[i] 不可能与 B[j] 及其后更大值相等，推进 i；
A[i] 大于 B[j] 时，同理推进 j；
二者相等时输出该值，两个指针都推进。

std::vector<int> intersect_sorted(
    std::span<const int> a,
    std::span<const int> b) {
    std::vector<int> result;
    std::size_t i = 0;
    std::size_t j = 0;
 
    while (i != a.size() && j != b.size()) {
        if (a[i] < b[j]) {
            ++i;
        } else if (b[j] < a[i]) {
            ++j;
        } else {
            result.push_back(a[i]);
            ++i;
            ++j;
        }
    }
    return result;
}

每次比较至少推进一个指针，故时间：

T_{\mathrm{merge}}(n,m) = O(n+m)

若 n 与 m 同阶，这是必须读取输入的最优算法。访问完全顺序，外存只需 O((n+m)/B) I/O，而且不依赖 B 写进代码，是简单的 cache-oblivious 扫描。

表长悬殊时不要扫描整个长表

令 m 不大于 n。若短表 B 只有少数项，可对每个 B[j] 在长表 A 中二分，时间 O(m log n)。当 m 远小于 n/log n 时优于扫描 n 项，但每次二分反复检查 A 的中间位置，并产生随机内存或磁盘访问。

更精确的目标应同时适应 m约等于n与m远小于n：

T^\star(n,m) = \Theta\left( m\left(1+\log\frac{n}{m}\right) \right)

当 m与n同阶，对数项为常数，退化到 O(n)；当 m 很小，则接近 m log n。本页给出相互分割和倍增搜索两种达到该比较界的算法。

相互分割：用短表中位数同时切两表

mutual partitioning先交换角色保证 B 较短，再取 B 中位数 p，在 A 中二分。

若 p 出现在 A 中就输出。p 把 B 近似对半，也把 A 分为小于与大于 p 两段；只需递归 A 左与 B 左、A 右与 B 右，跨侧元素不可能相等。

MutualIntersect(A, B):
  if B is longer than A: swap A and B
  if B is empty: return
  p = median of B
  j = lower_bound(A, p)
  if A[j] == p: output p
  MutualIntersect(A before j, B before p)
  MutualIntersect(A after j, B after p)

看似 A 的不平衡划分会很糟，实际恰好相反：若 p 落在 A 范围外，A 一侧为空，对应的半个 B 立即丢弃；若两表都均分，则递归树有 O(m) 个节点，每层二分的长表规模也下降。

总时间为 O(m(1+log(n/m)))。比较下界来自至少有组合数 C(n,m) 种“B 是 A 子集”的可能位置：

\log\binom{n}{m} = \Omega\left( m\log\frac{n}{m} \right)

所以它在比较模型中最优。但递归分配、许多 binary search 与不连续访问，让渐进最优不自动成为磁盘最快。

倍增搜索：从上次位置向右跳

doubling search（，也叫 galloping/exponential search）利用两表递增。处理完 B[j-1] 后，下一项 B[j] 只可能出现在 A 的当前位置右侧。

从该位置起探测 A[i+1]、A[i+2]、A[i+4]、A[i+8]，直到越过 B[j] 或数组末端；再在最后包围窗口内二分。定位后把 i 推到 B[j] 的插入位置，下一项不再看左侧。

std::size_t gallop_lower_bound(
    std::span<const int> a,
    std::size_t first,
    int target) {
    if (first == a.size() || a[first] >= target)
        return first;
 
    std::size_t step = 1;
    while (first + step < a.size() &&
           a[first + step] < target)
        step *= 2;
 
    const std::size_t low =
        first + step / 2 + 1;
    const std::size_t high =
        std::min(first + step + 1, a.size());
    return static_cast<std::size_t>(
        std::lower_bound(
            a.begin() + low,
            a.begin() + high,
            target) - a.begin());
}

记第 j 次搜索的最后窗口长为 Delta_j。窗口小于实际向右进度的两倍，因此所有进度望远镜求和后有：

\sum_{j=1}^{m}\Delta_j \le 2n, \qquad \sum_{j=1}^{m}\log\Delta_j \le m\log\frac{2n}{m}

第二式由对数凹性得到，所以总时间仍是 O(m(1+log(n/m)))。它避免递归，却仍按指数位置跳过 A；对缓存和磁盘来说，这些跳跃可能一探测就换一页。

两级存储求交：先看块首，再顺扫候选块

two-level storage approach把 A 切成长度 L 的 A_i，并把每块首元素复制到 A0。

第一阶段归并 A0 与 B，把每个 B 项分配到可能所在的 A_i；第二阶段只对 B_i 非空的块做局部归并。最多有 m 个候选块。

TwoLevelIntersect(A0, blocks, B):
  groups = merge B with block heads A0
  for each nonempty group B_i:
    decode block A_i sequentially
    merge-intersect A_i with B_i

RAM 时间与 I/O 分别可写为：

O\left(\frac{n}{L}+mL\right), \qquad O\left( \frac{n}{LB} +\frac{mL}{B} +m \right)

第一项扫描稀疏首级，第二项读取候选块，第三项反映每个分散候选块至少触发一次 I/O。L 太小使首级膨胀，L 太大使每个候选块扫描过多；外存常让 L 与页容量同阶，再按列表比率和压缩块大小调参。

块内递增 docID 适合。局部扫描可边解码边求交，少读的字节常抵消解码 CPU；首级索引宜保持定长和未压缩，以便快速定位。

随机置换与分桶让跳过更彻底

本页还把所有列表的 docID 先用同一个可逆随机 permutation pi 映射，再按映射值高位分桶。若 z 同时属于 A、B，则 pi(z) 在两边相同；桶标签不同的子表无需读取。

随机映射让元素近似均匀落桶，控制最大 gap，块内差分需要的位数更小。查询命中 pi(z) 后必须用 pi 的逆映射恢复原 docID。

这一路线的平均时间可降到 O(m+min(n,mL))，I/O 约 O(m+min(n/B,mL/B))，并能跳过 A 中没有对应 B 桶的整块。优势来自共同映射、桶目录和压缩一起设计，而不是单独“打乱更快”。

为查询分布选择自适应策略

搜索引擎不是只求一次两表交。多词 AND 查询通常先按 posting list 长度升序求交，让中间结果尽快缩小；也可把最短表的元素作为驱动，在长表上使用块索引或 galloping。

实现应基于 n/m、块压缩格式、缓存状态与查询并发选择路径：长度接近时 zipper merge 最稳定；短表极小时块索引和倍增有优势；压缩外存表优先顺序解码候选块。原稿实验也提示，相互分割虽渐进最优，递归常数可能输给两级 skipper。

测试要验证输出严格递增、属于两侧、没有漏项；用哈希集合预言机对随机短表对拍。还应覆盖空表、无交集、全包含、交集在首尾、长度比极端、块边界命中、重复输入拒绝或去重，以及压缩解码跨块。

性能基准同时记录比较数、解码整数数、读取块数、字节数、随机页数和中间结果大小。这样才能判断收益来自算法跳过、压缩减流量还是缓存偶然命中。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“6 Set Intersection”中先预测层级和访问模式如何改变“work = O(m log(n/m))，m ≤ n”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

6 Set Intersection

根据集合规模比在归并、相互分割、倍增搜索与块索引间切换

工作集所在层级

规模8192

传输256

相对成本8×

work = O(m log(n/m))，m ≤ n

不变量：结果只包含两边共有元素，保持排序并明确集合与多重集合语义

可重放工程合同

“6 Set Intersection”的实验必须保留：两表长度、探测位置、分割点、比较次数、块访问与朴素求交结果。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “6 Set Intersection”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“work = O(m log(n/m))，m ≤ n”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“忽略重复键或越过倍增搜索边界，产生漏报、重复输出或越界访问”已经修复？

本章回顾

倒排索引把多词 AND 查询转化为多个有序 docID 集合交。
双指针归并 O(n+m) 时间、连续访问，列表长度接近时最优。
对短表每项二分可降比较数，却会反复随机访问长表。
相互分割以短表中位数同时切两表，达到 O(m(1+log(n/m)))。
倍增搜索从上次位置指数探测，在同一比较界下避免递归。
比较最优不代表 I/O 最优，二分和跳跃仍会频繁换页。
两级存储用块首索引筛候选，再局部归并长度 L 的块。
差分压缩可边解码边求交，减少外存字节流量。
共同可逆随机置换与分桶可跳过更多空配对块，但必须保持跨列表一致。