He creado una función que lee listas de pares de ID (es decir, [("A", "B"), ("B", "C"), ("C", "D" "), ...] y secuencia las ID desde el principio hasta el final, incluidas las ramas.La función recursiva de Python excede el límite de recursión. Cómo puedo convertirlo a la iteración
Cada lista de ID ordenados se almacena en una clase llamada Alineación y esta función usa la recursividad para manejar las ramas creando una nueva alineación comenzando en el ID en el que la rama se divide de la lista principal.
He encontrado que con ciertas entradas es posible alcanzar el límite máximo de recursión establecido por Python. Sé que podría aumentar este límite usando sys.setrecursionlimit (), pero como no sé cuántas combinaciones de ramas son posibles, me gustaría evitar esta táctica.
He estado leyendo varios artículos sobre la conversión de funciones recursivas a funciones iterativos, pero no han sido capaces de determinar la mejor manera de manejar esta función en particular debido a que la recursividad se lleva a cabo en medio de la función y puede ser exponencial.
¿Alguno de ustedes podría ofrecer alguna sugerencia?
Gracias, Brian
Código se publica a continuación:
def buildAlignments(alignment, alignmentList, endIDs):
while alignment.start in endIDs:
#If endID only has one preceding ID: add preceding ID to alignment
if len(endIDs[alignment.start]) == 1:
alignment.add(endIDs[alignment.start][0])
else:
#List to hold all branches that end at spanEnd
branches = []
for each in endIDs[alignment.start]:
#New alignment for each branch
al = Alignment(each)
#Recursively process each new alignment
buildAlignments(al, branches, endIDs)
branches.append(al)
count = len(branches)
i = 0
index = 0
#Loop through branches by length
for branch in branches:
if i < count - 1:
#Create copy of original alignment and add branch to alignment
al = Alignment(alignment)
al += branch #branches[index]
alignmentList.append(al)
i += 1
#Add single branch to existing original alignment
else: alignment += branch #branches[index]
index += 1
def main():
IDs = [("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")]
#Gather all startIDs with corresponding endIDs and vice versa
startIDs = {}
endIDs = {}
for pair in IDs:
if not pair[0] in startIDs: startIDs[pair[0]] = []
startIDs[pair[0]].append(pair[1])
if not pair[1] in endIDs: endIDs[pair[1]] = []
endIDs[pair[1]].append(pair[0])
#Create Alignment objects from any endID that does not start another pair (i.e. final ID in sequence)
alignments = [Alignment(end) for end in endIDs if not end in startIDs]
#Build build sequences in each original Alignment
i = len(alignments)
while i:
buildAlignments(alignments[i-1], alignments, endIDs)
i -= 1
EDIT: Debo señalar que las identificaciones proporcionadas son sólo una pequeña muestra de lo acostumbrado para probar este algoritmo. En realidad, las secuencias de identificaciones pueden ser de varios miles de largo con muchas ramas y ramas fuera de las ramas.
RESOLUCIÓN: Gracias a Andrew Cooke. El nuevo método parece ser mucho más simple y mucho más fácil en la pila de llamadas. Hice algunos ajustes menores a su código para adaptarme mejor a mis propósitos. He incluido la solución completa a continuación:
from collections import defaultdict
def expand(line, have_successors, known):
#print line
known.append(line)
for child in have_successors[line[-1]]:
newline = line + [child]
if line in known: known.remove(line)
yield expand(newline, have_successors, known)
def trampoline(generator):
stack = [generator]
while stack:
try:
generator = stack.pop()
child = next(generator)
stack.append(generator)
stack.append(child)
except StopIteration:
pass
def main(pairs):
have_successors = defaultdict(lambda: set())
links = set()
for (start, end) in pairs:
links.add(end)
have_successors[start].add(end)
known = []
for node in set(have_successors.keys()):
if node not in links:
trampoline(expand([node], have_successors, known))
for line in known:
print line
if __name__ == '__main__':
main([("L", "G"), ("A", "B"), ("B", "I"), ("B", "H"), ("B", "C"), ("F", "G"), ("D", "E"), ("D", "J"), ("E", "L"), ("C", "D"), ("E", "F"), ("J", "K")])
RESUMEN DE CAMBIOS: enlaces intercambiados y have_successors para crear la lista de principio a fin añade if line in known: known.remove(line) para expandir el fin de conservar únicamente la variable de línea modificada serie completa de cuerdas a la lista para manejar múltiples caracteres en una sola ID.
ACTUALIZACIÓN: Por lo que acaba de descubrir la razón por la que estaba teniendo un problema con todo esto, en primer lugar es hacer a referencias circulares en la lista de identificadores que se proporcionó. Ahora que la referencia circular es fija, cualquiera de los métodos funciona como se espera. - Gracias, de nuevo, por toda su ayuda.
Creo que quieres decir retoños. –
¿Es este tu código real? Lanza IndexError en 'i = len (alineaciones)' ... 'buildAlignments (alineaciones [i]' incluso antes de que empiece a recursarse. –
@Erin - gracias por señalarlo. He cambiado las rampas a las ramas, ya que una mejor descripción. – Brian