Список кортежей: выбирайте только кортежи на основе общего элемента в первой или второй позиции.

Question

У меня огромный список кортежей :

ijs = [(0,1),(0,2),(0,3), (3,2)...]

Для заданного значения v я хочу получить только пары (i,j), которые имеют либо i=v или j=v (из всех возможных пар (i, j), хранящихся в ijs).

Например, для v=0 и с учетом ijs = [(0,1),(0,2),(0,3), (3,2)], тогда я должен вернуться only_current = [(0,1),(0,2),(0,3)]

---

Пример:

Пожалуйста, не обращайте внимания на первые 3 строки, в которых я построил список ijs с кортежами внутри.

import numpy as np

# IGNORE THIS PART UNTIL THE MAIN LOOP 
N= 1000
indices_upper_triangle = np.triu_indices(N, k = 1) # k=1 above diagonal
i,j = indices_upper_triangle
ijs = [(i,j) for i,j in zip(i,j)] # create (i,j) positions

# MAIN LOOP HERE 
# Main loop
all_neig_results = list()
for v in range(N): # for each point

    # from all possible (i,j) pairs, get only (i,j) pairs that have either i=v or j=v
    only_current = [item for item in ijs if v in item]

    all_neig_results.append(only_current)

Понимание списка в l oop очень медленное.

%timeit [item for item in ijs if v in item]
15.9 s ± 361 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Если я удалю проверочный аргумент if v in item:

%timeit [item for item in ijs]
1.28 s ± 90.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Как могу ли я оптимизировать [item for item in ijs if v in item]?

Answer 1

Здесь вы выполняете работу O (N ^ 2), потому что вы go по всему списку каждый раз во внутреннем l oop.

Вы должны выполнить предварительное вычисление один раз:

import collections
def precompute(pairs):
    d = collections.defaultdict(list)
    for ij in pairs:
        d[ij[0]].append(ij)
        d[ij[1]].append(ij)
    return d

d = precompute(ijs)

для выполнения работы во внутреннем l oop быстро:

for v in range(N):
    only_current = d[v]

таким образом вы выполняете только работу O (N).

Answer 2

Если ваша цель - найти ближайших соседей, я бы рекомендовал использовать KDTree , которое

можно использовать для быстрого поиска ближайших соседей любой точки.

и позволяет избежать l oop по всем парам точек / индексов.

См. Этот пример: Как найти набор точек в сетке x, y, используя KDTree.query_ball_tree

Относительно параметра leafsize: KDTrees «разбивают» пространство на разные области. Каждый лист соответствует региону. если leafsize = 1, он продолжает разбивать, пока каждая область не будет содержать только одну точку. Это означает, что построение дерева займет много времени, но поиск будет быстрым. Если на листьях больше точек, дерево будет мельче, поэтому строительство будет быстрее. Но запросы, вероятно, будут медленнее. бит «грубой силы» в do c относится к тому факту, что если у вас больше 1 точки в каждом регионе, вам нужно грубой силой определить ближайших соседей среди тех, кто находится в этом регионе.

leafsize=10 будет означать, что у листа 10 или меньше. Каждое разбиение таково, что дочерние узлы имеют (приблизительно) половину точек в родительском узле, поэтому точное количество точек в каждом листе будет переменным. есть и другие детали реализации, которые могут повлиять на это.