如何提高此代码的性能？

问题描述：

感谢这里的一些人的帮助，我能够让我的塔斯马尼亚骆驼拼图代码运行起来。但是，它的速度非常慢（我认为如此。我不确定，因为这是我的第一个 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 分钟了 :()。如果完成，我会更新此内容。

我应该怎么做才能改进这段代码？（主要是性能方面，但也欢迎任何其他建议）。

解决方案 1：

首先让我告诉你如何找到问题。然后我会告诉你问题在哪里：

我甚至没有费心去弄清楚你的代码。我只是运行它并获取了 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调用中。您可以看看是否可以将它们拆分到不同的行上。

所以我希望您能从中找到一种快速简便的方法来找出您的性能问题所在。

解决方案 2：

我以前也遇到过这个问题。这里的瓶颈其实是if neighbor in closedlist。

该in语句非常易于使用，以至于您会忘记它是线性搜索，而当您在列表上进行线性搜索时，它会快速累加。您可以做的是将 closedlist 转换为对象set。这会保留其项目的哈希值，因此in运算符比列表更高效。但是，列表不是可哈希的项目，因此您必须将配置更改为元组而不是列表。

如果顺序closedlist对于算法来说至关重要，那么您可以使用一个集合作为in运算符并为结果保留一个并行列表。

我尝试了一个简单的实现，包括 aaronasterling 的 namedtuple 技巧，第一个例子执行了 0.2 秒，第二个例子执行了 2.1 秒，但我还没有尝试验证第二个较长例子的结果。

解决方案 3：

tkerwin 说得对，你应该使用一个集合作为 closedlist，这样可以大大加快速度，但对于每边 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 秒。我还使用了 closedlist 和 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)))

这没有考虑所需的移动次数，但没关系。有了这个谜题（以及筛选出将骆驼移向错误方向的移动），您无需担心所需的移动次数 - 移动一次可以使您朝着解决方案前进，或者走到死胡同。换句话说，所有可能的解决方案都需要相同数量的移动。这一改变将找到每边 12 只骆驼的解决方案所需的时间从超过 13 秒（即使使用 heapq、closedlist 的设置以及上述查找邻居的更改）缩短到 0.389 秒。这还不错。

顺便说一句，判断是否找到解决方案的更好方法是检查第一个 fCamel 的索引是否等于编队的长度/2 + 1（使用 int 除法）以及其之前的索引是否等于间隙。

解决方案 4：

更换

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 1毫秒[fCamel, fCamel, gap, bCamel, bCamel]。输出相同。

这显然不会对任何算法问题有帮助，但就微优化而言，这并不坏。

1 我输入了错误的内容。有一个额外的fCamel内容导致它运行得更慢。

解决方案 5：

下面的代码用了不到 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)

解决方案 6：

好吧，我真说不出你的算法哪里出了问题，但我还是自己做了一个。为了尽可能做最简单的事情，我使用了 Dijkstra 算法的混杂版本，其中开放节点以任意顺序访问，而不考虑距离。这意味着我不必想出启发式算法。

""" 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

解决方案 7：

我的另一个答案相当长，所以我决定将其列为单独的答案。这个问题实际上更适合进行深度优先搜索。我制作了一个深度优先搜索解决方案，它比使用我的另一个答案中概述的更改进行的优化 A-star 方法（比 OP 代码快得多）要快得多。例如，以下是在每边 17 个骆驼的情况下运行我的 A-star 和深度优先搜索方法的结果。

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])))