2

現時点では、私のアルゴリズムが完了するまでに 10 時間以上 (推定) かかります。それは今でも実行されているので、それがどれほどひどいものであるかをより正確に見積もることができます.

さまざまな長さのソートされた出現リストを持つ一連の人々Pがあるとします。ここで、 iはインデックス変数です。G P i ,P j = nとなるようなグラフGを作成したいと思います。ここで、nはP iとP jの間のエッジの重みであり、特定の静的範囲r内でそれらが同時に発生する回数を表します。

私の現在のアルゴリズムは無知で、次のように Python で実装されています(読みやすく、明確にするため) 。

print '>Generating combinations...',
pairs = combinations(people, 2)
print 'Done'

print 'Finding co-occurences'
radius = 5
for A, B in pairs:
    for oA in A.occurances:
        for oB in B.occurances:
            if oB in range(oA - radius, oA + radius):
                try:
                    network.edge[A.common_name][B.common_name]['weight'] += 1
                except:
                    network.add_edge(A.common_name, B.common_name, weight=1)

oBが現在の範囲を超えるoAと、ループが単純に次の に続くように、このアルゴリズムを変更することを検討しましたoA。

リストがソートされていることを考えると、これを達成するためのより良い方法はありますか?

4

2 に答える 2

1

oA上限を超えたらすぐに次へ進むというあなたの考えは良いものです。また、 と の範囲がA.occurances' radius' と比較して大きい場合、毎回B.occurancesの最初から開始しない方がはるかに効率的です。B.occurances

print '>Generating combinations...',
pairs = combinations(people, 2)
print 'Done'

print 'Finding co-occurences'
radius = 5
for A, B in pairs:
    i = 0
    b = B.occurances
    maxi = len(B.occurances) - 1
    for oA in A.occurances:
        lo = oA - radius
        hi = oA + radius
        while (b[i] > lo) and (i > 0):     # while we're above the low end of the range
            i = i - 1                      #   go towards the low end of the range
        while (b[i] < lo) and (i < maxi):  # while we're below the low end of the range
            i = i + 1                      #   go towards the low end of the range
        if b[i] >= lo:
            while (b[i] <= hi):            # while we're below the high end of the range
                try:                       #   increase edge weight
                    network.edge[A.common_name][B.common_name]['weight'] += 1
                except:
                    network.add_edge(A.common_name, B.common_name, weight=1)

                if i < maxi:               #   and go towards the high end of the range
                    i = i + 1
                else:
                    break

私はこれをデバッグしていないので、おそらくバグがあることに注意してください。しかし、うまくいけば、私がやろうとしていることの一般的なアイデアを得ることができます. もちろん、アイデアをさらに最適化することもできますが、これは力ずくの方法よりもはるかに効率的です。

于 2013-04-23T13:47:14.827 に答える
0

1 つのオプションは、範囲 (oA - 半径、oA + 半径) 内のすべての oB をすばやくクエリできるように、間隔ツリーに B.occurances を配置することです。

もう 1 つのオプションは、[0, 1)、[1, 2) など、バケット内の B.occurances にインデックスを付けることです。次に、インデックス付きのバケットを選択することで、範囲 (oA - 半径、oA + 半径) 内のすべての oB をすばやく見つけることができます。 (oA - 半径) から (oA + 半径) まで。バケットは概算であるため、最初と最後に選択したバケットのすべての oB を繰り返し検証する必要があります。

于 2013-04-23T13:40:00.540 に答える