階乗ループの回数を減らす方法を教えて下さい。

Question

前提・質問

複雑ネットワークの無向辺グラフで、ノードの位置が100m以内の時、ノードとノードをエッジ（枝）で繋げるプログラムを書いています。ノードの数は7000個あり、それぞれに座標(x,y)が与えられています。
リストの中身はnode_list((id,x,y))で、ループを回して、x,yの差が100m以内のノード同士を探しています。
1つのノードに対して、すべてのノードでx,yの差を求めているため、ループの回数が7000の階乗回回しています。
ループの回数を減らすためにはどうしたらいいでしょうか？

発生している問題

7000！回ループなので、処理が重くて計算ができないです。

該当のソースコード

for i in range(len(node_list)):
for j in range(len(node_list) - i):

x_difference = node_list[i][1] - node_list[j][1]
y_difference = node_list[i][2] - node_list[j][2]

if abs(x_difference) < 100 and abs(y_difference) < 100:

if node_list[i][0] != node_list[j][0]:

if (node_list[i][0], node_list[j][0]) not in edge_list and (
node_list[j][0], node_list[i][0]) not in edge_list:

node_edge_list.append((node_list[i][0], node_list[j][0]))
edge_list.append((node_list[i][0], node_list[j][0]))
edge_list.append((node_list[j][0], node_list[i][0]))

python3

Comments

[yambejp]

pythonであればタグ付けしてください

Answer 1

こんばんわ。

付け足しになりますが、2点間の距離を求めるには以下のとおりにします。

点P(x1,y1)と点Q(x2,y2)との距離Dを求める式について

D = sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

Comments

[Dobutori]

ありがとうございます。解決することができました。

Answer 2

インデントが崩れているのでよく分かりませんが、forループが二重になっているだけなので、7000 * 7000 / 2 → 約25M回の処理のように見えます。
遅い原因が本当にループ回数なのか確認した方が良いと思います。

たとえば、貼ってもらったコードでは node_edge_list や edge_list にappendしているのでリストを使用していると思います。これだと、リストのサイズが大きくなると in で確認するのに時間がかかるようになります。これを以下のようにセット型にするだけで速度が改善されたりしませんか?

また、node_listの内容によっては node_edge_list や edge_list がメモリを大量に消費するので、～16GBのマシンだとメモリが不足するかもしれません。

マシンにもよりますが、以下のコードで私の環境だと1分以内に処理が完了します。

from random import randint

size = 7000
node_list = [[i, randint(0, 100), randint(0, 100)] for i in range(size)]
node_edge_list = set()
edge_list = set()

for i in range(len(node_list)):
    print(i)
    for j in range(len(node_list) - i):
        x_difference = node_list[i][1] - node_list[j][1]
        y_difference = node_list[i][2] - node_list[j][2]

        if abs(x_difference) < 100 and abs(y_difference) < 100:
            if node_list[i][0] != node_list[j][0]:
                if (node_list[i][0], node_list[j][0]) not in edge_list and (
                    node_list[j][0], node_list[i][0]) not in edge_list:
                    node_edge_list.add((node_list[i][0], node_list[j][0]))
                    edge_list.add((node_list[i][0], node_list[j][0]))
                    edge_list.add((node_list[j][0], node_list[i][0]))

Comments

[Dobutori]

プログラムの処理時間が11秒程度まで減らすことができました！ありがとうございました！

Answer 3

今のコードでも階乗回のループにはなってません。
データの内容にもよりますが、現状で一番時間がかかってるコードはおそらく

if (node_list[i][0], node_list[j][0]) not in edge_list and (
node_list[j][0], node_list[i][0]) not in edge_list: 

同じ辺を追加しないようにチェックしてるここです。edge_listをsetにすれば、計算できないというレベルの時間はかからないでしょう。

Comments

[Dobutori]

setにすることで大幅に時間を短縮することができました！ありがとうございます！