在O（N）时间复杂度或更高的情况下，从熊猫数据帧中查找最接近的元组对（在容差范围内）

问：

我面临的问题可能在循环中可以实现，但是，我需要找出一个具有最大 O（N） 时间复杂度的 pythonic 解决方案：

所以问题是这样的：

我有一个数据帧（我称之为查找）说如下：（它可能是一个非常大的数据帧，有 100M + 行）（我的 A 和 B 是要搜索的列，M、N 是我将要搜索的值，最后 col V 是我将提取的值）。所以让我明确一点。为了我们的论点，我只显示 5 行：

 lookup_df 

    A     B     M      N        V

    a1    b1    2.6   12.7     200.6
    u1    v1    4.5   19       145
    a2    b2    3.2   15.9     100
    a3    b3    5.5   21.5     45
    a7    b7    6.8   41.8     90
    a10   b10   70.0  120.5    123

所以现在的问题是我有另一个数据框，我称之为输入。因此，它可以具有确切的 A 和 B 列值，也可以具有一些新的 A 和 B 值。因此，输入可能看起来像这样（比如说）。我在这里还显示 5 行来说明这一点：

  input_df 

     A     B     M      N        

     u1   v1     4.5    19
     u1   v1     3.0    16.2
     a3   b3     5.5    21.5 
     a3   x1     7.0    41.5
     x7   y2    69.8   120.1

所以现在要解决的问题是，每当我在 A、B、M、N 之间的查找和输入数据帧中的值完全匹配时，我的 V 列就会按预期从查找中获取值。但是，例如，在输入数据帧的第二行中，A和B匹配，但M和N值不同。所以最接近的（0.3 说是我的阈值）是查找表的第 3 行，对应于 a2 和 b2 的 V，所以我选择了 V。输入中的 a3 和 b3 再次与查找 M 列和 N 列完全匹配，因此我可以拾取该 V。对于输入中的最后两行，此示例查找数据帧中没有行，因此我再次使用查找中最接近的值，对于 a3，x1 恰好是 a7，b7 的 V 中的值，对于 x7，y2 与 a10、b10 的值匹配。

因此，我的输入的输出 df 应如下所示：

 output_df 

     A     B     M      N        V

     u1   v1     4.5    19       145
     u1   v1     3.0    16.2     100
     a3   b3     5.5    21.5      45
     a3   x1     7.0    41.5      90
     x7   y2    69.8   120.1      123

所以我的查找数据框是巨大的（100M +），具有所有可能的组合。我的输入数据框可能没有那么大，可能是 10000 行，但是，假设我使用 0.3 的阈值来查找最近的一对，我怎样才能有一个有效的搜索代码来扫描查找以获得我想要的输出。