nak*_*iya 38 python optimization performance time-complexity
感谢来自这里的人们的帮助,我能够获得塔斯马尼亚骆驼拼图工作的代码.然而,它非常慢(我想.我不确定,因为这是我在Python中的第一个程序).在代码底部运行的示例需要很长时间才能在我的机器中解决:
dumrat@dumrat:~/programming/python$ time python camels.py
[['F', 'F', 'F', 'G', 'B', 'B', 'B'], ['F', 'F', 'G', 'F', 'B', 'B', 'B'],
['F', 'F', 'B', 'F', 'G', 'B', 'B'], ['F', 'F', 'B', 'F', 'B', 'G', 'B'],
['F', 'F', 'B', 'G', 'B', 'F', 'B'], ['F', 'G', 'B', 'F', 'B', 'F', 'B'],
['G', 'F', 'B', 'F', 'B', 'F', 'B'], ['B', 'F', 'G', 'F', 'B', 'F', 'B'],
['B', 'F', 'B', 'F', 'G', 'F', 'B'], ['B', 'F', 'B', 'F', 'B', 'F', 'G'],
['B', 'F', 'B', 'F', 'B', 'G', 'F'], ['B', 'F', 'B', 'G', 'B', 'F', 'F'],
['B', 'G', 'B', 'F', 'B', 'F', 'F'], ['B', 'B', 'G', 'F', 'B', 'F', 'F'],
['B', 'B', 'B', 'F', 'G', 'F', 'F']]
real 0m20.883s
user 0m20.549s
sys 0m0.020s
这是代码:
import Queue
fCamel = 'F'
bCamel = 'B'
gap = 'G'
def solution(formation):
return len([i for i in formation[formation.index(fCamel) + 1:]
if i == bCamel]) == 0
def heuristic(formation):
fCamels, score = 0, 0
for i in formation:
if i == fCamel:
fCamels += 1;
elif i == bCamel:
score += fCamels;
else:
pass
return score
def getneighbors (formation):
igap = formation.index(gap)
res = []
# AB_CD --> A_BCD | ABC_D | B_ACD | ABD_C
def genn(i,j):
temp = list(formation)
temp[i], temp[j] = temp[j], temp[i]
res.append(temp)
if(igap > 0):
genn(igap, igap-1)
if(igap > 1):
genn(igap, igap-2)
if igap < len(formation) - 1:
genn(igap, igap+1)
if igap < len(formation) - 2:
genn(igap, igap+2)
return res
class node:
def __init__(self, a, g, p):
self.arrangement = a
self.g = g
self.parent = p
def astar (formation, heuristicf, solutionf, genneighbors):
openlist = Queue.PriorityQueue()
openlist.put((heuristicf(formation), node(formation, 0, None)))
closedlist = []
while 1:
try:
f, current = openlist.get()
except IndexError:
current = None
if current is None:
print "No solution found"
return None;
if solutionf(current.arrangement):
path = []
cp = current
while cp != None:
path.append(cp.arrangement)
cp = cp.parent
path.reverse()
return path
#arr = current.arrangement
closedlist.append(current)
neighbors = genneighbors(current.arrangement)
for neighbor in neighbors:
if neighbor in closedlist:
pass
else:
openlist.put((current.g + heuristicf(neighbor),
node(neighbor, current.g + 1, current)))
#sorted(openlist, cmp = lambda x, y : x.f > y.f)
def solve(formation):
return astar(formation, heuristic, solution, getneighbors)
print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
#print solve([fCamel, fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel, bCamel])
那只是3只骆驼.我想至少4个这样做.那个测试用例仍然在运行(现在大概是5分钟:().如果它完成,我会更新它.
我该怎么做才能改进这段代码？(大多数是性能方面的,但也欢迎任何其他建议).
Mik*_*vey 59
首先让我告诉你如何找到问题.然后我会告诉你它在哪里:
我甚至不打算试图找出你的代码.我刚刚运行它并采集了3个随机时间的堆栈样本.我通过键入control-C并查看生成的堆栈跟踪来做到这一点.
查看它的一种方法是:如果一个语句出现在X%的随机堆栈跟踪上,那么它在堆栈上大约有X%的时间,所以这就是它的责任.如果你可以避免执行它,那就是你要节省多少钱.
好的,我拿了3个堆栈样本.他们来了:
File "camels.py", line 87, in <module>
print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
File "camels.py", line 87, in <module>
print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
File "camels.py", line 87, in <module>
print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
File "camels.py", line 85, in solve
return astar(formation, heuristic, solution, getneighbors)
File "camels.py", line 80, in astar
openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
请注意,在这种情况下,堆栈样本都是相同的.换句话说,这三行中的每一行几乎在所有时间都是单独负责的.所以看看它们:
line 87: print solve([fCamel, fCamel, fCamel, gap, bCamel, bCamel, bCamel])
line solve: 85: return astar(formation, heuristic, solution, getneighbors)
line astar: 80: openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
显然,第87行不是你可以避免执行的,也可能不是85.这就是80号openlist.put通话.现在,您无法判断问题是在+运营商,heuristicf呼叫,node呼叫还是put呼叫中.您可以找出是否可以将它们分成不同的行.
因此,我希望您能从中快速轻松地找到解决性能问题的方法.
tke*_*win 38
我之前也被这个绊倒了.实际上这里的瓶颈if neighbor in closedlist.
该in语句非常易于使用,您忘记了它是线性搜索,当您在列表上进行线性搜索时,它可以快速加起来.你可以做的是将closedlist转换为一个set对象.这样可以保持其项目的哈希值,因此in运算符比列表更有效.但是,列表不是可清除的项目,因此您必须将配置更改为元组而不是列表.
如果顺序对closedlist算法至关重要,则可以为in运算符使用集合,并为结果保留并行列表.
我尝试了一个简单的实现,包括aaronasterling的namedtuple技巧,你的第一个例子在0.2秒内执行,第二个例子在2.1秒执行,但我没有尝试验证第二个更长的结果.
tkerwin是正确的,你应该使用一个关闭列表的集合,这会加快速度,但对于每一侧的4只骆驼来说仍然有点慢.接下来的问题是你允许很多不可能的解决方案,因为你允许fCamels倒退而bCamels继续前进.要解决此问题,请更换线条,
if(igap > 0):
genn(igap, igap-1)
if(igap > 1):
genn(igap, igap-2)
if igap < len(formation) - 1:
genn(igap, igap+1)
if igap < len(formation) - 2:
genn(igap, igap+2)
同
if(igap > 0 and formation[igap-1] == fCamel):
genn(igap, igap-1)
if(igap > 1 and formation[igap-2] == fCamel):
genn(igap, igap-2)
if (igap < len(formation) - 1) and formation[igap+1] == bCamel:
genn(igap, igap+1)
if (igap < len(formation) - 2) and formation[igap + 2] == bCamel:
genn(igap, igap+2)
然后我在每个问题上得到4个骆驼的解决方案,比如.05秒而不是10秒.我也试过每边5只骆驼,花了0.09秒.我也使用了一个关闭列表和heapq而不是Queue的集合.
额外的加速
通过正确使用启发式,您可以获得额外的加速.目前,您正在使用该行
openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
(或者那个的heapq版本),但你应该把它改成
openlist.put((heuristicf(neighbor), node(neighbor, current.g + 1, current)))
这并不考虑所需的移动次数,但这没关系.有了这个谜题(以及移动骆驼向错误方向移动的移动),你不需要担心它所采取的移动次数 - 要么是一个移动使你前进到解决方案,要么它将走向死胡同.换句话说,所有可能的解决方案都需要相同数量的移动.这一次更改需要花费时间从超过13秒(甚至使用heapq,设置为closedlist,以及更改以找到上面的邻居)找到每个侧面情况下12只骆驼的解决方案为0.389秒.那不错.
顺便说,一种更好的方式找到,如果你已经找到了解决方案是检查第一fCamel的索引等于地层/ 2 + 1(使用INT除法)的长度,并且在此之前,该索引是等于差距.