两个有序随机访问序列的最小比较合并

问题

到 2014 年底，我在思考如何高效地合并两个有序序列。

如果你认为复制元素的成本大致与比较元素的成本相当，那么答案显然是显而易见的。在这种情况下，只需比较每个序列的剩余的第一个元素，取较小的一个，直到其中一个序列中的元素耗尽，然后只需复制剩余的部分。

但在许多情况下，这种认为比较的成本与复制的成本相当的假设是不正确的。假设你有一个包含 BigInt、Rational、非常长的 String 或复杂元组的序列。在这种情况下，比较两个元素的成本将是复制一个元素的 几个数量级 更高。

因此，让我们考虑这样一种情况：只有比较的次数才是重要的，而复制被认为是基本免费的（复制指针是你能做的最便宜的操作之一。你可以在现代机器上在不到一毫秒内复制数百万个指针）。

在这种情况下，合并两个有序列表的看似简单的问题变成了一个问题，这个问题在 TAOCP 中有 10 页 的内容（第 3 卷，第 197-207 页，最小比较合并）。

所以我就做了你通常在这种情况下会做的事情：在 StackExchange 上提问。鉴于这应该是一个相当常见的问题，我预计会得到一个类似于“显然你必须使用 XYZ 在 1969 年描述的 Foo-Bar 算法”这样的答案。但令我惊讶的是，作为答案发布的算法，尽管被称为 A simple algorithm for merging two disjoint linearly-ordered sets (F. K. Hwang , S. Lin)，并不是很简单。它是渐近最优的，但在比较相对便宜的情况下，实现起来过于复杂。而且，它的实现也很复杂。

所以我就试图找到一个更简单的解决方案。

情况

在合并两个有序序列时，必须考虑几种情况。为任何一种情况提出一个好的解决方案都是简单的。挑战在于找到一个解决方案，它适用于 所有 的情况，并且在最坏的情况下表现良好。

a) 合并长序列与单元素序列

a = [1,2,3,4,6,7,8,9,10]
b = [5]

在这种情况下，最好的解决方案是对单元素 b 在 a 中的插入点进行二分查找，然后直接复制

• a 中 b[0] 以下的部分
• 元素 b[0]
• a 中 b[0] 以下的部分

显然，可以对这个解决方案进行特殊处理。但这不够优雅，而且无论如何，在b)的情况下也不会有帮助

b) 合并长序列和短序列

a = [1,2,4,5,6,7,9,10]
b = [3,8]

在这种情况下，你可能想直接将较小列表的所有元素插入到较大列表中，并对每个插入进行二分查找。但这并不理想。从第一个元素的插入位置，我们知道哪些元素肯定小于第二个元素，因此不需要比较，因此我们可以根据第一个二分查找的结果限制第二个二分查找的范围。

c) 合并非重叠的两个大序列

a = [1,2,3,4,5]
b = [6,7,8,9,10]

这是一个可以预期获得巨大性能提升的情况，因为你只需要依次复制列表。你可以通过比较一个序列的第一个元素与另一个序列的最后一个元素，反之亦然来检测这种情况。但比较的成本将在其他情况下产生开销，因此只有当你知道这种情况非常常见时（我们不知道），才能证明这是合理的。

d) 完全交错的两个序列的合并

a = [1,3,5,7,9]
b = [2,4,6,8,10]

这是最坏的情况，无法比线性合并得到更好的结果。任何好的算法都应该优雅地处理这种情况，而无需进行比 m + n - 1 次比较更多的操作。根据你预期的平均情况，进行两倍的比较可能仍然是可以接受的。但例如，o(m log n) 次比较，如通过将较小列表的所有 n 个元素插入到有 m 个元素的较大列表中，将不会是可接受的。

设计一个好的算法

作为一个函数式程序员，我认为最优雅的算法是递归的。所以，让我们考虑递归步骤看起来会是什么样子。

命名

让我们使用 a0 和 a1 分别表示当前感兴趣 a 的第一个（包含）和最后一个（不包含）索引。同样，使用 b0 和 b1 分别表示当前感兴趣 b 的第一个（包含）和最后一个（不包含）索引。

基本案例

在我们考虑复杂的事情之前，让我们考虑基本案例。将序列的一部分与另一个序列的空部分合并意味着只需将感兴趣的序列的所有元素复制到目标序列中。所以如果 a0 是 a1，只需将 b0 到 b1 之间的所有内容复制到结果中，反之亦然。

第一次比较

很明显，为了将比较的次数降到最少，我们必须从每次比较中获得最大信息。因此，直观上似乎很明显，我们必须将a的中间元素与b的中间元素进行比较。无论比较的结果如何，我们都已经获得了所有可能的比较中四分之一的信息，只需一次比较即可。如果你有一个大小为m * n的表格，每个单元格都是一个可能的比较，执行表格中心的比较可以让你消除表格的一个象限。

am = (a0 + a1) / 2
bm = (b0 + b1) / 2

a(am) < b(bm)，所以所有元素a[i], a0 ≤ i ≤ am都小于所有元素b[j], bm ≤ j < b1。

递归步骤

既然我们已经知道第一次比较要做什么，我们该如何处理它？我想出的办法如下：我们使用二分搜索来查找a的中间元素的插入索引在b中。二分搜索的第一次比较将正好像上面描述的那样。一旦我们得到了结果，我们可以将其称为bm，然后我们可以递归。

我们需要合并来自a的元素a0 until am与来自b的元素b0 until bm。然后我们需要将单个元素a(am)复制到结果中，最后合并来自a的元素am + 1 until a1与来自b的元素bm + 1 until b1。

就是这样。以下是我们的代码，适用于a和b是不相交有序集合的情况。

    fn binary_merge(&self, m: &mut M, an: usize, bn: usize) -> bool {
        if an == 0 {
            bn == 0 || self.from_b(m, bn)
        } else if bn == 0 {
            an == 0 || self.from_a(m, an)
        } else {
            // neither a nor b are 0
            let am: usize = an / 2;
            // pick the center element of a and find the corresponding one in b using binary search
            let a = &m.a_slice()[am];
            match m.b_slice()[..bn].binary_search_by(|b| self.cmp(a, b).reverse()) {
                Ok(bm) => {
                    // same elements. bm is the index corresponding to am
                    // merge everything below am with everything below the found element bm
                    self.binary_merge(m, am, bm) &&
                    // add the elements a(am) and b(bm)
                    self.collision(m) &&
                    // merge everything above a(am) with everything above the found element
                    self.binary_merge(m, an - am - 1, bn - bm - 1)
                }
                Err(bi) => {
                    // not found. bi is the insertion point
                    // merge everything below a(am) with everything below the found insertion point bi
                    self.binary_merge(m, am, bi) &&
                    // add a(am)
                    self.from_a(m, 1) &&
                    // everything above a(am) with everything above the found insertion point
                    self.binary_merge(m, an - am - 1, bn - bi)
                }
            }
        }
    }

请注意，尽管此方法使用递归，但它不是引用透明的。结果序列是通过使用可变构建器来提高效率的，在fromA和fromB方法中构建。当然，你通常会用一种引用透明的方式包装此算法。

此外，请注意，在spire中的版本稍微复杂一些，因为它还适用于a和b中有公共元素的情况，并且有时拥有插入点是一个优点。

以下是一个示例，说明如何使用合并策略将两个有序的Array[T]与给定的Order[T]合并。