N点間の3D距離の高速pythonでnetworkxノードを使用するpython

Question

私はこれを一日中考えようとしています。

私は現在サイトツーサイトパーコレーションを使用してコロニーシミュレーションを実行しています。私は大きな数にスケールアップしようとしています〜10^6しかし、距離を計算するための従来のnumpyの方法では、私はプログラムを1日以上実行するような大規模な実行のために二次的にスケールを使用しています。私は本当にこれがより速くしたい。私は解決策を探しましたが、私はシミュレーションで使用されるカスタムクラスを持っているので、これで私を助けるものは何も見つかりません。

私は各ノードと他のすべてのノードとの距離を求め、ノードが互いにD_max内にある場合、エッジが描画され、2つのノード間の移動が可能になります。

`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をご覧ください。彼らはPythonバインディングを持っていますが、スピードのためにC++で実装されています。

希望します。