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

Gracias a la ayuda de la gente de aquí, pude hacer funcionar mi código para el rompecabezas de los camellos de Tasmania. Sin embargo, es terriblemente lento (creo que no estoy seguro porque este es mi primer programa en Python). El ejemplo ejecutado al final del código tarda mucho 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 sólo para 3 camellos cada uno. Quería hacer esto durante al menos 4. Ese caso de prueba todavía se está ejecutando (han pasado aproximadamente 5 minutos :(). Lo actualizaré cuando termine.

¿Qué debo hacer para mejorar este código? (Principalmente en cuanto a rendimiento, pero cualquier otra sugerencia también es bienvenida).

Nov 28 '10 14:11 nakiya

Esto también me ha hecho tropezar antes. El cuello de botella aquí es en realidad if neighbor in closedlist.

La indeclaración es tan fácil de usar que olvidas que es una búsqueda lineal y, cuando realizas búsquedas lineales en listas, se puede sumar rápidamente. Lo que puedes hacer es convertir la lista cerrada en un setobjeto. Esto mantiene los hashes de sus elementos, por lo que el inoperador es mucho más eficiente que con las listas. Sin embargo, las listas no son elementos que se pueden dividir en hash, por lo que tendrás que cambiar tus configuraciones a tuplas en lugar de listas.

Si el orden de closedlistes crucial para el algoritmo, puede usar un conjunto para el inoperador y mantener una lista paralela para sus resultados.

Probé una implementación simple de esto, incluido el truco de tupla con nombre de aaronasterling, y funcionó en 0,2 segundos para el primer ejemplo y 2,1 segundos para el segundo, pero no he intentado verificar los resultados para el segundo más largo.

Nov 28 '2010 09:11 tkerwin

tkerwin tiene razón en que deberías usar un conjunto para lista cerrada, lo que acelera mucho las cosas, pero todavía es un poco lento para 4 camellos en cada lado. El siguiente problema es que estás permitiendo muchas soluciones que no son posibles porque estás permitiendo que fCamels retroceda y bCamels avance. Para solucionar este problema, 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)

luego obtengo la solución al problema de los 4 camellos en cada lado en aproximadamente 0,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 conjunto para lista cerrada y heapq en lugar de cola.

Aceleración adicional

Puede obtener una aceleración adicional si utiliza 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 heapq de eso) pero deberías cambiarlo a

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

Esto no tiene en cuenta la cantidad de movimientos que se han necesitado, pero está bien. Con este rompecabezas (y la detección de movimientos que mueven a los camellos en la dirección equivocada), no necesitas preocuparte por la cantidad de movimientos necesarios: o un movimiento te hace avanzar 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 cambio toma tiempo para encontrar la solución de los 12 camellos en cada caso lateral desde más de 13 segundos (incluso usando heapq, configurado para lista cerrada y los cambios para encontrar los vecinos anteriores) a 0,389 segundos. No esta mal.

Por cierto, una mejor manera de saber 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 división int) y que el índice anterior es igual a la brecha.

Nov 28 '2010 16:11 Justin Peel

Reemplazo

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 ms a 11,4 1,89 ¹ ms en la entrada [fCamel, fCamel, gap, bCamel, bCamel]. Arrojó el mismo resultado.

Obviamente, esto no ayudará con ningún problema algorítmico, pero en lo que respecta a las microoptimizaciones, no está mal.

^{1 Tuve la entrada incorrecta. Había un extra fCamelque hacía que funcionara más lento.}

Nov 28 '2010 08:11 aaronasterling