如何提高此代码的性能？

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.883s

user    0m20.549s

sys    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&nbsp;>&nbsp;0): &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap-1)if(igap&nbsp;>&nbsp;1): &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap-2)if&nbsp;igap&nbsp;<&nbsp;len(formation)&nbsp;-&nbsp;1: &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap+1)if&nbsp;igap&nbsp;<&nbsp;len(formation)&nbsp;-&nbsp;2: &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap+2)带着if(igap&nbsp;>&nbsp;0&nbsp;and&nbsp;formation[igap-1]&nbsp;==&nbsp;fCamel): &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap-1)if(igap&nbsp;>&nbsp;1&nbsp;and&nbsp;formation[igap-2]&nbsp;==&nbsp;fCamel): &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap-2)if&nbsp;(igap&nbsp;<&nbsp;len(formation)&nbsp;-&nbsp;1)&nbsp;and&nbsp;formation[igap+1]&nbsp;==&nbsp;bCamel: &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap+1)if&nbsp;(igap&nbsp;<&nbsp;len(formation)&nbsp;-&nbsp;2)&nbsp;and&nbsp;formation[igap&nbsp;+&nbsp;2]&nbsp;==&nbsp;bCamel: &nbsp;&nbsp;&nbsp;&nbsp;genn(igap,&nbsp;igap+2)然后，我得到了每边问题上的4只骆驼的答案，大约在0.05秒，而不是10秒。我还试了5头骆驼每侧，花了0.09秒。我还使用了一组封闭列表和堆，而不是队列。额外提速通过正确地使用你的启发式，你可以得到一个额外的速度。目前，您使用的是openlist.put((current.g&nbsp;+&nbsp;heuristicf(neighbor),&nbsp;node(neighbor,&nbsp;current.g&nbsp;+&nbsp;1,&nbsp;current)))(或该版本的heapq)，但您应该将其更改为openlist.put((heuristicf(neighbor),&nbsp;node(neighbor,&nbsp;current.g&nbsp;+&nbsp;1,&nbsp;current)))这不包括所需的移动次数，但这是可以的。有了这个谜题(以及将骆驼移向错误方向的动作的筛选)，你不需要担心它所需要的移动次数-要么一步地推进你的解决方案，要么它就会走到死胡同。换句话说，所有可能的解决方案都需要相同数量的移动。这一更改需要花费时间从13秒以上(甚至使用设置为近距离列表的heapq，以及找到上述邻居的更改)到0.389秒，以找到每侧情况下的12只骆驼的解决方案。还不错。顺便说一句，如果找到了解决方案，一个更好的方法是检查第一个fCamel的指数是否等于/2+1(使用int除法)的长度，并且它之前的指数是否等于间隙。

Answer 2

顶替class&nbsp;node: &nbsp;&nbsp;&nbsp;&nbsp;def&nbsp;__init__(self,&nbsp;a,&nbsp;g,&nbsp;p): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.arrangement&nbsp;=&nbsp;a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.g&nbsp;=&nbsp;g &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.parent&nbsp;=&nbsp;p带着node&nbsp;=&nbsp;collections.namedtuple('node',&nbsp;'arrangement,&nbsp;g,&nbsp;parent')把时间从340-600米降到11.4&nbsp;1.891输入的Msecs[fCamel, fCamel, gap, bCamel, bCamel]..它产生了同样的输出。这显然无助于解决任何算法问题，但就微观优化而言，它并不坏。1我输入错误。有一个额外的fCamel这让它跑得更慢了。