如何提高这段代码的性能？

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 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 分钟了:()。如果完成，我会更新它。

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

Answer 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 调用。您可以看看是否可以将它们分成单独的行。

因此，我希望您能从中学到一种快速、简单的方法来找出性能问题所在。

Answer 2

我以前也被这个绊倒过。这里的瓶颈实际上是如果邻居在闭合列表中。

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

如果 closelist 的顺序对算法至关重要，您可以使用 in 运算符的集合，并为结果保留一个并行列表。

我尝试了一个简单的实现，包括 aaronasterling 的命名元组技巧，第一个示例的执行时间为 0.2 秒，第二个示例的执行时间为 2.1 秒，但我还没有尝试验证第二个较长示例的结果。

Answer 3

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)

我在 0.05 秒而不是 10 秒内得到了每侧 4 只骆驼问题的解决方案。我还尝试了每边5只骆驼，花了0.09秒。我还使用一组 closelist 和 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，设置为 closelist，以及查找上面的邻居的更改）到 0.389 秒才能找到每一侧情况下 12 只骆驼的解。那还不错。

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

Answer 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')

输入 [fCamel, fCamel, gap, bCamel, bCamel]11.4 1.89¹ 毫秒>。它产生了相同的输出。

这显然对解决任何算法问题没有帮助，但就微观优化而言，这还不错。

^{1 我输入错误。有一个额外的 fCamel 使其运行速度变慢。}

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

Answer 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

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