比较两个点元组列表的更快方法是什么？

Question

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

我正在将这两个列表相互比较，以找到具有相似点值的两个点。我尝试了列表推导技术，但由于列表中嵌套的元组太多，我很难理解并且无法使其正常工作。

这是做这件事情的最佳（最快）方法吗？我觉得可能有更符合Python风格的方法。

假设我有两个列表：

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) )]

- STH

---

如果您可以使用“距离”代替公差的平方，那么您可以使用复数而不是元组，例如[2+1j, 4+8j]。然后，您可以将abs（pt1-pt2）与公差进行比较。 - John La Rooy

Answer 1

如果这些列表很大，我建议找到更快的算法...

首先，我会按照对于(x,y)的和排序两个配对列表。(因为只有当它们的和接近时两个点才会接近)

对于第一个列表中的任何一个点，这将严重限制您需要在第二个列表中搜索的范围。在第二个列表上保持一个“滑动窗口”，与第一个列表当前元素的总和相差不超过2*tolerance的元素相对应。(实际上，您只需要跟踪滑动窗口的起始位置...)

假设tolerance是相当小的，这应该可以将您的O(n^2)操作转换为O(n log n)。

- Nemo

---

抱歉我之前没有提到，这些列表并不是很大。事实上，目前它们永远不会超过15个元组的长度，而且大多数只有约14个元素。 - STH

Answer 2

这里的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

- John La Rooy

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]

略微比你的循环快：

(for 1 million executions)

>>> (list comprehension).timeit()
2.1963138580322266 s

>>> (your method).timeit()
2.454944133758545 s

- manji

---

我明白我之前做错了什么，谢谢你的例子。那正是我需要的一行代码。稍微快了一点，我相信这会累加起来：我有一个列表，需要与其他2万个列表进行比较。 - STH

@STH，由于您正在将一个列表与其他20k个列表进行比较，因此花费一些时间从这个列表中创建字典或集合可能是有意义的，从而允许在20k个列表中进行快速查找。这些值总是整数吗？ 对于容差为2，字典的大小将是列表的25倍，但是20k个比较将是O（N）。 - John La Rooy

@gnibbler 你的意思是将第一个列表作为字典或集合，而不是其他20k个列表，对吗？这些值始终为整数。这20k个列表在被pickle后存储在MySQL数据库中。 - STH

只是想让你知道我的速度差异。在转换为一行代码后，整个函数运行一次的速度从1.80秒变为0.87秒。 - STH

@STH，是的，我现在已经在答案中提供了这个。 - John La Rooy