优化 python 脚本以更快地生成输出（变量分配）

Question

我正在使用 python 进行优化。我使用 Networkx 库和 1100 个节点制作了一个图表。 python 脚本包括以下几行。

# Compute key parameters of MIP model formulation
from itertools import product
num_facilities = len(facilities)
print("The num_facility = ", num_facilities)
num_customers = len(customers)
print("The num_customers = ", num_customers)
cartesian_prod = list(product(range(num_customers), range(num_facilities))) 

#Output
The num_facility =  1100
The num_customers =  1100

下一步生成一些随机数如下：

import random
random.seed(7) 
number_of_vpns = random.sample(range(0, 1200), num_facilities)

我使用以下函数计算图中节点之间的距离。

def compute_distance(source_number,dest_number):
    path = (nx.shortest_path(g,source=source_number,target= dest_number, weight='weight'))
    path_length = path_weight(g, path, weight="weight")
    return path_length

最后，我将变量“shipping_cost”定义为：

%%time
shipping_cost = {(c,f): number_of_vpns[c]*compute_distance(c,f) for c, f in cartesian_prod}

以上代码的每一行都以很短的方式（毫秒）执行。但是，变量“shipping_cost”的赋值在 7 小时后仍未完成。该变量逻辑上包含 1210000 个值。

就运行时间而言是否正常？
有什么方法可以减少 shipping_cost 赋值的执行时间吗？

Answer 1

根据@Ram 的评论：

cartesian_prod 包含 1210000 个值。该代码正在调用 compute_distance()，后者又会为 networkx 库中的所有 1210000 个值调用 shortest_path() 和 path_length()。这就是计算 shipping_cost 需要花费大量时间的原因。

我更改了代码如下（添加path_lengths代替compute_distance并修改了shipping_cost）：

import networkx as nx
path_lengths = dict(nx.all_pairs_dijkstra_path_length(g, weight='weight'))

shipping_cost = {(c,f): number_of_vpns[c]*path_lengths[c][f] for c, f in cartesian_prod}

这样，path_lengths对所有节点计算一次，时间复杂度集中在访问path_lengths.

的元素上

优化 python 脚本以更快地生成输出（变量分配）

Optimizing python script to produce output faster (Variable Assignment)

python

performance

time