python - 加速networkx中的随机最小生成树？

Question

这里有一些代码，其目标是使用贪婪和随机边缘权重构建随机生成树。它的运行速度比我希望的慢得多。有什么加快速度的技巧吗？

随机生成权重和最小生成树的采样都很慢...第一个对我来说特别奇怪，因为只有 179400 条边和 np.random.uniform(0 ,1,179400) 执行速度非常快。

(这里慢是指以秒为单位。)

(我很高兴使用networkx以外的东西，但这并不可取。)

import numpy as np
import networkx as nx

graph = nx.grid_graph([300, 300])

for edge in graph.edges():
    graph.edges[edge]["weight"] = np.random.uniform(0, 1)

tree = nx.minimum_spanning_tree(graph)

Answer 1

如果在您的测试中批量生成随机数更快，那么就这样做。

rand = np.random.uniform(0, 1, graph.edges.size())
i = 0
for edge in graph.edges():
    graph.edges[edge]["weight"] = rand[i]
    i += 1