このコードのパフォーマンスを向上させるにはどうすればよいですか？

Question

ここの人々の助けを借りて、私はタスマニアのラクダパズルの仕事のためのコードを手に入れることができました。しかし、それはひどく遅いです（これはPythonの私の最初のプログラムなので、わかりません）。コードの下で実行する例は、私のマシンで解決するのに長い時間を要する：

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頭のラクダそれぞれにある：

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 

ここではコードです。私は少なくとも4のためにこれをやりたかった。このテストケースはまだ稼動しています（これは約5分後です:(）。これが終了した場合は更新します）

このコードを改善するにはどうすればよいですか（主にパフォーマンス面での提案）も歓迎されている。

感謝。

Answer 1

私はこれまでにもこれまでにトリップされています。ここのボトルネックは実際にはif neighbor in closedlistです。

inステートメントは非常に使いやすいので、線形検索であることを忘れてしまい、リストを線形検索しているときには速くなる可能性があります。あなたができることはclosedlistをsetオブジェクトに変換することです。これによりアイテムのハッシュが保持されるので、in演算子はリストよりもはるかに効率的です。ただし、リストはハッシュ可能なアイテムではないので、リストの代わりにタプルに設定を変更する必要があります。

の順番がアルゴリズムにとって重要な場合は、in演算子に1組を使用して、結果に対して並列リストを維持することができます。

私はaaronasterlingのnamedtupleトリックを含め、これを簡単に実装しようとしました。最初の例では0.2秒、2番目の例では2.1秒でしたが、2番目の長時間の結果を検証しようとはしませんでした。

Answer 2

が

node = collections.namedtuple('node', 'arrangement, g, parent') 

で

class node: 
    def __init__(self, a, g, p): 
     self.arrangement = a 
     self.g = g 
     self.parent = p 

の交換210

は約340〜600ミリ秒から に時間を落としました。 [fCamel, fCamel, gap, bCamel, bCamel]の11.4 1.89 ミリ秒です。同じ出力が得られました。

これは明らかにアルゴリズム上の問題に役立ちませんが、マイクロ最適化が行われる限り、悪くはありません。

^{1入力が間違っていました。余分にあるのはfCamelなので、遅く実行されていました。}

Answer 3

もこの

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

を解決するために1秒未満を使用して以下のコードは、私は本当にあなたのアルゴリズムが道に迷って実行されている、非常にどこ言うことはできませんが、私は先に行って、自分を作りました。おそらく動作する可能性が最も簡単なことを行うために、私はオープンノードが距離を考慮せずに任意の順序で訪問される、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秒かかりました。また、キューよりもclosedlistとheapqのセットを使用しています。

追加のスピードアップ

あなたが正しくあなたのヒューリスティックを使用して、追加のスピードアップを得ることができます。現在、あなたがライン

openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current))) 

（またはそのheapq版）を使用しているが、あなたは

openlist.put((heuristicf(neighbor), node(neighbor, current.g + 1, current))) 

にそれを変更する必要があります。この行い必要に応じてきた動きの数には影響を与えません、それは大丈夫です。このパズル（そして間違った方向にラクダを動かす動きからの選別）では、動きの回数を心配する必要はありません。動きがあなたを解決に向かって進めるか、それとも行き止まりになるでしょう。換言すれば、すべての可能な解決策は同じ数の移動を必要とする。この1回の変更では、各サイドケースの12個のラクダの解を13秒以上で見つけ出す時間がかかります（ヒープを使用し、クローズドリストを設定し、上記の隣人を見つけるための変更も0.389秒になります）。悪くない。

ところで、あなたが解決策を見つけたかどうかを見つける良い方法は、最初のfCamelのインデックスがフォーメーション/ 2 + 1（int除算を使用）の長さと等しいかどうかをチェックし、その前のインデックスはギャップに等しい。

Answer 6

まず、問題の見つけ方を教えてください。それから、どこにあるのか教えてください：

私はあなたのコードを理解しようとしていません。私はちょうどそれを実行し、3ランダムサンプルのスタックを取った。私はcontrol-Cと打ち込み、結果のスタックトレースを調べることでそれを行いました。

これを見る方法の1つは、文がX％のランダムなスタックトレースに現れた場合、それは約X％の時間スタックにあるので、それが原因です。あなたがそれを実行することを避けることができれば、それはあなたがどれくらい節約できるかです。

OK、私は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))) 

この場合、スタックサンプルはすべて同じです。言い換えれば、これらの3つの線のそれぞれは、ほとんどすべての時間に個々に責任があります。だから、彼らを見て：

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スターメソッドよりずっと高速です。たとえば、私のA-starと深さ優先の両方の検索方法をサイドケースの17個のラクダで実行した結果がここにあります。興味のある方は

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