Generador de Python vs función de callback

Tengo una clase que resuelve un problema de cobertura exacto usando un algoritmo recursivo y de seguimiento. Originalmente, implementé la clase con una función de callback que pasé al objeto durante la inicialización. Esta callback se invoca cada vez que se encuentra una solución. Al observar la implementación del mismo problema por parte de otra persona, vi que estaban usando declaraciones de rendimiento para pasar una solución, en otras palabras, su código era un generador de Python. Pensé que esta era una idea interesante, así que hice una nueva versión de mi clase para usar los rendimientos. Luego realicé pruebas de comparación entre las dos versiones y, para mi sorpresa, encontré que la versión del generador era 5 veces más lenta que la versión de callback. Tenga en cuenta que, excepto para cambiar el rendimiento de una callback, el código es idéntico.

¿Que esta pasando aqui? Estoy especulando con eso, porque un generador necesita guardar información de estado antes de ceder y luego restaurar ese estado cuando se reinicia en la próxima llamada, es esta operación de guardar / restaurar lo que hace que la versión del generador se ejecute mucho más lentamente. Si este es el caso, ¿cuánta información de estado debe guardar y restaurar el generador?

¿Alguna idea de los expertos en python?

–Editado 7:40 PDT

Aquí está el código del solucionador que usa el rendimiento. Reemplace el primer rendimiento a continuación con una llamada a la función de callback y cambie el siguiente bucle con el segundo rendimiento a solo una llamada recursiva para resolver la versión original de este código.

def solve(self): for tp in self.pieces: if self.inuse[tp.name]: continue self.inuse[tp.name] = True while tp.next_orientation() is not None: if tp.insert_piece(): self.n_trials += 1 self.pieces_in += 1 self.free_cells -= tp.size if self.pieces_in == len(self.pieces) or self.free_cells == 0: self.solutions += 1 self.haveSolution = True yield True self.haveSolution = False else: self.table.next_base_square() for tf in self.solve(): yield tf tp.remove_piece() self.pieces_in -= 1 self.table.set_base_square(tp.base_square) self.free_cells += tp.size self.inuse[tp.name] = False tp.reset_orientation() 

El bucle de correo que invoca al solucionador (después de la inicialización, por supuesto) es

  start_time = time.time() for tf in s.solve(): printit(s) end_time = time.time() delta_time = end_time - start_time 

En la versión de callback, el bucle se ha ido con una sola llamada para resolver.

Lo que quise decir en mi comentario, (“el rendimiento de una función recursiva parece que requiere más para que los bucles pasen los resultados a la persona que llama”) es esta línea:

  for tf in self.solve(): yield tf 

Estas líneas recursivamente recorren los resultados de las etapas de recursión más profundas. Eso significa que un solo resultado se itera en cada nivel de la recursión, lo que resulta en un montón de bucles innecesarios.

Déjame ilustrar con este ejemplo:

 n = 0 def rekurse(z): global n if z: yield z for x in rekurse(z-1): n += 1 yield x print list(rekurse(10)) print n 

Como puede ver, simplemente cuenta hacia abajo desde 10, por lo que esperaría un número lineal de iteraciones. Sin embargo, lo que puede ver es que n crece de forma cuadrada: recurse(10) repite en 9 elementos, recurse(9) en 8 elementos, etc.

Cuantos más elementos tenga, más tiempo pasará Python en estas líneas simples. Las devoluciones de llamada evitan completamente ese problema, por lo que sospecho que ese es el problema con su código.

Una implementación optimizada de PEP 380 podría solucionar este problema (consulte este párrafo ). Mientras tanto, no creo que sea una buena idea ceder de las funciones recursivas (al menos si recurren profundamente), simplemente no funcionan bien juntos.