algorithm - 如何找到两个数组之间所有互斥的最近邻居

Question

我有两个排序的数字数组。第一个数组是一组 n 个整数，它们是在数组边界之间等距分布的目标。第二个数组有 n 个整数的大倍数，也是一个集合。我想从第二个数组中找到最接近第一个数组中所有目标的 n 个整数，条件是第二个数组中只有一个整数可以匹配第一个数组中的任何目标。也就是说，所有匹配都是互斥的。

感谢您的帮助!

编辑:

抱歉缺少细节。这是对实际问题的简化。

具有常规目标的第一个简单数组示例:[0x0,0x7FFFFFFF,0xFFFFFFF]

第二个数组本质上是没有重复的随机数据，均匀分布在第一个数组的范围内。也就是说，在 0x0 和 0xFFFFFFFF 之间可能有 2000 个整数。我需要第二个数组中最接近第一个数组中的目标的三个整数。在实际问题中，目标将具有更小的范围和更多的目标，并且总是有规律地间隔开。

编辑:更多上下文。

一个大数组 B 是一个随机的 32 字节散列流，这些散列已经排序并被装入 n 叉树中。对于每个节点，都有已知的限制 u 和 v。数组 A 是通过将 u 和 v 分成 n-1 个步幅来构造的。对于 u 和 v 之间的每个 B 子集，尝试找到 B 中最接近 n-1 个步幅之一的成员。然后使用这些选定的成员进一步过滤 B 下面的每个子节点。它基本上是用于平衡包含随机数据的树的启发式方法。深度节点需要考虑的 B 逐渐变小。 A 总是固定长度。

Answer 1

首先让我尝试正式地说明问题。调用第一组数字 A 和第二组 B。我们想要一个单射映射 f : A -> B(单射意味着 x != y 意味着 f(x) != f(y))最小化一些目标函数来衡量所有 x f(x) 与 x 的接近程度。有多种合理的选择，所以我会为你选择一个:让我们最小化 sum_{x in A} |f(x) - x|。 (这个答案的其余部分在某种程度上与确切的目标无关，只要某个最佳 f 是递增函数即可。)

贪婪算法(定义，对于 A 中的所有 x，值 f(x) 是 B 中的 y 最小化 |x - y|)失败，因为它选择的 f 可能不是单射的。通常的修复技术是动态规划，它有效但需要二次而不是线性时间。这是一个未经测试的 Python 示例，它应该计算最佳目标值。 table[(i, j)] 的值是将 A 的前 i 元素映射到第一个 的最佳成本B 的 j 元素。

def assign(A, B):
    m = len(A)
    n = len(B)
    table = {(0, j): 0 for j in range(n + 1)}
    for i in range(1, m + 1):
        table[(i, 0)] = 1e309  # infinity
        for j in range(1, n + 1):
            table[(i, j)] = min(table[(i - 1, j - 1)] + abs(A[i - 1] - B[j - 1]),
                                table[(i, j - 1)])
    return table[(m, n)]

为了在最后恢复匹配，我们扩展代码以在每个表中创建另一个条目，指示采用了 min 的哪个分支，然后将决策追溯到 (0, j)条目。

现在，我不知道你的问题有多大，也不知道你想要多快的结果，但我们假设无论出于何种原因，二次时间都是 Not Acceptable 。一般来说，上面的代码考虑了许多彼此相距很远的元素之间明显愚蠢的匹配。下面我将“显然很傻”做成一个技术术语，有一个有效的定义和一个线性时间算法。然后我们可以用更小的东西替换内部循环中考虑的 j 的范围，希望平均为线性大小，因为 B 比 A 密集得多并且呈半合理分布。运行时间相应减少。

请注意，将 A 中的最小值 x 与任何大于 min {y : y in B, y >= x} 的值匹配是没有意义的，我将其称为 x 的上邻域。如果我们这样做了，并且 f 正在增加，那么我们可以将 f(x) 更改为 x 的上邻居并在不违反约束的情况下提高目标值。如果我们贪婪地将 A 中的每个元素 x' 从最小到最大分配给 B 中不小于 x' 的最低可用 y'，那么我们可以通过归纳证明存在一个最优解，其中每个 x' 匹配的值不大于比它的y'。此外，我们可以按如下方式在线性时间内计算这些值(更多未经测试的 Python)。

def uppers(A, B):
    n = len(B)
    j = 0
    for x in A:
        while j < n and B[j] < x:
            j += 1
        if j < n:
            j += 1
        yield j  # exclusive upper bound

对称地，我们可以计算下界。将这些范围之外的任何赋值称为“显然很愚蠢”，并按照之前的描述进行。