Comment améliorer les performances de ce code?

Question

Grâce à l'aide de quelques personnes ici, j'ai pu obtenir mon code de Tasmanie chameaux puzzle de travail. Cependant, il est horriblement lent (je pense. Je ne suis pas sûr, parce que c'est mon premier programme en python). L'exemple exécuter dans le fond de la code prend du temps à être résolu dans ma machine:

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

Voici le code:

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

C'est juste pour les 3 chameaux chaque. Je voulais le faire pour 4 au moins. Ce scénario de test est toujours en cours (Il est à environ 5 minutes à maintenant :(). Je vais mettre à jour ce si et quand il se termine.

Que dois-je faire pour améliorer ce code?(Surtout au niveau des performances, toutes les autres suggestions sont les bienvenus aussi).

Merci.

Answer 1

D'abord, permettez-moi de vous dire comment trouver le problème. Alors, je vais vous dire où il est:

Je n'ai même pas pris la peine d'essayer de comprendre votre code. J'ai juste couru et a pris 3 random-temps de la pile des échantillons. Je l'ai fait en tapant control-C et en regardant la résultante stacktrace.

Une façon de voir les choses est la suivante: si un énoncé apparaît sur X% de l'aléatoire des traces de pile, alors il est sur la pile à propos de X% du temps, donc qu'est ce qu'il en est responsable. Si vous pouviez éviter de l'exécution, c'est-à combien vous économisez.

OK, j'ai pris 3 échantillons de la pile. Ici, ils sont:

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

Avis, dans ce cas, la pile échantillons sont toutes identiques. En d'autres termes, chacun de ces trois lignes est individuellement responsable de presque tous les temps. Afin d'oeil:

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

Clairement la ligne 87 n'est pas celui que vous pouvez éviter en cours d'exécution, et probablement pas 85 soit. Que les feuilles 80, openlist.put appel. Maintenant, vous ne pouvez pas dire si le problème est dans l' + de l'opérateur, l' heuristicf appel, l' node d'appels, ou dans l' put appel. Vous pouvez trouver si vous pouviez split celles sur des lignes séparées.

Donc j'espère que vous chercher à partir de ce un moyen facile et rapide de trouver où vos problèmes de performances.

Answer 2

J'ai été fauché par cela avant de trop. Le goulot d'étranglement est, en réalité, if neighbor in closedlist.

L' in déclaration est tellement facile à utiliser, vous oubliez que c'est la recherche linéaire, et quand vous faites linéaire des recherches sur les listes, il peut ajouter jusqu'à rapide. Ce que vous pouvez faire est de convertir closedlist en set objet. Cela permet de maintenir les hachages de ses éléments afin que le in opérateur est beaucoup plus efficace que pour les listes. Cependant, les listes ne sont pas hashable éléments, de sorte que vous devrez changer vos configurations dans des tuples au lieu de listes.

Si l'ordre d' closedlist est crucial pour l'algorithme, vous pouvez utiliser un jeu pour l' in de l'opérateur et de garder un parallèle liste autour de vos résultats.

J'ai essayé une simple mise en œuvre de ce dont aaronasterling de namedtuple truc et qu'il a réalisées dans 0,2 sec pour votre premier exemple et 2.1 sec pour votre deuxième, mais je n'ai pas essayé de vérifier les résultats de la deuxième plus longue.

Answer 3

tkerwin est correct que vous devriez être en utilisant un ensemble de closedlist, ce qui accélère les choses beaucoup, mais il est encore un peu lent pour 4 chameaux sur chaque côté. Le problème suivant est que vous permettant à tout un tas de solutions qui ne sont pas possible parce que vous êtes en permettant fCamels pour aller vers l'arrière et bCamels à aller de l'avant. Pour résoudre ce problème, remplacez les lignes,

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)

avec

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)

puis-je obtenir une solution à l'4 chameaux sur chaque côté problème comme .05 secondes au lieu de 10 secondes. J'ai aussi essayé 5 chameaux sur chaque côté, et il a fallu 0.09 secondes. Moi aussi je suis à l'aide d'un ensemble de closedlist et heapq plutôt que de la File d'attente.

De vitesse supplémentaire-jusqu'

Vous pouvez obtenir un montant supplémentaire de vitesse à l'aide de votre heuristique correctement. Actuellement, vous êtes à l'aide de la ligne de

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

(ou le heapq version de cela), mais vous devez la modifier pour

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

Ce ne sont pas comptabilisés dans le nombre de coups qui ont été nécessaires, mais c'est correct. Avec ce casse-tête (et le dépistage des mouvements qui déplacent des chameaux dans la mauvaise direction), vous n'avez pas besoin de s'inquiéter sur le nombre de coups, il faut - soit déplacer les progrès vers la solution ou elle viendra à une impasse. En d'autres termes, toutes les solutions possibles nécessitent le même nombre de coups. Ce changement prend le temps de trouver la solution de l'12 chameaux sur chaque côté de cas de plus de 13 secondes (même à l'aide de la heapq, ensemble pour closedlist, et les changements de trouver les voisins ci-dessus) sont établis à 0,389 secondes. Ce n'est pas mauvais.

Par ailleurs, une meilleure façon de savoir si vous avez trouvé la solution est de vérifier si l'indice de la première fCamel est égale à la durée de la formation/2 + 1(en utilisant int division) et que l'indice est égale à l'écart.

Answer 4

Remplacement

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

avec

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

a chuté les temps d'environ 340-600 ms à 11,4 1,89 ¹ ms sur l'entrée [fCamel, fCamel, gap, bCamel, bCamel] . Il a donné le même résultat.

Cela n'aidera évidemment pas les problèmes algorithmiques, mais en ce qui concerne les micro-optimisations, ce n'est pas mal.

^{1 J'ai eu la mauvaise entrée. Il y avait un fCamel supplémentaire qui le ralentissait}

Answer 5

Le code ci-dessous utilise moins de 1 pour résoudre ce problème

 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)