如何提高此代码的性能？

Question

如何提高此代码的性能？多亏了这里的一些人的帮助，我才能让我的塔斯马尼亚骆驼谜题的代码工作起来。然而，它是可怕的缓慢(我认为。我不确定，因为这是我在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.883suser    0m20.549ssys    0m0.020s下面是代码：import QueuefCamel = 'F'bCamel = 'B'gap = 'G'def solution(formation):     return len([i for i in formation[formation.index(fCamel) + 1:]                 if i == bCamel]) == 0def heuristic(formation):     fCamels, score = 0, 0     for i in formation:         if i == fCamel:             fCamels += 1;         elif i == bCamel:             score += fCamels;         else:             pass     return scoredef 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)每个只给3只骆驼。我至少想做4次。这个测试用例仍然在运行(现在大约5分钟了：()。如果它完成的话我会更新的。我应该做些什么来改进这个代码呢？(主要是在性能方面，但任何其他建议也是受欢迎的)。

Answer 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只骆驼的答案，大约在0.05秒，而不是10秒。我还试了5头骆驼每侧，花了0.09秒。我还使用了一组封闭列表和堆，而不是队列。

额外提速

通过正确地使用你的启发式，你可以得到一个额外的速度。目前，您使用的是

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，以及找到上述邻居的更改)到0.389秒，以找到每侧情况下的12只骆驼的解决方案。还不错。

顺便说一句，如果找到了解决方案，一个更好的方法是检查第一个fCamel的指数是否等于/2+1(使用int除法)的长度，并且它之前的指数是否等于间隙。

Answer 2

顶替

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¹输入的Msecs[fCamel, fCamel, gap, bCamel, bCamel]..它产生了同样的输出。

这显然无助于解决任何算法问题，但就微观优化而言，它并不坏。

^{1我输入错误。有一个额外的fCamel这让它跑得更慢了。}