Оптимизация симметричного теста - PullRequest
Новая
       6

Оптимизация симметричного теста

0 голосов
/ 20 июня 2019

у меня есть n предметов. Для каждой пары я должен выполнить тест (True / False). Тест является симметричным: test (a, b) = test (b, a). Я ищу самое быстрое решение для запуска этих тестов.

Каждый элемент имеет идентификатор и свойство. В данном конкретном случае свойство имеет форму многоугольника, и я ищу другие ближайшие многоугольники. Этот тест является симметричным: если A касается B, то B касается A. Двойное тестирование является излишним. Поэтому я написал этот код для проверки только n (n-1) / 2 раза: 

from collections import defaultdict
dict_neigh = defaultdict(list)

# initially my data is in a dataframe, but I though an array would be faster(?) 

# the property of the item:
data=df_gps.coordinates.values

# the index of the item:
ind=df_gps.index.values

end=len(data)
for x in range(0,end-1):
    for y in range(x +1,end):
        # The symmetric test:
        if Polygon(data[x]).touches(Polygon(data[y])):
            # Store the result in a dic
            dict_neigh[ind[x]].append(ind[y])
            dict_neigh[ind[y]].append(ind[x])

Я хотел бы знать, видит ли кто-нибудь способ улучшить скорость этого (своего рода) теста.

...