为什么计算优先依附是昂贵的？

Question

我有一个无向图，有1034个顶点和53498条边。我在计算顶点的优先附着指数。将两个顶点之间的优先附着相似性定义为第一个顶点的度数乘以第二个顶点的度数。我注意到我的计算速度很慢。用了2.7分钟来计算上述图表的数值。我不确定是我的算法速度慢还是别的什么地方出错了。如果有人能看看我的代码，我会非常感激。在

编辑：我刚刚意识到S是一个1034×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

据我所知，以下是我可以建议的加速：

第零加速：i_度不取决于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

第一个加速：只调用N次，而不是2N^2。在

^{pr2}$

第二个加速：numpy代替python for循环

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修饰符，但最好只在递归的东西上使用它，而这不是其中之一。在