以 O(N) 或更好的时间复杂度从 pandas 数据框中找到最接近的元组对（在容差范围内）

Question

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

所以问题是这样的。

我有一个数据框（我称之为查找），如下所示：（它可能是一个 100M + 行的非常大的数据框）（我的 A 和 B 是要搜索的列，M、N 是我要搜索的值将搜索，最后我将提取第 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 是我的阈值）是对应于 a2 和 b2 的 V 的查找表的第 3 行，因此我选择 V。输入中的 a3 和 b3 再次与 M 和 N 列的查找完全匹配，因此我可以拾取对于 input 中的最后两行，此示例查找数据框中没有行，因此我再次查找查找中最接近的值，对于 a3，x1 恰好是 V 中 a7、b7 和对于 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 的阈值来查找最近的对，如何才能我有一个高效的搜索代码来扫描查找以获得所需的输出。

任何帮助都将非常有价值。如果我无法清楚地定义问题，请告诉我，我将尝试根据需要添加任何其他信息。

Answer 1

您可以将合并分为几个步骤：

1.尝试找到精确的合并

exact_matches = pd.merge(input_df, lookup_df, on=["A", "B", "M", "N"])
print(exact_matches)

打印：

    A   B    M     N      V
0  u1  v1  4.5  19.0  145.0
1  a3  b3  5.5  21.5   45.0

---

2.从

input_df

中排除精确匹配

# exclude exact matches from input_df
input_df = input_df.loc[~input_df.index.isin(exact_matches.index)]

3.合并者

M

# merge M
lookup_df = lookup_df.sort_values(by="M")
input_df = input_df.sort_values(by="M")

M_V = pd.merge_asof(
    input_df, lookup_df[["M", "V"]], on="M", direction="nearest", tolerance=0.3
)[["A", "B", "M", "N", "V"]]

4.合并者

N

# merge N
lookup_df = lookup_df.sort_values(by="N")
input_df = input_df.sort_values(by="N")

N_V = pd.merge_asof(
    input_df, lookup_df[["N", "V"]], on="N", direction="nearest", tolerance=0.3
)[["V"]]

vals = pd.concat([M_V, N_V[["V"]].add_suffix("_2")], axis=1)
print(vals)

打印：

    A   B     M      N      V   V_2
0  a3  b3   5.5   21.5   45.0  45.0
1  a3  x1   7.0   41.5   90.0  90.0
2  x7  y2  69.8  120.1  123.0   NaN

---

4.将精确匹配和公差匹配结合在一起

但是这里你必须指定逻辑（如果

V

/

V_2

的值不同怎么办？等等）现在我简单地将它们连接起来：

print(pd.concat([exact_matches, vals]))

打印：

    A   B     M      N      V   V_2
0  u1  v1   4.5   19.0  145.0   NaN
1  a3  b3   5.5   21.5   45.0   NaN
0  a3  b3   5.5   21.5   45.0  45.0
1  a3  x1   7.0   41.5   90.0  90.0
2  x7  y2  69.8  120.1  123.0   NaN