问题:
我已经对我的 Python 程序进行了分析，并且有一个函数会减慢一切。它大量使用 Python 字典，所以我可能没有以最好的方式使用它们。如果我不能让它运行得更快，我将不得不用 C++ 重新编写它，那么有没有人可以帮助我用 Python 优化它？
我希望我已经给出了正确的解释，并且你可以理解我的代码!在此先感谢您的帮助。
我的代码:
这是有问题的函数，使用 line_profiler and kernprof 进行分析。我正在运行 Python 2.7
我对诸如第 363、389 和 405 行之类的事情感到特别困惑，其中比较两个变量的 if 语句似乎花费了过多的时间。
我已经考虑过使用 NumPy(因为它使用稀疏矩阵)，但我认为它不合适，因为:(1)我没有使用整数索引我的矩阵(我使用的是对象实例)； (2) 我没有在矩阵中存储简单的数据类型(我存储的是浮点数和对象实例的元组)。
但我愿意被 NumPy 说服。
如果有人知道 NumPy 的稀疏矩阵性能与 Python 的哈希表，我会很感兴趣。
抱歉，我没有给出一个您可以运行的简单示例，但此功能被捆绑在一个更大的项目中，我无法弄清楚如何设置一个简单的示例来测试它，而不给您一半的代码根据!
Timer unit: 3.33366e-10 s
File: routing_distances.py
Function: propagate_distances_node at line 328
Total time: 807.234 s
Line # Hits Time Per Hit % Time Line Contents
328 @profile
329 def propagate_distances_node(self, node_a, cutoff_distance=200):
330
331 # a makes sure its immediate neighbours are correctly in its distance table
332 # because its immediate neighbours may change as binds/folding change
333 737753 3733642341 5060.8 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
334 512120 2077788924 4057.2 0.1 use_neighbour_link = False
335
336 512120 2465798454 4814.9 0.1 if(node_b not in self.node_distances[node_a]): # a doesn't know distance to b
337 15857 66075687 4167.0 0.0 use_neighbour_link = True
338 else: # a does know distance to b
339 496263 2390534838 4817.1 0.1 (node_distance_b_a, next_node) = self.node_distances[node_a][node_b]
340 496263 2058112872 4147.2 0.1 if(node_distance_b_a > neighbour_distance_b_a): # neighbour distance is shorter
341 81 331794 4096.2 0.0 use_neighbour_link = True
342 496182 2665644192 5372.3 0.1 elif((None == next_node) and (float('+inf') == neighbour_distance_b_a)): # direct route that has just broken
343 75 313623 4181.6 0.0 use_neighbour_link = True
344
345 512120 1992514932 3890.7 0.1 if(use_neighbour_link):
346 16013 78149007 4880.3 0.0 self.node_distances[node_a][node_b] = (neighbour_distance_b_a, None)
347 16013 83489949 5213.9 0.0 self.nodes_changed.add(node_a)
348
349 ## Affinity distances update
350 16013 86020794 5371.9 0.0 if((node_a.type == Atom.BINDING_SITE) and (node_b.type == Atom.BINDING_SITE)):
351 164 3950487 24088.3 0.0 self.add_affinityDistance(node_a, node_b, self.chemistry.affinity(node_a.data, node_b.data))
352
353 # a sends its table to all its immediate neighbours
354 737753 3549685140 4811.5 0.1 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
355 512120 2129343210 4157.9 0.1 node_b_changed = False
356
357 # b integrates a's distance table with its own
358 512120 2203821081 4303.3 0.1 node_b_chemical = node_b.chemical
359 512120 2409257898 4704.5 0.1 node_b_distances = node_b_chemical.node_distances[node_b]
360
361 # For all b's routes (to c) that go to a first, update their distances
362 41756882 183992040153 4406.3 7.6 for node_c, (distance_b_c, node_after_b) in node_b_distances.iteritems(): # Think it's ok to modify items while iterating over them (just not insert/delete) (seems to work ok)
363 41244762 172425596985 4180.5 7.1 if(node_after_b == node_a):
364
365 16673654 64255631616 3853.7 2.7 try:
366 16673654 88781802534 5324.7 3.7 distance_b_a_c = neighbour_distance_b_a + self.node_distances[node_a][node_c][0]
367 187083 929898684 4970.5 0.0 except KeyError:
368 187083 1056787479 5648.8 0.0 distance_b_a_c = float('+inf')
369
370 16673654 69374705256 4160.7 2.9 if(distance_b_c != distance_b_a_c): # a's distance to c has changed
371 710083 3136751361 4417.4 0.1 node_b_distances[node_c] = (distance_b_a_c, node_a)
372 710083 2848845276 4012.0 0.1 node_b_changed = True
373
374 ## Affinity distances update
375 710083 3484577241 4907.3 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
376 99592 1591029009 15975.5 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
377
378 # If distance got longer, then ask b's neighbours to update
379 ## TODO: document this!
380 16673654 70998570837 4258.1 2.9 if(distance_b_a_c > distance_b_c):
381 #for (node, neighbour_distance) in node_b_chemical.neighbours[node_b].iteritems():
382 1702852 7413182064 4353.4 0.3 for node in node_b_chemical.neighbours[node_b]:
383 1204903 5912053272 4906.7 0.2 node.chemical.nodes_changed.add(node)
384
385 # Look for routes from a to c that are quicker than ones b knows already
386 42076729 184216680432 4378.1 7.6 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
387
388 41564609 171150289218 4117.7 7.1 node_b_update = False
389 41564609 172040284089 4139.1 7.1 if(node_c == node_b): # a-b path
390 512120 2040112548 3983.7 0.1 pass
391 41052489 169406668962 4126.6 7.0 elif(node_after_a == node_b): # a-b-a-b path
392 16251407 63918804600 3933.1 2.6 pass
393 24801082 101577038778 4095.7 4.2 elif(node_c in node_b_distances): # b can already get to c
394 24004846 103404357180 4307.6 4.3 (distance_b_c, node_after_b) = node_b_distances[node_c]
395 24004846 102717271836 4279.0 4.2 if(node_after_b != node_a): # b doesn't already go to a first
396 7518275 31858204500 4237.4 1.3 distance_b_a_c = neighbour_distance_b_a + distance_a_c
397 7518275 33470022717 4451.8 1.4 if(distance_b_a_c < distance_b_c): # quicker to go via a
398 225357 956440656 4244.1 0.0 node_b_update = True
399 else: # b can't already get to c
400 796236 3415455549 4289.5 0.1 distance_b_a_c = neighbour_distance_b_a + distance_a_c
401 796236 3412145520 4285.3 0.1 if(distance_b_a_c < cutoff_distance): # not too for to go
402 593352 2514800052 4238.3 0.1 node_b_update = True
403
404 ## Affinity distances update
405 41564609 164585250189 3959.7 6.8 if node_b_update:
406 818709 3933555120 4804.6 0.2 node_b_distances[node_c] = (distance_b_a_c, node_a)
407 818709 4151464335 5070.7 0.2 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
408 104293 1704446289 16342.9 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
409 818709 3557529531 4345.3 0.1 node_b_changed = True
410
411 # If any of node b's rows have exceeded the cutoff distance, then remove them
412 42350234 197075504439 4653.5 8.1 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can't use iteritems() here, as deleting from the dictionary
413 41838114 180297579789 4309.4 7.4 if(distance_b_c > cutoff_distance):
414 206296 894881754 4337.9 0.0 del node_b_distances[node_c]
415 206296 860508045 4171.2 0.0 node_b_changed = True
416
417 ## Affinity distances update
418 206296 4698692217 22776.5 0.2 node_b_chemical.del_affinityDistance(node_b, node_c)
419
420 # If we've modified node_b's distance table, tell its chemical to update accordingly
421 512120 2130466347 4160.1 0.1 if(node_b_changed):
422 217858 1201064454 5513.1 0.0 node_b_chemical.nodes_changed.add(node_b)
423
424 # Remove any neighbours that have infinite distance (have just unbound)
425 ## TODO: not sure what difference it makes to do this here rather than above (after updating self.node_distances for neighbours)
426 ## but doing it above seems to break the walker's movement
427 737753 3830386968 5192.0 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].items(): # Can't use iteritems() here, as deleting from the dictionary
428 512120 2249770068 4393.1 0.1 if(neighbour_distance_b_a > cutoff_distance):
429 150 747747 4985.0 0.0 del self.neighbours[node_a][node_b]
430
431 ## Affinity distances update
432 150 2148813 14325.4 0.0 self.del_affinityDistance(node_a, node_b)
我的代码解释:
此函数维护一个稀疏距离矩阵，表示(非常大的)网络中节点之间的网络距离(最短路径上的边权重之和)。使用完整的表并使用 Floyd-Warshall algorithm 会非常慢。 (我首先尝试了这个，它比当前版本慢了几个数量级。)所以我的代码使用一个稀疏矩阵来表示全距离矩阵的阈值版本(任何距离大于 200 个单位的路径都被忽略)。网络拓扑随时间变化，因此该距离矩阵需要随时间更新。为此，我使用了 distance-vector routing protocol 的粗略实现:网络中的每个节点都知道彼此之间的距离以及路径上的下一个节点。当拓扑发生变化时，与此变化相关的节点会相应地更新它们的距离表，并告诉它们的直接邻居。信息通过节点通过网络传播，将它们的距离表发送给它们的邻居，后者更新它们的距离表并将它们传播给它们的邻居。
有一个表示距离矩阵的对象:
self.node_distances 。这是一个将节点映射到路由表的字典。节点是我定义的对象。路由表是一个字典，将节点映射到 (distance, next_node) 的元组。距离是node_a到node_b的图距离，next_node是node_a的邻居，你必须先去，在node_a和node_b之间的路径上。 None 的 next_node 表示 node_a 和 node_b 是图邻居。例如，距离矩阵的样本可以是:self.node_distances = { node_1 : { node_2 : (2.0, None),
node_3 : (5.7, node_2),
node_5 : (22.9, node_2) },
node_2 : { node_1 : (2.0, None),
node_3 : (3.7, None),
node_5 : (20.9, node_7)},
...etc...
由于拓扑变化，相距很远(或根本没有连接)的两个节点可以变得很近。当这种情况发生时，条目被添加到这个矩阵中。由于阈值，两个节点可能会变得太远而无法关心。发生这种情况时，将从该矩阵中删除条目。
self.neighbours 矩阵类似于 self.node_distances ，但包含有关网络中直接链接(边)的信息。通过化学 react ，self.neighbours 不断被外部修改为该功能。这就是网络拓扑变化的来源。我遇到问题的实际功能:
propagate_distances_node() 执行 distance-vector routing protocol 的一步。给定一个节点 node_a ，该函数确保 node_a 的邻居在距离矩阵中正确(拓扑变化)。然后，该函数将 node_a 的路由表发送到网络中 node_a 的所有直接邻居。它将 node_a 的路由表与每个邻居自己的路由表集成在一起。在我程序的其余部分，
propagate_distances_node() 函数被重复调用，直到距离矩阵收敛。维护了一组 self.nodes_changed ，其中包含自上次更新以来已更改其路由表的节点。在我的算法的每次迭代中，都会选择这些节点的随机子集，并对它们调用 propagate_distances_node()。这意味着节点异步和随机地传播它们的路由表。当集合 self.nodes_changed 为空时，该算法收敛于真实距离矩阵。“亲和距离”部分(
add_affinityDistance 和 del_affinityDistance )是距离矩阵的(小)子矩阵的缓存，由程序的不同部分使用。我这样做的原因是我正在模拟参与 react 的化学物质的计算类似物，作为我博士学位的一部分。 “化学”是“原子”(图中的节点)的图。结合在一起的两种化学物质被模拟为它们的两个图被新边连接起来。发生化学 react (通过与此处无关的复杂过程)，从而改变图的拓扑结构。但是 react 中发生的事情取决于构成化学物质的不同原子相距多远。所以对于模拟中的每个原子，我想知道它与哪些其他原子接近。稀疏的阈值距离矩阵是存储此信息的最有效方法。由于网络的拓扑结构随着 react 的发生而变化，我需要更新矩阵。 distance-vector routing protocol 是我能想到的最快的方法。我不需要更复杂的路由协议(protocol)，因为在我的特定应用程序中不会发生诸如路由循环之类的事情(因为我的化学品的结构方式)。我随机进行的原因是，我可以将化学 react 过程与距离传播交织在一起，并模拟化学 react 随着时间的推移逐渐改变形状(而不是立即改变形状)。
这个函数中的
self 是一个代表化学物质的对象。 self.node_distances.keys() 中的节点是构成化学物质的原子。 self.node_distances[node_x].keys() 中的节点是来自化学物质的节点，并且可能来自与化学物质结合(并与之 react )的任何化学物质的节点。更新:
我尝试用
node_x == node_y(根据@Sven Marnach 的评论)替换 node_x is node_y 的每个实例，但它减慢了速度! (我没想到!)我原来的配置文件需要 807.234s 才能运行，但是通过这个修改它增加到 895.895s。对不起，我做的分析错误!我正在使用 line_by_line，它(在我的代码中)有太多的差异(大约 90 秒的差异完全在噪音中)。正确分析时，
is 绝对快于 == 。使用 CProfile ，我的代码 == 花费了 34.394s，但使用 is ，它花费了 33.535s(我可以确认这是噪音)。更新:
现有图书馆
我不确定是否会有一个现有的库可以做我想做的事，因为我的要求不寻常:
我需要计算加权无向图中所有节点对之间的最短路径长度。我只关心低于阈值的路径长度。计算路径长度后，我对网络拓扑进行了小的更改(添加或删除边)，然后我想重新计算路径长度。与阈值相比，我的图很大(从给定节点来看，大部分图都比阈值更远)，因此拓扑变化不会影响大多数最短路径长度。这就是我使用路由算法的原因:因为它通过图结构传播拓扑变化信息，所以当它超过阈值时我可以停止传播它。即，我不需要每次都重新计算所有路径。我可以使用之前的路径信息(来自拓扑变化之前)来加速计算。这就是为什么我认为我的算法将比最短路径算法的任何库实现更快。
我从未见过在通过物理网络实际路由数据包之外使用的路由算法(但如果有人有，那么我会感兴趣)。
NetworkX 是由@Thomas K 建议的。
它有 lots of algorithms 用于计算最短路径。
它有一个算法来计算具有截止值的 all-pairs shortest path lengths(这是我想要的)，但它只适用于未加权的图(我的是加权的)。
不幸的是，它的 algorithms for weighted graphs 不允许使用截止(这可能会使我的图表变慢)。而且它的算法似乎都不支持在非常相似的网络(即路由内容)上使用预先计算的路径。
igraph 是我所知道的另一个图形库，但是查看 its documentation ，我找不到关于最短路径的任何信息。但我可能错过了——它的文档似乎不是很全面。
感谢@9000 的评论，NumPy 可能是可能的。如果我为节点的每个实例分配一个唯一的整数，我可以将我的稀疏矩阵存储在 NumPy 数组中。然后我可以用整数而不是节点实例来索引一个 NumPy 数组。我还需要两个 NumPy 数组:一个用于距离，另一个用于“next_node”引用。这可能比使用 Python 字典更快(我还不知道)。
有谁知道任何其他可能有用的库？
更新: 内存使用
我正在运行 Windows (XP)，所以这里有一些关于内存使用的信息，来自 Process Explorer 。 CPU 使用率为 50%，因为我有一台双核机器。
我的程序没有用完 RAM 并开始进行交换。您可以从数字和没有任何事件的 IO 图中看出这一点。 IO 图形上的尖峰是程序打印到屏幕上以说明其运行情况的地方。
但是，随着时间的推移，我的程序确实会继续使用越来越多的 RAM，这可能不是一件好事(但它总体上并没有使用太多 RAM，这就是为什么我直到现在才注意到增加的原因)。
并且 IO 图上尖峰之间的距离随着时间的推移而增加。这很糟糕 - 我的程序每 100,000 次迭代就会打印到屏幕上，这意味着随着时间的推移，每次迭代需要更长的时间来执行......我已经通过长时间运行我的程序并测量之间的时间来确认这一点打印语句(程序每 10,000 次迭代之间的时间)。这应该是恒定的，但正如您从图中看到的那样，它呈线性增加……所以那里有些东西。 (此图上的噪音是因为我的程序使用了大量随机数，因此每次迭代的时间各不相同。)
在我的程序运行了很长时间后，内存使用情况如下所示(因此它肯定不会耗尽 RAM):
最佳答案
node_after_b == node_a 将尝试调用 node_after_b.__eq__(node_a) :
>>> class B(object):
... def __eq__(self, other):
... print "B.__eq__()"
... return False
...
>>> class A(object):
... def __eq__(self, other):
... print "A.__eq__()"
... return False
...
>>> a = A()
>>> b = B()
>>> a == b
A.__eq__()
False
>>> b == a
B.__eq__()
False
>>>
在求助于 C 之前，尝试使用优化版本覆盖
Node.__eq__()。更新
我做了这个小实验(python 2.6.6):
#!/usr/bin/env python
# test.py
class A(object):
def __init__(self, id):
self.id = id
class B(A):
def __eq__(self, other):
return self.id == other.id
@profile
def main():
list_a = []
list_b = []
for x in range(100000):
list_a.append(A(x))
list_b.append(B(x))
ob_a = A(1)
ob_b = B(1)
for ob in list_a:
if ob == ob_a:
x = True
if ob is ob_a:
x = True
if ob.id == ob_a.id:
x = True
if ob.id == 1:
x = True
for ob in list_b:
if ob == ob_b:
x = True
if ob is ob_b:
x = True
if ob.id == ob_b.id:
x = True
if ob.id == 1:
x = True
if __name__ == '__main__':
main()
结果:
Timer unit: 1e-06 s
File: test.py Function: main at line 10 Total time: 5.52964 s
Line # Hits Time Per Hit % Time Line Contents
==============================================================
10 @profile
11 def main():
12 1 5 5.0 0.0 list_a = []
13 1 3 3.0 0.0 list_b = []
14 100001 360677 3.6 6.5 for x in range(100000):
15 100000 763593 7.6 13.8 list_a.append(A(x))
16 100000 924822 9.2 16.7 list_b.append(B(x))
17
18 1 14 14.0 0.0 ob_a = A(1)
19 1 5 5.0 0.0 ob_b = B(1)
20 100001 500454 5.0 9.1 for ob in list_a:
21 100000 267252 2.7 4.8 if ob == ob_a:
22 x = True
23 100000 259075 2.6 4.7 if ob is ob_a:
24 x = True
25 100000 539683 5.4 9.8 if ob.id == ob_a.id:
26 1 3 3.0 0.0 x = True
27 100000 271519 2.7 4.9 if ob.id == 1:
28 1 3 3.0 0.0 x = True
29 100001 296736 3.0 5.4 for ob in list_b:
30 100000 472204 4.7 8.5 if ob == ob_b:
31 1 4 4.0 0.0 x = True
32 100000 283165 2.8 5.1 if ob is ob_b:
33 x = True
34 100000 298839 3.0 5.4 if ob.id == ob_b.id:
35 1 3 3.0 0.0 x = True
36 100000 291576 2.9 5.3 if ob.id == 1:
37 1 3 3.0 0.0 x = True
我很惊讶:
然后我尝试了更复杂的对象，结果与第一个实验一致。
你换了很多吗？如果您的数据集太大以至于无法容纳可用的 RAM，我想您可能会遇到某种与虚拟内存获取相关的 I/O 争用。
你在运行 Linux 吗？如果是这样，您可以在运行程序时发布机器的 vmstat 吗？向我们发送类似以下内容的输出:
vmstat 10 100
祝你好运!
更新(来自 OP 的评论)
我建议使用 sys.setcheckinterval 并启用/禁用 GC。基本原理是，对于这种特殊情况(大量实例)，默认的 GC 引用计数检查有些昂贵，并且其默认间隔过于频繁。
Yes, I had previously played with sys.setcheckinterval. I changed it to 1000 (from its default of 100), but it didn't do any measurable difference. Disabling Garbage Collection has helped - thanks. This has been the biggest speedup so far - saving about 20% (171 minutes for the whole run, down to 135 minutes) - I'm not sure what the error bars are on that, but it must be a statistically significant increase. – Adam Nellis Feb 9 at 15:10
我猜:
I think the Python GC is based on reference count. From time to time it will check the reference count for every instance; since you are traversing these huge in-memory structures, in your particular case the GC default frequency (1000 cycles?) is away too often - a huge waste. – Yours Truly Feb 10 at 2:06
关于python - 优化Python字典访问代码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4900747/