如何提高这个代码的性能？
感谢来自这里的人们的帮助，我能够得到我的塔斯马尼亚骆驼拼图代码工作。 然而，这是非常慢的（我想，我不确定，因为这是我的第一个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 : xf > yf) 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])
那只是三只骆驼。 我至less想要做到这一点。 那个testing用例还在运行（现在已经是5分钟了:(），我会在更新完成后更新它。
我应该怎样做才能改进这个代码？（主要是性能方面，还有其他build议也是可以的）。
谢谢。
我也被绊倒了。 这里的瓶颈实际上if neighbor in closedlist 。
in声明是如此容易使用，你忘了它是线性search，当你在列表上进行线性search时，它可以快速加起来。 你可以做的是将closures列表转换为set对象。 这保持了它的项目散列，所以in运算符比列表更有效率。 但是，列表不是可哈希的项目，所以您将不得不将您的configuration更改为元组而不是列表。
如果closedlist的顺序对algorithm至关重要，那么可以使用in运算符的集合，并为结果保留一个并行列表。
我尝试了一个简单的实现，其中包括aaronasterling的命名技巧，它在第一个例子中是0.2秒，第二个是2.1秒，但是我没有尝试validation第二个结果。
首先让我告诉你如何find问题。 那么我会告诉你它在哪里：
我甚至没有打算试图找出你的代码。 我只是跑了它，并采取了3个随机堆栈样本。 我通过inputcontrol-C来查看结果堆栈跟踪。
一种看待它的方法是：如果一个语句出现在随机堆栈跟踪的X％上，那么它在堆栈上大约有X％的时间，所以这就是它的责任。 如果你能避免执行它，那么你将会节省多less。
好的，我拿了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调用中。 你可以看看你是否可以将这些分离出来。
所以我希望你能从中快速轻松地find你的性能问题。
tkerwin是正确的，你应该使用一个closures列表，这加快了很多东西，但它仍然有点缓慢，每边4个骆驼。 接下来的问题是，你允许许多解决scheme，因为你允许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)
然后我得到解决scheme，在每个问题的四个骆驼在0.05秒，而不是10秒。 我也尝试了5只骆驼，每次只花了0.09秒。 我也使用一个closures列表和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)))
这并不影响所需要的移动次数，但是没关系。 有了这个难题（以及放弃将骆驼朝错误方向移动的举动），您无需担心所需要的移动次数，无论是一举一动都可以朝着解决scheme迈进，也可能会走向死胡同。 换句话说，所有可能的解决scheme都需要相同数量的移动。 这一个改变需要花费时间从13秒以上（甚至使用heapq，设置为closures列表，以及发现上述邻居的改变）到每个scheme的12个骆驼的解决scheme到0.389秒。 这并不坏。
顺便说一下，find解决方法的一个更好的方法是检查第一个fCamel的索引是否等于地层/ 2 + 1的长度（使用int除法），并且之前的索引是等于差距。
更换
class node: def __init__(self, a, g, p): self.arrangement = a self.g = g self.parent = p
同
node = collections.namedtuple('node', 'arrangement, g, parent')
将投入时间从340-600毫秒降至11.4 1.89 [fCamel, fCamel, gap, bCamel, bCamel] 。 它产生了相同的输出。
这显然不会帮助解决任何algorithm问题，但就微观优化而言，这并不坏。
1我有错误的input。 有一个额外的fCamel ，使其运行速度较慢
下面的代码使用小于1秒来解决这个问题
from itertools import permutations GAP='G' LEFT='F' RIGHT='B' BEGIN=('F','F','F','F','G','B','B','B','B') END=('B','B','B','B','G','F','F','F','F') LENGTH=len(BEGIN) ALL=set(permutations(BEGIN)) def NextMove(seq): g=seq.index(GAP) ret = set() def swap(n): return seq[:n]+seq[n:n+2][::-1]+seq[n+2:] if g>0 and seq[g-1]==LEFT: ret.add(swap(g-1)) if g<LENGTH-1 and seq[g+1]==RIGHT: ret.add(swap(g)) if g<LENGTH-2 and seq[g+1]==LEFT and seq[g+2]==RIGHT: ret.add(seq[:g]+seq[g+2:g+3]+seq[g+1:g+2]+seq[g:g+1]+seq[g+3:]) if g>1 and seq[g-1]==RIGHT and seq[g-2]==LEFT: ret.add(seq[:g-2]+seq[g:g+1]+seq[g-1:g]+seq[g-2:g-1]+seq[g+1:]) return ret AllMoves={state:NextMove(state) for state in ALL} def Solve(now,target): if now==target: return True for state in AllMoves[now]: if Solve(state,target): print(now) return True return False Solve(BEGIN,END)
好吧，我不能确切地说你的algorithm在哪里运行，但我只是继续前进，自己做了。 为了尽可能做到最简单的事情，我使用了Dijkstraalgorithm的混合版本，其中开放节点以任意顺序访问，而不考虑距离。 这意味着我不必拿出一个启发式。
""" notation: a game state is a string containing angle brackets ('>' and '<') and blanks '>>> <<<' """ def get_moves(game): result = [] lg = len(game) for i in range(lg): if game[i] == '>': if i < lg-1 and game[i+1] == ' ': # '> ' -> ' >' result.append(game[:i]+' >'+game[i+2:]) if i < lg-2 and game[i+1] != ' ' and game[i+2] == ' ': # '>< ' -> ' <>' result.append(game[:i]+' '+game[i+1]+'>'+game[i+3:]) if game[i] == '<': if i >= 1 and game[i-1] == ' ': # ' <' -> '< ' result.append(game[:i-1]+'< '+game[i+1:]) if i >= 2 and game[i-1] != ' ' and game[i-2] == ' ': # ' ><' -> '<> ' result.append(game[:i-2]+'<'+game[i-1]+' '+game[i+1:]) return result def wander(start, stop): fringe = [start] paths = {} paths[start] = () def visit(state): path = paths[state] moves = [move for move in get_moves(state) if move not in paths] for move in moves: paths[move] = paths[state] + (state,) fringe.extend(moves) while stop not in paths: visit(fringe.pop()) print "still open: ", len(fringe) print "area covered: " , len(paths) return paths[stop] + (stop,) if __name__ == "__main__": start = '>>>> <<<<' stop = '<<<< >>>>' print start, " --> ", stop pathway = wander(start,stop) print len(pathway), "moves: ", pathway
我的其他答案是相当长的，所以我决定列出这是一个单独的答案。 这个问题真的更适合做深度优先search。 我做了一个深度优先的search解决scheme，它比我的其他答案（这比OP代码快得多）中所述的变化所做的优化的A-star方法要快得多。 例如，下面是在每个侧面17个骆驼上运行我的A-star和我的深度优先search方法的结果。
A-star: 14.76 seconds Depth-first search: 1.30 seconds
如果您感兴趣，以下是我的深度优先方法代码：
from sys import argv fCamel = 'F' bCamel = 'B' gap = 'G' def issolution(formlen): def solution(formation): if formation[formlen2] == gap: return formation.index(fCamel) == x return 0 x = formlen/2 + 1 formlen2 = formlen/2 return solution def solve(formation): def depthfirst(form, g): if checksolution(form): return [tuple(form)], g + 1 else: igap = form.index(gap) if(igap > 1 and form[igap-2] == fCamel): form[igap-2],form[igap] = form[igap],form[igap-2] res = depthfirst(form,g+1) form[igap-2],form[igap] = form[igap],form[igap-2] if res != 0: return [tuple(form)]+res[0],res[1] if (igap < flen - 2) and form[igap + 2] == bCamel: form[igap+2],form[igap] = form[igap],form[igap+2] res = depthfirst(form,g+1) form[igap+2],form[igap] = form[igap],form[igap+2] if res != 0: return [tuple(form)]+res[0],res[1] if(igap > 0 and form[igap-1] == fCamel): form[igap-1],form[igap] = form[igap],form[igap-1] res = depthfirst(form,g+1) form[igap-1],form[igap] = form[igap],form[igap-1] if res != 0: return [tuple(form)]+res[0],res[1] if (igap < flen - 1) and form[igap+1] == bCamel: form[igap+1],form[igap] = form[igap],form[igap+1] res = depthfirst(form,g+1) form[igap+1],form[igap] = form[igap],form[igap+1] if res != 0: return [tuple(form)]+res[0],res[1] return 0 flen = len(formation) checksolution = issolution(flen) res = depthfirst(list(formation), 0) return res L = lambda x: tuple([fCamel]*x + [gap] + [bCamel]*x) print solve(L(int(argv[1])))
