python - 为什么计算优先依恋成本很高？

Question

我有一个无向图，有 1034 个顶点和 53498 条边。我正在计算顶点的优先附着指数。两个顶点之间的优先依附相似度定义为第一个顶点的度乘以第二个顶点的度。我注意到我的计算速度很慢。计算上述图表需要 2.7 分钟。我不确定是我的算法慢了还是其他什么地方出了问题。如果有人可以稍微查看一下我的代码，我将不胜感激。

编辑:我刚刚意识到 S 是一个 1034_by_1034 矩阵。查看嵌套的 for 循环，它似乎是一个 O(n^2) 算法!我想这就是为什么它很慢。你不同意吗？

def pa(graph):
    """
        Calculates Preferential Attachment index.

        Returns S the similarity matrix.
    """
    A = gts.adjacency(graph)
    S = np.zeros(A.shape)
    for i in xrange(S.shape[0]):
        for j in xrange(S.shape[0]):
            i_degree = graph.vertex(i).out_degree()
            j_degree = graph.vertex(j).out_degree()
            factor = i_degree * j_degree
            S[i,j] = factor
    return S

Answer 1

据我所知，这些是我可以建议的加速:

第 0 次加速:i_degree 不依赖于 j，因此将其提高一级

def pa(graph):
    A = gts.adjacency(graph)
    S = np.zeros(A.shape)
    for i in xrange(S.shape[0]):
        i_degree = graph.vertex(i).out_degree() # easy to see that this can be put here instead, since it does not depend on j 
        for j in xrange(S.shape[0]):
            j_degree = graph.vertex(j).out_degree()
            factor = i_degree * j_degree
            S[i,j] = factor
    return S

第一次加速:只调用 out_degree() N 次，而不是 2N^2 次。

def pa2(graph):
    A = gts.adjacency(graph)
    i_degree = numpy.zeros(A.shape[0])
    for i in xrange(A.shape[0]):
        i_degree[i] = graph.vertex(i).out_degree()
    S = np.zeros(A.shape)
    for i in xrange(S.shape[0]):
        for j in xrange(S.shape[0]):
            S[i,j] = i_degree[i]*i_degree[j]
    return S

第二次加速:numpy 代替 python for-loop

def pa3(graph):
    A = gts.adjacency(graph)
    i_degree = numpy.zeros(A.shape[0])
    for i in xrange(A.shape[0]):
        i_degree[i] = graph.vertex(i).out_degree()
    S = i_degree[:,None]*i_degree[None,:]
    return S

这会滥用问题的对称性。

注意:[None,:] 与使用 [numpy.newaxis,:] 的作用相同。如果你想保留你的代码，你也可以在 out_degree() 方法上使用 @memoize 装饰器，但最好只在递归的东西上使用它，这不是其中一种情况。