python - 比较两个点元组列表的更快方法？

Question

我有两个列表(长度可能相同也可能不同)。在每个列表中，是一系列两点元组(基本上是 X、Y 值)。

我正在将两个列表相互比较以找到具有相似点值的两个点。我已经尝试过列表理解技术，但它确实与列表中的嵌套元组混淆，我无法让它工作。

这是最好(最快)的方法吗？我觉得可能有一种更 Pythonic 的方式来做到这一点。

假设我有两个列表:

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

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

matchedPairs = []
tolerance = 2

然后这个循环解包元组，比较差异，并将它们添加到 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))

这将导致 matchedPairs 看起来像这样，其中包含两个点元组的元组:

[( (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