python - optimizing - ¿Cómo mejorar el rendimiento de este código?
python optimize for loop (7)
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 que se ejecuta en la parte inferior del código tarda mucho tiempo en resolverse 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 solo para 3 camellos cada uno. Quería hacer esto por 4 al menos. Ese caso de prueba todavía se está ejecutando (Han pasado aproximadamente 5 minutos :(). Lo actualizaré siempre y cuando termine.
¿Qué debo hacer para mejorar este código? (Sobre todo en cuanto a rendimiento, cualquier otra sugerencia también es bienvenida).
Gracias.
Bueno, realmente no puedo decir dónde se está descarrilando tu algoritmo, pero yo seguí adelante y hice el mío. 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
El siguiente código usa menos de 1s para resolver esto
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)
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 puedes hacer es convertir una set 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 la lista 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 tipeo nombrado de aaronasterling y se realizó en 0.2 segundos para tu primer ejemplo y 2.1 segundos para tu segundo, pero no he intentado verificar los resultados para el segundo más largo.
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 de método de 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])))
Primero déjame decirte cómo encontrar el problema. Entonces te diré dónde está:
Ni siquiera me molesté en tratar de 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 X% de las veces, y eso es de lo que es responsable. Si pudieras evitar ejecutarlo, eso es cuánto ahorrarías.
OK, tomé 3 muestras de 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)))
Tenga en cuenta que, en este caso, las muestras de pila son todas idénticas. En otras palabras, cada una de estas tres líneas es responsable individualmente casi todo el tiempo. Así que míralos:
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 ejecutarse, 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 al node o en la llamada a la redirección. 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.
Reemplazando
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'')
redujo los tiempos de alrededor de 340-600 msecs a 11.4 1.89 1 mseg en la entrada [fCamel, fCamel, gap, bCamel, bCamel] . Dio la misma salida.
Obviamente, esto no ayudará con ningún problema algorítmico, pero en lo que respecta a las microoptimizaciones, no está mal.
1 Tenía la entrada incorrecta. Había un fCamel extra que lo hacía funcionar más lento
tkerwin tiene razón al decir que deberías estar usando un conjunto de listas cerradas, lo que acelera mucho las cosas, pero sigue siendo lento para 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 esto, reemplace las líneas,
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)
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)
entonces obtengo la solución a los 4 camellos en cada problema lateral en .05 segundos en vez 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.
Aceleración adicional
Puede obtener una aceleración adicional al usar su heurística correctamente. Actualmente, estás usando la línea
openlist.put((current.g + heuristicf(neighbor), node(neighbor, current.g + 1, current)))
(o la versión de Heapq de eso), pero debe cambiarlo a
openlist.put((heuristicf(neighbor), node(neighbor, current.g + 1, current)))
Esto no tiene en cuenta el número de movimientos que se han necesitado, 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 verificar 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 anterior es igual a la brecha.