比较两个指针元组列表的更快方法？

Question

我有两个列表（长度可能相同，也可能不同）。基本上是两个点组成的一系列X值。在

我将两个列表相互比较，以找到两个点值相似的点。我尝试过列表理解技术，但是它与列表中嵌套的元组混淆了，我无法使用它。在

这是最好的（最快的）方法吗？我觉得可能还有一种更像Python的方法。在

假设我有两个列表：

pointPairA = [(2,1), (4,8)]
pointPairB = [(3,2), (10,2), (4,2)]

然后是一个空列表用于存储对，以及一个仅存储匹配对的容差值

^{pr2}$

然后这个循环将解包元组，比较差异，并将它们添加到matchedPairs列表以指示匹配。在

for pointPairA in pointPairListA:
    for pointPairB in pointPairListB:
        ## Assign the current X,Y values for each pair
        pointPairA_x, pointPairA_y = pointPairA
        pointPairB_x, pointPairB_x = pointPairB

        ## Get the difference of each set of points
        xDiff = abs(pointPairA_x - pointPairB_x)
        yDiff = abs(pointPairA1_y - pointPairB_y)

        if xDiff < tolerance and yDiff < tolerance:
            matchedPairs.append((pointPairA, pointPairB))

这将导致匹配对如下所示，其中包含两个点元组的元组：

[( (2,1), (3,2) ), ( (2,1), (4,2) )]

Answer 1

这里pointpairA是单个列表，pointpairB是20k的列表之一

from collections import defaultdict
from itertools import product

pointPairA = [(2,1), (4,8)]
pointPairB = [(3,2), (10,2), (4,2)]
tolerance = 2

dA = defaultdict(list)
tolrange = range(-tolerance, tolerance+1)
for pA, dx, dy in product(pointPairA, tolrange, tolrange):
    dA[pA[0]+dx,pA[1]+dy].append(pA)

# you would have a loop here though the 20k lists
matchedPairs = [(pA, pB) for pB in pointPairB for pA in dA[pB]]  

print matchedPairs

Answer 2

如果这些列表很大，我建议找到一个更快的算法。。。在

首先，我将根据一对中的（x，y）的和对两个成对列表进行排序。（因为只有当它们的和接近时，两点才能接近。）

对于第一个列表中的任何一个点，这将严重限制您需要在第二个列表中搜索的范围。跟踪第二个列表上的一个“滑动窗口”，对应于其和在第一个列表的当前元素和的2*tolerance之内的元素。（实际上，您只需要跟踪滑动窗口的开始…）

假设tolerance相当小，这将把O（n^2）操作转换成O（n logn）。在

Answer 3

通过列表理解：

[(pa, pb) for pa in pointPairA for pb in pointPairB \
          if abs(pa[0]-pb[0]) <= tolerance and abs(pa[1]-pb[1]) <= tolerance]

比你的循环快得多：

^{pr2}$