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

Question

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

pythonperformanceoptimizationtime-complexity

43

在这里得到了一些人的帮助，我成功地让我的塔斯马尼亚骆驼难题的代码运行起来了。不过，它非常慢（我想是这样的，因为这是我第一个用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])

这只是每只骆驼三个的计算方式。我希望至少可以为四只骆驼进行此操作。该测试用例仍在运行中（已经大约5分钟了:()。如果完成，我会更新这个结果。

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

- nakiya

1

@nakiya：如果您不打算创建多线程程序，则可以使用http://docs.python.org/library/heapq.html#module-heapq作为优先级队列。（尽管这不是瓶颈。） - kennytm

1

这个特定谜题的搜索空间非常小。实际上，只有140种可能的方式可以让3只骆驼朝着任意方向行进。其中并不是所有的方式都是可达的。如果你的求解器需要超过一眨眼的时间才能得出结论，那么你就在某个地方出错了。 - SingleNegationElimination

dumrat 3803 3660 98 12:49 pts/2 01:32:14 python camels.py - nakiya

@TokenMacGuy：我认为这是正确的。 :) 但我错在哪里了呢？我想不出来。 - nakiya

2

如果程序执行完毕，我会进行更新。你的代码是否曾经停止执行？ - hochl

显示剩余5条评论

7个回答

39

我之前也遇到过这个问题。瓶颈在于if neighbor in closedlist。

in语句很容易使用，但你会忘记它是线性搜索，当你对列表进行线性搜索时，速度会变慢。你可以将closedlist转换为一个set对象，这样它就会保留其项的哈希值，因此in操作符比列表更高效。但是，列表不是可哈希的项，所以你必须将配置改为元组而不是列表。

如果closedlist的顺序对算法至关重要，你可以使用一个集合来进行in运算符的操作，并在你的结果周围维护一个并行列表。

我尝试了一个简单的实现，包括aaronasterling的namedtuple技巧，并且它在你的第一个示例中执行了0.2秒，在你的第二个示例中执行了2.1秒，但我没有验证第二个更长的示例的结果。

- tkerwin

此外，集合是无序的，将潜在解决方案保存在排序容器中似乎对算法至关重要（我还不理解），因此除非可以更改算法以不依赖于排序属性，否则使用集合是相当无用的。 - aaronasterling

1

我认为保持“closedlist”的有序并不是算法关键，但我可能错了。 - tkerwin

对于在并行中使用集合的想法，我给予加1。这个想法不知怎么就逃过了我的注意。 - aaronasterling

1

如果没有其他更大的问题，in 可能会成为瓶颈 - 远远大于。 openlist.put 行中的某些内容要大得多。 - Mike Dunlavey

9

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秒。我还使用了闭合列表的set和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的索引以及其之前的索引是否等于间隙是找到解决方案的更好方法。

- Justin Peel

比我的解决方案快得多。使用正确的数据结构是标准优化，但挑出算法中的逻辑问题才是正确的方法。 - tkerwin

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]的情况下，将时间从约340-600毫秒降至1.89¹毫秒（~~11.4~~），输出结果相同。虽然这对算法问题并没有帮助，但在微观优化方面还是不错的。

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

- aaronasterling

4

下面的代码只需要不到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)

- Kabie

+1 非常不同的解决方案。请注意，这是 Python 3k（字典推导式）。 - SingleNegationElimination

请注意，自Python 2.7以来，可以使用字典推导式。 - Jan Vlcinsky

3

好的，我无法确定您的算法出了什么问题，但我已经自己编写了一个。为了做到可能的最简单的事情，我使用了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

- SingleNegationElimination

0

我的另一个答案比较长，所以我决定将其列为单独的答案。这个问题真的更适合使用深度优先搜索。我制作了一个深度优先搜索解决方案，它比在我的其他答案中概述的更改优化的A星方法要快得多（后者比OP代码快得多）。例如，在每侧有17只骆驼的情况下，同时运行我的A星和深度优先搜索方法的结果如下。

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

- Justin Peel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mike Dunlavey · Accepted Answer

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

我甚至都没有试图去理解你的代码，我只是运行了它并获取了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调用中。如果你把它们分别拆分到不同的行上，就可以找到问题所在。

因此，我希望你能从中找到一种快速简便的方法来找出性能问题的根源。