| Blog信息 |
|
blog名称:
日志总数:1304
评论数量:2242
留言数量:5
访问次数:7636657
建立时间:2006年5月29日 |
| |
|
 [Python]profile优化实践(基于A*算法)-1
软件技术
lhwork 发表于 2007/2/6 9:05:26 |
| 在《用profile协助程序性能优化》一文中，我们学习了python用以协助性能优化的模块——profile/hotshot/timeit等，但缺少一个实例来让我们动手尝试，今天我拿以前写的A*算法的python实现来开刀，临床实验。
实验用的代码可以从我以前发在blog上的文章《基本A*算法python实现》(http://blog.csdn.net/lanphaday/archive/2006/10/11/1329956.aspx)里找到，你可以从那里了解或者重温一下A*算法；不过为了使用profile，我做了一些小小的改动，所以建议你从这里(暂未能提供)下载本文相关的所有示例代码（已将每一次改进保存到独立的.py文件）以及profile的输出文档。
下面，让我们开始吧！
得来全不费功夫
定位热点
拿到代码后，可以看到代码的入口如下：
if __name__ == "__main__":
import profile, pstats
profile.run("main()", "astar_prof.txt")
p = pstats.Stats("astar_prof.txt")
p.strip_dirs().sort_stats("time").print_stats(10)
代码段1
profile.run执行main()函数，并把输出保存到astar_prof.txt，pstats.Stats的实例p把统计结果以”time”为key排序后打印出前10条。执行一下，输出结果如下：
62468 function calls in 1.258 CPU seconds
Ordered by: internal time
List reduced from 27 to 10 due to restriction <10>
ncalls tottime percall cumtime percall filename:lineno(function)
5713 0.581 0.000 0.581 0.000 origine.py:156(node_in_close)
33818 0.208 0.000 0.208 0.000 origine.py:111(get_dist)
778 0.178 0.000 0.387 0.000 origine.py:99(get_best)
778 0.150 0.000 0.851 0.001 origine.py:119(extend_round)
2933 0.048 0.000 0.048 0.000 origine.py:162(node_in_open)
6224 0.028 0.000 0.028 0.000 origine.py:168(is_valid_coord)
5714 0.022 0.000 0.022 0.000 origine.py:46(__init__)
5713 0.021 0.000 0.021 0.000 origine.py:148(get_cost)
1 0.016 0.016 1.256 1.256 origine.py:71(find_path)
778 0.003 0.000 0.003 0.000 origine.py:96(is_target)
输出1
其中node_in_close()函数用以检测可扩展的节点是否在close表中，这个简单的函数占用了46%的运行时间，差不多是排第二的get_dist()函数的三倍，我们的优化显然应该从node_in_colse()入手。优化一个函数，第一个方法应该是减少它的调用次数，然后才是优化这个函数本身，所以我们先在“代码段1”后面加入一条语句，用以查看哪个函数调用了node_in_close()：
p.print_callers("node_in_close")输出结果如下：
Ordered by: internal time
List reduced from 27 to 1 due to restriction <'node_in_close'>
Function was called by...
origine.py:156(node_in_close) origine.py:119(extend_round)(5713) 0.851
输出2
我们看到只有extend_round函数调用了node_in_close()，看起来情况相当简明，extend_round()函数用以扩展搜索空间，有关node_in_close的代码段如下：
#构造新的节点
node = Node_Elem(p, new_x, new_y, p.dist+self.get_cost(
p.x, p.y, new_x, new_y))
#新节点在关闭列表，则忽略
if self.node_in_close(node):
continue
代码段2
从“代码段2”可以看到根据A*算法我们必然要检测node是否在close表中，所以无法在extend_round()中减少对node_in_close()函数的调用了。那我们只好在node_in_close()函数里找突破口：
def node_in_close(self, node):
for i in self.close:
if node.x == i.x and node.y == i.y:
return True
return False
代码段3
马上可以看出这是一个对list的线性查找，在close表变得很大的时候，这种复杂度为O(N)的线性算法是相当耗时的，如果能转化为O(logN)的算法那就能节省不少时间了。O(logN)的查找算法基于两个数据结构，一个是有序表，另一个是二叉查找树。显然，对于频繁插入而不删除元素的list保持有序的代价非常大，使用查找树是我们更好的选择。
修改代码
在程序里加入二叉查找树支持非常简单，python2.3开始增加了sets模块，提供了以RB_tree为底层数据结构的Set类：
from sets import Set as set然后在把close表初始化为一个空set
self.close = set()把self.close.append(p)语句替换为：
self.close.add(p)最关键的是重写node_in_close()函数为：
def node_in_close(self, node):
return node in self.close
代码段4
简简单单就可以了，但这时候程序还不能运行，因为原来的Node_Elem类并不支持__hash__和__eq__函数，这样set就无法构造也无法查找元素了，所以最后一步是为Node_Elem增加这两个函数：
class Node_Elem:
def __init__(self, parent, x, y, dist):
# …略
self.hv = (x << 16) ^ y
def __eq__(self, other):
return self.hv == other.hv
def __hash__(self):
return self.hv
代码段5
在构造函数中，我们加了一句self.hv=(x<<8)^y来计算一个Node_Elem元素的hash值，因为坐标相同的两个节点我们认为是相等的且坐标数值不会很大，所以这个hash函数可以保证不会产生冲突。大功告成之后我们运行一下看看：
78230 function calls in 0.845 CPU seconds
Ordered by: internal time
List reduced from 33 to 10 due to restriction <10>
ncalls tottime percall cumtime percall filename:lineno(function)
33818 0.205 0.000 0.205 0.000 astar.py:120(get_dist)
778 0.179 0.000 0.383 0.000 astar.py:108(get_best)
778 0.150 0.000 0.426 0.001 astar.py:128(extend_round)
5713 0.068 0.000 0.097 0.000 sets.py:292(__contains__)
5713 0.052 0.000 0.149 0.000 astar.py:165(node_in_close)
2933 0.050 0.000 0.050 0.000 astar.py:172(node_in_open)
6224 0.028 0.000 0.028 0.000 astar.py:178(is_valid_coord)
5714 0.028 0.000 0.028 0.000 astar.py:48(__init__)
6490 0.021 0.000 0.021 0.000 astar.py:58(__hash__)
5713 0.021 0.000 0.021 0.000 astar.py:157(get_cost)
输出3
我们可以看到，总的运行时间已经从1.258s下降到0.845s，而且node_in_close函数占用的时间已经相当少，不过因为node_in_close只在一个地方被调用，而且函数体本身就非常简单，那么我们可以去掉这个函数，直接在extend_round里进行判断，可以省下几千次函数调用的时间。
在这一步优化里，我们可以看到使用合适的数据结构可以增进数十倍的性能（使用list用时0.581s，使用set用时0.052s），随着地图的增大，这个比例将会更大。而profile也在这一个小节里初显身手，下一步又该怎么样去优化呢？ |
|
|