J'ai créé une fonction qui lit des listes de paires d'identité (par exemple [("A", "B"), ("B", "C"), ("C", "D "), ...] et séquence les identifiants du début à la fin, y compris les branchesLa fonction récursive Python dépasse la limite de récursivité. Comment puis-je convertir à l'itération
Chaque liste d'ID ordonnée est conservée dans une classe appelée Alignement et cette fonction utilise la récursivité pour gérer les branches en créant un nouveau départ à partir de l'alignement. J'ai trouvé que pour certaines entrées, il est possible d'atteindre la limite de récursion maximale définie par Python, je sais que je pourrais simplement augmenter cette limite en utilisant sys.setrecursionlimit (), mais comme je ne sais pas combien de combinaisons de branches sont possibles, j'aimerais éviter cette tactique:
J'ai lu plusieurs articles sur la conversion des fonctions récursives aux fonctions itératives, mais je n'ai pas été en mesure de déterminer la meilleure façon de gérer cette fonction particulière, car la récursion a lieu au milieu de la fonction et peut être exponentielle.
Pourrait-vous proposer des suggestions?
Merci, Code Brian
est affiché ci-dessous:
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: Je tiens à souligner que les ID fournis sont juste un petit échantillon j'ai utilisé pour tester cet algorithme. En réalité, les séquences d'ID peuvent être longues de plusieurs milliers avec de nombreuses branches et branches de branches.
RÉSOLUTION: Merci à Andrew Cooke. La nouvelle méthode semble être beaucoup plus simple et beaucoup plus facile sur la pile d'appels. J'ai fait quelques ajustements mineurs à son code pour mieux répondre à mes besoins. J'ai inclus la solution complétée ci-dessous:
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")])
RÉSUMÉ DES CHANGEMENTS: liens permutés et have_successors pour créer la liste du début à la fin ajouté if line in known: known.remove(line) se développer afin de ne conserver que la série complète variable ligne modifiée de chaîne énumérer afin de gérer plusieurs caractères dans un seul ID.
MISE À JOUR: Je viens de découvrir la raison pour laquelle j'avais un problème avec tout cela en premier lieu est de faire des références circulaires dans la liste des ID que je fournis. Maintenant que la référence circulaire est fixe, l'une ou l'autre méthode fonctionne comme prévu. - Merci encore pour votre aide.
Je pense que vous voulez dire des ramifications. –
Est-ce votre code actuel? Il lance IndexError à 'i = len (alignements)' ... 'buildAlignments (alignements [i]' avant même qu'il ne commence à être récursif.) –
@Erin - merci de m'avoir signalé cela, j'ai changé les chutes en branches comme il est une meilleure description – Brian