2

目前，我的算法需要（估计）十多个小时才能完成。它现在仍在运行，这样我就可以更好地估计它有多糟糕。

假设我有一组人P，每个人都有一个不同长度的排序列表，其中i是一个索引变量。我想创建一个图G使得G P i ,P j = n，其中n是P i和P j之间的边权重，表示它们在某个静态范围r内共同出现的次数。

我当前的算法是无意识的，并在 Python 中实现（既可读又明确），如下所示：（为简洁起见，从GitHub 上的存储库中更改）

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超过 current 的范围时oA，循环就会继续到下一个oA。

考虑到列表已排序，有没有更好的方法来实现这一点？

4

2 回答 2

1

oA越过上限就继续下一个的想法是个好主意。此外，如果 和 的范围A.occurances与“半径”相比较大，那么每次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

一种选择是将 B.occurances 放在区间树中，以便您可以快速查询范围内的所有 oB（oA - 半径，oA + 半径）。

另一种选择是对桶中的 B.occurances 进行索引，例如 [0, 1), [1, 2) 等。然后您可以通过选择具有索引的桶来快速找到范围内的所有 oB (oA - 半径, oA + 半径) (oA - 半径) 到 (oA + 半径)。桶是近似的，因此您仍需要迭代地验证第一个和最后一个选定桶中的所有 oB。

于 2013-04-23T13:40:00.540 回答