在两个二维数组中查找所有紧密的数值匹配

Question

更新：我将解决方案放入一个名为close-numerical-matches的库中

---

我正在寻找一种方法来查找两个2D数组之间的所有紧密匹配（在一定公差范围内），并获得所找到匹配的索引数组。上面的多个答案显示了如何解决精确匹配的问题（通常是使用字典），但这不是我想要的。让我举一个例子：

>>> arr1 = [
    [19.21, 19.19],
    [13.18, 11.55],
    [21.45,  5.83]
]
>>> arr2 = [
    [13.11, 11.54],
    [19.20, 19.19],
    [51.21, 21.55],
    [19.22, 19.18],
    [11.21, 11.55]
]
>>> find_close_match_indices(arr1, arr2, tol=0.1)
[[0, 1], [0, 3], [1, 0]]

在上面，返回[[0, 1], [0, 3], [1, 0]]，因为arr1[19.21,19.19]中的元素0在arr2中的元素1和3的容差范围内。顺序对我来说并不重要，也就是说[[0, 3], [1, 0], [0, 1]]同样可以接受

{}的形状是（n，2），而{}的形状是（m，2）。您可以预期n和m将是巨大的。现在，我可以使用嵌套的for循环轻松实现这一点，但我确信一定有比将每个元素与所有其他元素进行比较更聪明的方法

我曾考虑过使用k-means集群将问题划分为k个桶，从而使嵌套for循环方法更易于处理，但我认为可能存在一个小风险，即两个紧密元素正好位于每个集群的“边界”，因此无法进行比较

任何外部依赖项（如Numpy、Scipy等）都可以，使用O（n+m）空间也可以

Answer 1

我有了一个如何使用桶来解决这个问题的想法。其思想是根据元素的值和公差级别形成一个键。为了确保将存储桶“边缘”中的潜在匹配项与“边缘”中的其他元素进行比较，将比较所有相邻存储桶。最后，我修改了@Tim Roberts执行实际匹配的方法，使之在两列上都匹配

我把它做成了一个叫做close-numerical-matches的图书馆。示例用法：

>>> import numpy as np
>>> from close_numerical_matches import find_matches
>>> arr0 = np.array([[25, 24], [50, 50], [25, 26]])
>>> arr1 = np.array([[25, 23], [25, 25], [50.6, 50.6], [60, 60]])
>>> find_matches(arr0, arr1, tol=1.0001)
array([[0, 0], [0, 1], [1, 2], [2, 1]])
>>> find_matches(arr0, arr1, tol=0.9999)
array([[1, 2]])
>>> find_matches(arr0, arr1, tol=0.60001)
array([], dtype=int64)
>>> find_matches(arr0, arr1, tol=0.60001, dist='max')
array([[1, 2]])
>>> manhatten_dist = lambda arr: np.sum(np.abs(arr), axis=1)
>>> matches = find_matches(arr0, arr1, tol=0.11, dist=manhatten_dist)
>>> matches
array([[0, 1], [0, 1], [2, 1]])
>>> indices0, indices1 = matches.T
>>> arr0[indices0]
array([[25, 24], [25, 24], [25, 26]])

一些分析：

from timeit import default_timer as timer
import numpy as np
from close_numerical_matches import naive_find_matches, find_matches

arr0 = np.random.rand(320_000, 2)
arr1 = np.random.rand(44_000, 2)

start = timer()
naive_find_matches(arr0, arr1, tol=0.001)
end = timer()
print(end - start)  # 255.335 s

start = timer()
find_matches(arr0, arr1, tol=0.001)
end = timer()
print(end - start)  # 5.821 s