Ускорение создания ребер на основе парного взаимодействия узлов

Question

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

if (crit(i,j)) : 
    G.add_edge(i,j) 

Для этого я написал цикл

nnd = len(ndlist) 
for ind in range(nnd) : 
    ndi = ndlist[ ind ] 
    for jnd in range(nnd) : 
     if (jnd != ind) : # no self interaction 
      ndj = ndlist[ jnd ] 
      interaction = inrange(ndi, ndj, threshold) 
      if (interaction) : 
       G.add_edge(ind, jnd) 

ndlist представляет собой список, который содержит особенности узлов, один элемент для каждого узла, и эта информация используется для оценки взаимодействия между парами узлов. Узлы помечены с тем же номером индекса, что и в ndlist, и это используется. Это также является причиной циклизации целых чисел, поскольку к ним присоединяются (ind,jnd), а не (ndi,ndj).

Это оказывается очень медленным. Есть ли способ оптимизировать это?

Конечно, время выполнения будет зависеть от inrange, но может быть способом ускорения коды независимо от inrange (возможно подключить содержимое ndlist в качестве атрибутов узлов и итерации по-разному). Даже преобразование моего «очень медленного» кода в «просто медленный» код поможет.

Answer 1

answer by Joel показал один из способов сделать код более удобочитаемым, но при этом добавляя по одному краю за раз. И еще один способ добавления всех ребер за один раз, что, возможно, ускорило код. Но оказывается, что добавление всех ребер сразу не делает код быстрее (по крайней мере, в моем случае).

PS: Первая версия моего кода добавила один узел за раз (эта часть не показана выше, чтобы уменьшить беспорядок). Позже я изменил добавления всех узлов одновременно с

G.add_nodes_from(range(nnd)) 
nx.set_node_attributes(G, 'pos', posdict) 

и он сделал код гораздо быстрее.

Таким образом, у меня было некоторое ожидание о чем-то подобном, происходящем с краями. Но узким местом является оценка каждого кандидата, и я думаю, что этого мало. Мне, вероятно, придется пойти на скомпилированную оценочную функцию. Это стоит некоторой работы и, возможно, дальнейших вопросов SO.

Answer 2

Если я понимаю взаимосвязь между вашими переменными, следующее, по крайней мере, упростит чтение кода и уменьшит количество циклов для циклов, что, как правило, делает Python более эффективным. В принципе, как я понимаю (что может быть неисправным понимание) нажимаешь более зацикленной на C, а не чисто Python:

from intertools import permutations 
for ind, jnd in permutations(ndlist, 2): #all pairs without replacemnt 
    if inrange(ndi, ndj, threshold): 
     G.add_edge(ndi, ndj) 

Вы можете сделать это более кратким и избегать для цикла (который, вероятно, делает его более эффективный) с помощью list comprehension

from itertools import permutations 
new_edges = [ (ind,jnd) for ind, jnd in permutations(ndlist, 2) if inrange(ndi, ndj, threshold)] 
G.add_edges_from(new_edges) 

Создания new_edges генератора вместо списка будет сохранить память.

---

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