Более быстрый способ сравнения двух списков точечных кортежей? - PullRequest
Новая
       8

Более быстрый способ сравнения двух списков точечных кортежей?

3 голосов
/ 08 июня 2011

У меня есть два списка (которые могут иметь или не иметь одинаковую длину). В каждом списке есть ряд кортежей из двух точек (в основном значения 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) )]

Ответы [ 3 ]

2 голосов
/ 08 июня 2011

Если эти списки большие, я бы предложил найти более быстрый алгоритм ...

Я бы начал с сортировки обоих списков пар по сумме (x, y) в паре.(Поскольку две точки могут быть близки, только если их суммы близки.)

Для любой точки в первом списке это сильно ограничит диапазон, который необходимо искать во втором списке.Отслеживайте «скользящее окно» во втором списке, соответствующее элементам, чьи суммы находятся в пределах 2*tolerance от суммы текущего элемента первого списка.(На самом деле, вам нужно только отслеживать начало скользящего окна ...)

Предполагая, что tolerance достаточно мало, это должно преобразовать вашу операцию O (n ^ 2) в O (n logп).

2 голосов
/ 08 июня 2011

Здесь 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
1 голос
/ 08 июня 2011

С пониманием списка: 

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