如何提高此代碼的性能？

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

我也被這個絆倒了。這裏的瓶頸實際上是if neighbor in closedlist。

in聲明非常易於使用，您忘記了它是線性搜索，並且當您在列表上進行線性搜索時，它可以快速加起來。你可以做的是將關閉列表轉換爲set對象。這可以保持項目的哈希值，所以in運算符比列表更有效率。但是，列表不是可哈希的項目，所以您必須將您的配置更改爲元組而不是列表。

如果closedlist的順序對算法至關重要，那麼可以使用in運算符的集合併爲結果保留一個並行列表。

我嘗試了一個簡單的實現，包括aaronasterling的namedtuple技巧，它在第一個例子中的執行時間爲0.2秒，第二個執行的時間爲2.1秒，但是我沒有嘗試驗證第二個更長的結果。

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 毫秒輸入[fCamel, fCamel, gap, bCamel, bCamel]。它產生了相同的輸出。

這顯然不會幫助解決任何算法問題，但就微型優化而言，這並不壞。

^{1我輸入了錯誤的信息。有一個額外的fCamel，這使得它運行速度更慢}

Answer 3

下面使用小於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 4

很好的代碼，我真的不能說很您的算法是誤入歧途，但我只是說幹就幹，做了我自己。爲了儘可能做到最簡單的事情，我使用了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 5

tkerwin是正確的，你應該使用closedlist一組，從而加快了很多東西，但它是在每邊4個駱駝一種緩慢仍。接下來的問題是，你允許許多不可能的解決方案，因爲你允許fCamels倒退，bCamels前進。爲了解決這個問題，更換線，

與

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秒。我也在使用一個關閉列表和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，爲關閉列表設置，以及發現上述鄰居的變化）爲每個側面案例找到12個駱駝的解決方案至0.389秒。這並不壞。順便說一句，找到是否找到解決方案的更好方法是檢查第一個fCamel的索引是否等於編組長度/ 2 + 1（使用int除法），並且之前的指數等於差距。

Answer 6

首先讓我告訴你如何找到問題。然後我會告訴你它在哪裏：

我甚至沒有打算試圖找出你的代碼。我只是跑了它，並採取了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 7

我的其他答案很長，所以我決定把它列爲一個單獨的答案。這個問題真的更適合做深度優先搜索。我做了一個深度優先的搜索解決方案，它比我的其他答案中概述的更改（比OP代碼快得多）所做的優化的A-star方法要快得多。例如，下面是在每邊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])))