파이썬에서 networkx 노드를 사용하는 N 포인트 파이썬 간의 빠른 3d 거리

Question

나는 이것을 하루 종일 알아 내려고 노력해 왔지만 나는 제대로 이해하지 못했습니다.

현재 사이트 투콜 (site-to-site) 퍼콜 레이션을 사용하여 식민지 시뮬레이션을 실행 중입니다. 나는 그것을 큰 숫자 ~ 10^6까지 확장하려고 노력하고 있는데, 거리를 계산하기위한 종래의 numpy 방법은 2 차적으로 비늘을 사용하므로 프로그램이 하루 이상 실행됩니다. 나는 이것이 정말로 더 빠르기를 정말로 원한다. 솔루션을 찾았지만 시뮬레이션에 사용되는 사용자 정의 클래스를 가지고 있기 때문에이를 해결하는 데 도움이되는 것을 찾을 수 없습니다.

각 노드의 거리를 다른 모든 노드와 비교하고 각 노드가 서로 D_max 내에 있으면 가장자리가 그려져 두 노드 사이의 이동이 허용됩니다.

`density = 0.14 #Stellar density per cubic parsec 
L = 100 
Patches = int(0.056*density*L**3+15) 
Distance = 5 

nearand = np.genfromtxt('/Users/Skippy/nearand.csv', delimiter = ',',usecols=np.arange(0, 3)).astype('float32') # a csv of 3d cartesian co-ordinates 

G = nx.Graph() 

xcoord = nearand[:,0] 
ycoord = nearand[:,1] 
zcoord = nearand[:,2] 

class patch: 
    def __init__(self,status=0,pos=(0,0,0)): 
     self.status = status 
     self.pos = pos 
    def __str__(self): 
     return(str(self.status)) 

for i in xrange(Patches): 

    Stat = 1 if np.random.uniform() < P_init else 0 # a parameter used in the algorithm later 
    Pos = (xcoord[i], ycoord[i], zcoord[i]) 

    G.add_node(patch(Stat,Pos)) 

for p1 in G.nodes(): 
    for p2 in G.nodes(): 
     Dist = np.sqrt((p1.pos[2] - p2.pos[2])**2 + (p1.pos[1]-p2.pos[1])**2+(p1.pos[0]-p2.pos[0])**2) 

     if Dist <= Distance: 
      G.add_edge(p1,p2)` 

이 후 알고리즘은 실행되지만 더 큰 실행은 거리 계산에서 유지되므로 거리 최적화 만 필요합니다. 아무도 이것으로 나를 도울 수 없습니까? 그것은 다른 문제와 비슷하게 생겼지 만, 기존의 numpy 계산이 거리를 계산하는 방식으로 이러한 가장자리를 그릴 수 있어야합니다.

Answer 1

내가 이해 한 것에서 몇 가지 언급이 있습니다. "엡실론 - 이웃 그래프"를 작성하여 모든 노드와 다른 노드 사이의 거리를 계산 한 다음 거리가 임계 값 ε 미만이면 필터링합니다.

그래프가 움직이지 않는다는 것을 알기 때문에 (N × (N-1))/2 계산 만하면됩니다. 그것은 여전히 ​​2 차 O (n^2)이지만, 내부 루프가 항상 외부 루프 인덱스 + 1에서 시작하도록 가장자리를 만드는 루프를 변경해야합니다. 계산을 절반으로 줄입니다.

이제 실제 규모를 원한다면 표준 L2 표준 (유클리드 거리)을 사용하기 때문에 근사 이웃 법을 사용할 수 있다면 숙고해야합니다.

이렇게하려면 NMSLib 또는 Annoy을 살펴 보시기 바랍니다. 그들은 파이썬 바인딩을 가지고 있지만 속도면에서 C++로 구현됩니다.

희망이 있습니다.