比較兩個點元組列表的更快方法？

我有兩個列表（可能是也可能不是相同的長度）。在每個列表中，有一系列兩點的元組（基本上是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))]

來源

2011-06-08 STH

的列表中一個如果你可以用「距離」，而不是爲容忍廣場，你可以使用複雜的數字，而不是元組例如。 '[2 + 1j，4 + 8j]'。然後你可以比較'abs（pt1-pt2）'和容差 – 2011-06-08 02:01:06

這裏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

來源

2011-06-08 04:08:13

+1：gnibbler先到那裏:) – tzot 2011-06-10 08:41:40

隨着列表理解：

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

來源

2011-06-08 01:14:16 manji

我明白我做錯了，謝謝你的例子。這正是我需要的一個班輪。稍微快一點，我肯定會加起來：我有一個列表，我可以比較其他20k個列表。 – STH 2011-06-08 01:45:54

@STH，由於您將一個列表與20k個其他列表進行比較，因此可能需要花費一些時間從一個列表中創建一個字典或一組列表，以便爲其他20k個列表快速查找。這些值是否始終是整數？對於2的容差，字典將是列表大小的25倍，但是20k比較將是O（N） – 2011-06-08 02:06:28

@gnibbler你的意思是將第一個列表設置爲字典或集合，而不是20k其他，對嗎？這些值將始終是整數。醃製後，20k列表存儲在MySQL數據庫中。 – STH 2011-06-08 02:09:54

如果這些列表很大，我會建議找到一個更快的算法...

我首先將這兩個對的列表按對中的（x，y）之和排序。（因爲兩點只有在它們的總和接近時才能關閉）

對於第一個列表中的任何點，這將嚴重限制您需要在第二個列表中搜索的範圍。跟蹤第二個列表上的「滑動窗口」，對應於其總和在第一個列表的當前元素的總和的2*tolerance內的元素。（實際上，你只需要跟蹤滑動窗口的開始...）

假設tolerance相當小，這應該將您的O（n^2）操作轉換爲O（n log n）。

來源

2011-06-08 01:18:46 Nemo

對不起，我沒有提到這個，名單根本不大。事實上，目前它們的長度不會超過15個元組，其中大部分長度是14個。 – STH 2011-06-08 01:44:30

比較兩個點元組列表的更快方法？

回答

相關問題