题:
我已经将我的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
。这是将节点映射到路由表的字典。节点是我定义的对象。路由表是将节点映射到(距离,next_node)元组的字典。距离是从node_a到node_b的图形距离,next_node是您必须首先在node_a和node_b之间的路径上到达的node_a的邻居。 next_node为None表示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
相似,但包含有关网络中直接链接(边缘)的信息。通过化学反应,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
)是距离矩阵的(小)子矩阵的缓存,程序的不同部分使用该缓存。
我这样做的原因是,我正在模拟参与反应的化学物质的计算类似物,这是我的博士学位的一部分。 “化学物质”是“原子”的图(图中的节点)。结合在一起的两种化学物质被模拟为它们的两个图通过新的边缘连接在一起。发生化学反应(通过与此处无关的复杂过程),从而改变了图形的拓扑。但是反应中发生的情况取决于组成化学物质的不同原子相距多远。因此,对于模拟中的每个原子,我想知道它靠近哪个其他原子。稀疏的阈值距离矩阵是存储此信息的最有效方法。由于网络的拓扑随着反应的发生而改变,因此我需要更新矩阵。 distance-vector routing protocol是我可以想到的最快方法。我不需要更复杂的路由协议,因为路由循环之类的事情在我的特定应用程序中不会发生(因为我的化学物质的结构)。我随机执行此操作的原因是,我可以将化学反应过程与距离扩展交织在一起,并模拟随着反应发生时间随时间逐渐变化的化学形状(而不是立即改变形状)。
此功能中的self
是代表化学物质的对象。 self.node_distances.keys()
中的节点是组成化学物质的原子。 self.node_distances[node_x].keys()
中的节点是该化学物质的节点,并且可能是该化学物质绑定(并与之反应)的任何化学物质的节点。
更新:
我尝试用node_x == node_y
替换node_x is node_y
的每个实例(根据@Sven Marnach的评论),但是这会使事情变慢! (我没想到!)
我的原始配置文件花了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
我很惊讶:
“点”访问(属性)似乎非常昂贵(第25行与第27行)。
至少对于简单对象来说,is和'=='之间没有太大区别
然后,我尝试使用更复杂的对象,结果与第一个实验一致。
你交换很多吗?如果您的数据集太大而无法容纳可用的RAM,我想您可能会遇到与虚拟内存获取有关的某种I / O争用。
您正在运行Linux吗?如果是这样,您可以在运行程序时发布计算机的vmstat吗?发送给我们类似以下内容的输出:
vmstat 10 100
祝好运!
更新(来自OP的评论)
我建议使用sys.setcheckinterval并启用/禁用GC。理由是对于这种特殊情况(大量实例),默认的GC引用计数检查有些昂贵,并且其默认间隔过于频繁。
是的,我以前玩过
sys.setcheckinterval。我将其更改为
1000(默认值是100),但是
没有任何可测量的差异。
禁用垃圾收集有
帮助-谢谢。这是
迄今为止最大的加速-节省约
20%(整个运行时间为171分钟,
最多135分钟)-我不确定
误差条是什么,但是
它必须具有统计意义
增加。 –亚当·内利斯2月9日15:10
我猜:
我认为Python GC是基于
参考计数。不时地
将检查参考计数
每个实例;因为你是
遍历这些巨大的内存
结构,在您的特定情况下
GC默认频率(1000
周期?)经常离开-巨大
浪费。 –您的真实2月10日2:06
我正在阅读Keras blog讲解如何使用Flask创建简单的图像分类器Restful API。我想知道如何在不使用python的其他Web框架中实现加载模型的相同方法。在下面的代码中,将在服务器启动之前将模型加载到内存中,直到服务器处于活动状态,它才会运行:# if this is the main thread of execution first lo…
无法使用Python和Node对应用程序进行代码签名 - python我有一个相当大而复杂的应用程序。未压缩的文件大小约为550兆,文件大小约为36,000。由于主要源代码在Python中,因此我使用pyInstaller创建初始的.app文件。然后,我将应用程序需要的所有其他内容(文档,示例,node_modules等)复制到Content/MacOS文件中的XXX.app子文件夹中。 (是的,它也使用node。).app正…
npm通过结构安装 - python在尝试通过Fabric在服务器上运行“ npm install”时 Ubuntu操作系统出现错误“找不到npm命令”I have installed node version v6.11.0 and npm version 3.10.10 on the server > user@ip-xx-xx-xx-xx:~$ npm -v > 3.10.…
Python sqlite3数据库已锁定 - python我在Windows上使用Python 3和sqlite3。我正在开发一个使用数据库存储联系人的小型应用程序。我注意到,如果应用程序被强制关闭(通过错误或通过任务管理器结束),则会收到sqlite3错误(sqlite3.OperationalError:数据库已锁定)。我想这是因为在应用程序关闭之前,我没有正确关闭数据库连接。我已经试过了: connectio…
如何用'-'解析字符串到节点js本地脚本? - python我正在使用本地节点js脚本来处理字符串。我陷入了将'-'字符串解析为本地节点js脚本的问题。render.js:#! /usr/bin/env -S node -r esm let argv = require('yargs') .usage('$0 [string]') .argv; console.log(argv…