从两个数组中提取接近的配对的更快方法？

Question

假设我有两个随机的int数组，如下：

int A[] = {484, 834, 591, 23, 174, 248, 147, 765};
int B[] = {659, 805, 12, 180, 771, 386, 354, 568, 710, 312, 6, 848};

我希望能够从两个数组中分别找到所有接近的数对，其中两个int之间的差不大于某个固定值k，例如50：

(from A, from B)
(834, 805)
(834, 848)
(591, 568)
(23, 12)
(23, 6)
(174, 180)
(147, 180)
(765, 805)
(765, 771)

一种简单的做法是使用嵌套的 for 循环：

for (int a : A) {
  for (int b : B) {
    if (abs(a - b) < k)
      // find (a, b)
  }
}

但这需要 O(n^2) 的时间复杂度，似乎不太高效。是否有更好的方法，无论空间成本如何？

- 康桓瑋

---

我建议先去除语法糖，并使用测量方法检查性能瓶颈。但我怀疑是否有更快的方法。如果有优化潜力，给我们提供一个完整的示例可能会取决于具体的上下文。 - πάντα ῥεῖ

@πάνταῥεῖ 谢谢您的回复，我已经更改了描述。 - 康桓瑋

一个简单的改进是使用二分查找来找到极值之一，并将其用作起点。这是log(n)而不是n，使得总体复杂度为O(n*(log n + k)))，但考虑到k是固定的，这更好。 - Voo

@康桓瑋 嗯，我认为优化的潜力可能在于使用不同的数据结构，该数据结构针对您要查找的条件进行了优化。 - πάντα ῥεῖ

“Adjacent”这个词有点让我困惑。它们是什么意义上相邻？只是指它们的差值小于50吗？ - 463035818_is_not_a_number

Answer 1

您可以使用 O(N log N) 的时间复杂度（加上可能超过 N log N 的结果对数）进行以下操作：

std::sort(std::begin(A), std::end(A)); // O(N log N)
std::sort(std::begin(B), std::end(B)); // O(N log N)

auto begin = std::begin(B);
auto end = begin;
for (auto v : A) {
    while (begin != std::end(B) && *begin < v - 50) ++begin;
    while (end != std::end(B) && *end < v + 50) ++end;
    for (auto it = begin; it != end; ++it) {
        std::cout << '(' << v << ", " << *it << ")\n";
    }
}

演示

- Jarod42

---

请注意，如果元素不需要唯一，则这是n^2的最坏情况。尽管如此，在这种情况下仍然是正确的。 - Voo

我认为begin应该用std::lower_bound初始化，而end应该用std::upper_bound初始化，在嵌套循环中它们也应该被赋值为std::lower_bound和std::upper_bound。 - 康桓瑋

@康桓瑋：一旦排序，我们就是线性的（除了显示结果）：我们使用for循环范围遍历一次A。同时begin/end也会遍历B一次，因此A.size() + 2 * B.size()。在循环中使用lower_bound会引入N个对数搜索。我认为这是一个错误的好主意。 - Jarod42

@Voo：结果的大小确实可能是O(N²)。不确定您所说的唯一性是什么意思（从输入的A和B中过滤重复项一旦排序就是线性的）... - Jarod42

如果元素都是唯一的，结果将为O(n log n)。如果数组中可能有重复项，则最坏情况下所有元素都相同，结果将为O(n^2)（即笛卡尔积作为结果）。 - Voo

Answer 2

尝试a）对第二个数组进行二分搜索b）记住第二个数组中先前的位置并c）跟踪第一个数组中元素之间的距离。第一步是log（n）而不是n，第二步使后续搜索的搜索空间更小。第三步重用以前的距离计算。

例如，二进制搜索与432的最大距离为50的项目，给出最低和最高索引3和6。对于下一个元素615，您可以忽略低于最低索引3的项目。这就是a）和b）。请参见https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure_for_finding_the_leftmost_element 对于许多数组，您可以通过存储先前搜索的最大距离值来节省计算。对于427，您将存储394和473，它们的索引和距离值，即（3，-33）和（6，46）。假设下一个项目是430。现在，您可以只检查与上一个元素的距离abs（430-427），并从存储的距离中减去它，得到-36和43。然后您可以得出结论，430具有427的距离集的超集，而无需搜索这些元素。假设下一个值为615。这使您获得abs（615-427）或188，因此您会获得-221和-142。两者都太大了，所以您可以跳过所有这些元素，并从索引7（6 + 1）开始进行二进制搜索，而不是从3开始。

注意：编辑后的OP不再相同，数组已排序并具有不同的值。

- dssjoblom

---

最坏情况并不是n^2，假设元素是唯一的且k是固定大小。 - Voo

@Voo，独特性很重要吗？我删除了关于假定最坏情况复杂度的部分，并稍微修改了文本。现在看起来即使有重复项，它的时间复杂度也是n log n，或者我漏掉了什么？ - dssjoblom

假设A和B中的所有元素都相等，那么结果应该是两个集合的笛卡尔积。笛卡尔积的基数|A x B|为|A| * |B|。因此，如果允许重复并且比n^2更好，则会漏掉一些对。 - Voo

@Voo 我认为这并不是必要的，它取决于输出的数据表示方式，而且据我所知，问题是关于有多少个 abs 调用被执行，而不是关于输出的内容。假设你有 [1,1,1] 和 [1,1,1]。朴素的实现方法是输出 1 => [1,1,1] 三次。另一个可能性是使用超集合的想法 c) 来使其变成 0 => [0,2]，1 => link(0)，2 = link(0)，也就是链接到共享段。左侧是 A 中的索引，右侧是 B 中的范围。你不需要重新检查每一对元素的范围，因为两个数组都已经排序了。再看一下 c) 部分。 - dssjoblom

根据我所看到的，你集合的输出应该是 (1,1),(1,1),(1,1),..。问题中也说了“我希望找到所有相近的对”，没有提到绝对值调用。我猜你可能能够将其优化为 6x (1,1)，但我需要先看到详细的算法——这些东西的细节才是最重要的。 - Voo

Answer 3

我建议利用没有空间成本和处理整数的事实，使用它来找到一个时间复杂度为O(n)的算法，或者按照Alex的定义，每个数组长度都用不同的变量（我完全同意），时间复杂度为O(n+m)。

1. 遍历第一个数组（称其为A-长度为n），并定义一个新数组，其中每个单元格指向一个链表，该链表将包含来自A的所有相关项。对于每个元素a，在位置[a-50：a+50]处添加其编号以添加到链表中。这个构造是O(n)
2. 遍历第二个数组（称之为B-长度为m）中的每个元素b，从A中选择与之相关的元素在单元格b中。时间复杂度O(m)

- antonpuz

---

O(n+m) …转换成(k * numeric_limits<unsigned int>)，即使巨大的数字是常数 ;) - Jarod42

Answer 4

基于Jarod42的答案，我尝试将所有内容提炼成标准算法和容器，然后得到了如下内容。

#include <set>

void print_close_pairs(vector<int> const& A, vector<int> const & B){
    auto a = std::multiset<int>(A.cbegin(),A.cend()); // O(n * log(n))
    auto b = std::multiset<int>(B.cbegin(),B.cend()); // O(m * log(m))

    for (auto v: a){ // O(n)
        auto beg = b.lower_bound(v - 50); // O(log(m))
        auto end = b.upper_bound(v + 50); // O(log(m))
        for (; beg != end; beg++) { // O(m)
            std::cout << '(' << v << ", " << *beg << ")\n";
        }
    }
}

我们看到A和B需要分别作为复杂性变量n和m进行处理。我们还发现只需要将其中一个输入放入集合（或排序）。因此，虽然我们无法避免O(n * m)的复杂度，但仍然做了很多额外的工作。

void mark_pairs(vector<int> const& A, vector<int> const & B){
    auto b = std::multiset<int>(B.cbegin(),B.cend()); // O(m * log(m))

    for (auto v: A){ // O(n)
        auto beg = b.lower_bound(v - 50); // O(log(m))
        auto end = b.upper_bound(v + 50); // O(log(m))
        for (; beg != end; beg++) { // O(m)
            std::cout << '(' << v << ", " << *beg << ")\n";
        }
    }
}

除此之外，你可以做一些事情来处理数据，使其仅适用于最小的子集，但我认为你真正受限于O(n*m)的复杂度。

顺便提一下：要注意仅进行排序，因为你可能会意外地遇到O(n² + m²)的最坏时间复杂度。

- Alex Shirley

---

你的 lower_bound 调用使得第二部分变成了 O(n log m)，而我的是线性的（但需要有序输入(O(n log n)））。 （我也会把结果大小视为其他变量来允许 O(max(N log N, M log M, result_size)) 的讨论/比较。） - Jarod42

@Jarod42 是的。我想到的其中一个扩展是选择较短的向量来构建多重集合，另一个作为“搜索键”。第二个函数的操作为 O(m * log (m)) + O(n (2*log(m) + m))，因为 m 占主导地位，从两个数组中较小的那个创建多重集合可能会提高速度。 - Alex Shirley