时间戳

首页 > 解决方案 > 创建环形图的两种方法

python - 创建环形图的两种方法

问题描述

假设我们有具有以下属性的图：

我有两个函数来绘制图表：

def ring_graph1(n, k):
   graph = nx.Graph()

   sources = np.arange(n)
   for i in range(1, k + 1):
       targets = np.roll(sources, i)
       graph.add_edges_from(zip(sources, targets))

   return graph

def ring_graph2(n, k):
   graph = nx.Graph()

   for i in range(n):
      sources = [i] * k
      targets = range(i + 1, i + k + 1)
      targets = [node % n for node in targets]
      graph.add_edges_from(zip(sources, targets))

   return graph

天真地我希望第一个工作得更快，因为它正在处理np.array并且一次分配更少的内存，并且因为k < n它分配的内存更少。

但测量表明：

times1 = []
times2 = []

for k in [2, 10, 50, 100, 200, 500]:
   t = %timeit -o ring_graph1(1000, k)
   times1.append(t.average)
   t = %timeit -o ring_graph2(1000, k)
   times2.append(t.average)

第二种方式的执行速度大约快 1.5 倍。为什么会这样？在此处输入图像描述

标签： pythonperformancenumpy

解决方案

物有所值，

def ring_graph3(n, k):
    edges = set()
    node_ids = list(range(n)) * 2

    for i in range(n):
        sources = [i] * k
        targets = node_ids[i + 1 : i + k + 1]
        edges.update(set(zip(sources, targets)))

    return edges

你不必做模数传递甚至更快（n = 1000，k = 500）：

ring_graph1: 2.64 ops/s (1 loops in 0.379351074)
ring_graph2: 5.29 ops/s (2 loops in 0.378035934)
ring_graph3: 5.75 ops/s (2 loops in 0.34760668299999997)

Numpy 魔法编辑！

经过一些工作，这会更快地返回相同的一组边对：

def ring_graph5(n, k):
    nxk = np.arange(0, n).repeat(k)
    src = nxk.reshape(n, k)
    dst = np.mod(np.tile(np.arange(0, k), n) + (nxk + 1), n).reshape((n, k))
    flat_pairs = np.dstack((src, dst)).flatten().tolist()
    return zip(flat_pairs[::2], flat_pairs[1::2])

ring_graph1: 2.92 ops/s (1 loops in 0.3422120950000007)
ring_graph2: 5.77 ops/s (2 loops in 0.34680103699999876)
ring_graph3: 6.93 ops/s (2 loops in 0.28863287499999934)
ring_graph4: 6.03 ops/s (2 loops in 0.3317746049999979)
ring_graph5: 19.43 ops/s (5 loops in 0.25736287700000204)

推荐阅读