¿Cómo mejorar el rendimiento de este código?

Question

Gracias a la ayuda de la gente de aquí, pude obtener mi código para el acertijo de los camellos de Tasmania trabajando. Sin embargo, es terriblemente lento (creo. No estoy seguro porque este es mi primer programa en Python). El ejemplo correr en la parte inferior del código toma un largo tiempo para ser resuelto en mi máquina:

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 

Aquí está el código:

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

Eso es sólo para 3 camellos cada uno. Quería hacer esto por 4 al menos. Ese caso de prueba aún se está ejecutando (han pasado unos 5 minutos :(). Lo actualizaré si y cuando termine.

¿Qué debo hacer para mejorar este código? (Sobre todo en cuanto a rendimiento, cualquier otra sugerencia también son bienvenidos).

Gracias.

Answer 1

Me he tropezado con esto antes también. El cuello de botella aquí es en realidad if neighbor in closedlist.

La declaración in es tan fácil de usar que olvida que es una búsqueda lineal, y cuando realiza búsquedas lineales en listas, puede sumarse rápidamente. Lo que puede hacer es convertir la lista cerrada en un objeto set. Esto mantiene el hash de sus elementos para que el operador in sea mucho más eficiente que para las listas. Sin embargo, las listas no son elementos hashable, por lo que tendrá que cambiar sus configuraciones en tuplas en lugar de listas.

Si el orden de closedlist es crucial para el algoritmo, puede usar un conjunto para el operador in y mantener una lista paralela para sus resultados.

Intenté una implementación simple de esto, incluyendo el truco de untar nombrado de aaronasterling y se realizó en 0.2 segundos para su primer ejemplo y 2.1 segundos para su segundo, pero no he intentado verificar los resultados para el segundo más largo.

Answer 2

Sustitución

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

con

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

bajó los tiempos de alrededor de 340-600 msecs a 11.4 1.89 mseg en la entrada [fCamel, fCamel, gap, bCamel, bCamel]. Dio la misma salida.

Esto obviamente no ayudará con ningún problema algorítmico, pero en lo que respecta a las micro-optimizaciones, no está mal.

^{1 Tuve una entrada incorrecta. Hubo un extra fCamel que lo hizo funcionar más lento}

Answer 3

El código de abajo usando menos de 1s para resolver este

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

bien, realmente no puedo decir con bastante donde su algoritmo está funcionando mal camino, pero simplemente siguió adelante e hizo la mía. Con el interés de hacer lo más simple que podría funcionar, utilicé una versión bastarda del algoritmo de Dijkstra, donde los nodos abiertos se visitan en orden arbitrario, sin considerar la distancia. Esto significa que no tengo que inventar una heurística.

""" 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 es correcto que usted debe utilizar un conjunto de closedlist, que acelera las cosas mucho, pero todavía es un poco lento durante 4 camellos en cada lado. El siguiente problema es que está permitiendo muchas soluciones que no son posibles porque está permitiendo que los fCamels retrocedan y bCamels para seguir adelante. Para solucionar este problema, reemplace las líneas,

con

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) 

en cuando me siento solución a los 4 camellos en cada problema en el lado como .05 segundos en lugar de 10 segundos. También probé 5 camellos en cada lado y me tomó 0.09 segundos. También estoy usando un set para closedlist y heapq en lugar de Queue.

adicional de aceleración

Usted puede obtener un adicional de aceleración mediante el uso de su heurística correctamente. Actualmente, se está utilizando la línea

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

(o la versión de que heapq), pero se debe cambiar a

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

Esto no tiene en cuenta el número de movimientos que ha sido necesario, pero está bien. Con este acertijo (y el apantallamiento de las movidas que mueven a los camellos en la dirección incorrecta), no tienes que preocuparte por la cantidad de movimientos que se requieren, ya sea que un movimiento te lleve hacia la solución o llegará a un callejón sin salida. . En otras palabras, todas las soluciones posibles requieren la misma cantidad de movimientos. Este único cambio toma el tiempo para encontrar la solución de los 12 camellos en cada caso lateral de más de 13 segundos (incluso usando el heapq, configurado para la lista cerrada, y los cambios para encontrar los vecinos más arriba) a 0.389 segundos. No esta mal.

Por cierto, una mejor manera de encontrar si ha encontrado la solución es comprobar si el índice del primer fCamel es igual a la longitud de la formación/2 + 1 (usando la división int) y que el índice antes de eso es igual a la brecha.

Answer 6

Primero déjame decirte cómo encontrar el problema. Entonces te diré dónde está:

Ni siquiera me he molestado en intentar descifrar tu código. Simplemente lo ejecuté y tomé 3 muestras de la pila al azar. Lo hice escribiendo control-C y mirando la stacktrace resultante.

Una forma de verlo es: si aparece una declaración en X% de los rastreos de pila aleatorios, entonces está en la pila durante aproximadamente el X% del tiempo, y eso es de lo que es responsable. Si pudieras evitar ejecutarlo, eso es cuánto ahorrarías.

OK, tomé 3 muestras de la pila. Aquí están:

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

Observe que, en este caso, las muestras de la pila son idénticas. En otras palabras, cada una de estas tres líneas es responsable individualmente casi todo el tiempo. Así que mírelos:

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

Claramente la línea 87 no es una que pueda evitar la ejecución, y probablemente tampoco la 85. Eso deja 80, la llamada openlist.put.Ahora, no puede decir si el problema está en el operador +, la llamada heuristicf, la llamada node, o en la llamada put. Podrías averiguar si puedes dividirlos en líneas separadas.

Así que espero que retomen de esta una manera rápida y fácil de averiguar dónde están sus problemas de rendimiento.

Answer 7

Mi otra respuesta es bastante larga, así que decidí incluir esta como una respuesta separada. Este problema es realmente más adecuado para hacer una búsqueda en profundidad. Hice una solución de búsqueda en profundidad y es mucho, mucho más rápido que el método optimizado de estrella A hecho con los cambios descritos en mi otra respuesta (que es mucho, mucho más rápido que el código OP). Por ejemplo, aquí están los resultados para ejecutar mi A-star y mis métodos de búsqueda en profundidad en los 17 camellos por caja lateral.

A-star: 14.76 seconds 
Depth-first search: 1.30 seconds 

Aquí está mi código del método de primero en profundidad si está interesado:

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