Python递归函数超出了递归限制.如何将其转换为迭代

Question

我创建了一个读取ID对列表的函数(即[("A","B"),("B","C"),("C","D"),...]和序列ID从头到尾包括任何分支机构.

每个有序ID列表都保存在一个名为Alignment的类中,该函数使用递归来处理分支,方法是从分支从主列表中拆分的ID开始创建一个新的对齐.

我发现使用某些输入可以达到Python设置的最大递归限制.我知道我可以使用sys.setrecursionlimit()来增加这个限制,但由于我不知道有多少分支组合是可能的,所以我想避免这种策略.

我一直在阅读几篇关于将递归函数转换为迭代函数的文章,但是我无法确定处理这个特定函数的最佳方法,因为递归发生在函数的中间并且可以是指数函数.

你们有没有提出任何建议？

谢谢,Brian

代码发布如下:

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

编辑:我应该指出,提供的ID只是我用于测试此算法的一小部分样本.实际上,ID的序列可能是几千长,其中有许多分支和分支.

决议:感谢Andrew Cooke.在调用堆栈上,新方法似乎更简单,更容易.我确实对他的代码做了一些小的调整,以更好地适应我的目的.我在下面列出了完整的解决方案:

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")])

更改摘要:交换链接和has_successors从头到尾创建列表添加if line in known: known.remove(line)到展开,以便仅保留从字符串到列表的完整系列更改的行变量,以便处理单个ID中的多个字符.

更新:所以我刚刚发现我遇到问题的原因首先是我提供的ID列表中的循环引用.现在循环引用已修复,任一方法都可以按预期工作.- 再次感谢你的帮助.

Answer 1

你的代码是混乱的混乱.我不知道应该详细说明它应该做些什么.如果你更小心(更整洁,更清晰),那么你可能还会发现重构更容易.

无论如何,这可能会做你想要的事情:

from collections import defaultdict

def expand(line, links, known):
    print 'expand'
    known.append(line)
    for child in links[line[-1]]:
        newline = line + child
        yield expand(newline, links, known)

def trampoline(generator):
    stack = [generator]
    while stack:
        try:
            generator = stack.pop()
            print 'next'
            child = next(generator)
            stack.append(generator)
            stack.append(child)
        except StopIteration:
            pass

def main(pairs):
    have_successors = set()
    links = defaultdict(lambda: set())
    for (start, end) in pairs:
        have_successors.add(start)
        links[end].add(start)
    known = []
    for node in set(links.keys()):
        if node not in have_successors:
            trampoline(expand(node, links, 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")])

我使用python2.7 -与早期版本中,你可能需要更换next(foo)同foo.__next__()或相似.

写清洁代码

首先,我也是一名自学成才的程序员,最初是一名学者(天文学家),所以你对此表示同情.如果你继续前进,你可以赶上并通过许多"教学"程序员.它并不像你想象的那么难......

第二,使用像"defaultdict"这样的"技巧",这只是经验/实践的问题,而是"整洁".我不指望你知道defaultdict - 这将随着时间的推移而来.

但你现在应该做的是编写干净简单的代码:

• 我认为您有关于早期版本代码的评论.一个提到"最大长度"但我没有看到任何长度计算.所以评论是过时的(在这种情况下为什么它在那里)或者它需要更清楚(为什么那些最大长度的东西？).一般来说,你应该尽可能少地评论,否则它会过时.但与此同时,你应该使用评论,而不清楚代码背后的"想法"是什么.代码应该说明一点,所以不要说"我在这里添加两个数字",但是如果存在一些"隐藏"逻辑,请说"这里的片段必须是最大长度,因为......".

• 小心你使用的图片.由于某种原因,您的代码从已知终端开始.所以你要从头到尾开始构建东西.为什么？这是一种看待问题的奇怪方式.从开始时的分数开始,但不是最终的分数是不是更清楚？然后使用"startIDs"来增长它们？那样你就是"向前走".它可能看起来像一个小东西,但它使阅读代码混乱.

• 使用正确的工具来完成工作.你没有使用startID,那你为什么要建一张地图？所有你需要的东西都有一套.也许你不知道套装,在这种情况下OK(但你现在做!:o).但除此之外,这也令人困惑 - 有人在阅读你的代码时希望你出于某种原因做事.所以,当你做的不仅仅是必要时,他们想知道为什么.

• 当你不需要时,避免计算东西.你必须i和index和count.他们都需要吗？这些类型的计数器是最容易出错的方法,因为它们可能有很少的逻辑错误.他们使代码不清楚.是if i < count - 1:真说:"这是最后的分支"？如果是这样的话,写起来会好得多,if branch == branches [-1]:因为这清楚你在想什么.

• 类似于在主要中循环对齐.使用i只是复杂的事情.你正在处理每个对齐,所以就说for each alignment in alignments.如果由于对齐正在改变而产生错误,请制作一份不变的副本:for each alignment in list(alignments).

• 如果不需要,请避免特殊情况.在buildAlignment中,您可以在开始时对特殊情况进行测试.但它真的需要吗？没有它你会得到相同的结果吗？通常,当您简单地编写代码时,事实证明您不需要特殊情况.在我的代码中,我不需要测试是否有一个"链接",因为它在所有这些情况下都可以正常工作.这样可以减少代码,减少需要担心的事情,减少错误的机会.

不仅仅是所有这些 - 你必须要过于整洁和有条不紊.你有很多想法,但不是尝试一半,然后跳到另一个,写下来并逐一完成它们.否则你最终得到一堆乱七八糟的代码,你不明白.起初感觉就像你在浪费时间,但是你开始意识到这样你就会变得更快,因为你花费的时间更少......

在发电机上

[我稍微修改了代码以分开newline并添加print到几个地方.]

首先,你运行了代码吗？它正在做你想要的那种事情吗？你能看出它与之前的相关联吗？我expand和你的相似buildAlignment(我希望).

如果你运行它(最新版本),你会看到:

: python2.7 recurse.py
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
expand
next
next
...

这可能会给出正在发生的事情的线索."技巧"是yield语句 - python编译器会看到它,并且不是创建普通函数,而是生成一个生成器.

发电机是一件非常奇怪的事情.它基本上是你的功能(在这种情况下expand),"捆绑",以便它可以分阶段运行.运行完成next()并且每次yield到达时功能再次停止.

所以trampoline通过这个奇怪的捆绑.它打来电话next().这是启动功能的"神奇" 功能.所以当next被调用时,函数开始运行,直到它到达yield,返回一个新的 bundle.该trampoline()命令然后保存旧的包,并开始工作的新的,要求next()上,开始吧...等等等等.

当发电机"用完了要做的事情"时,它就会升起StopIteration.所以当我们到达表达式不再增长的点时,我们就会看到异常trampoline().在那一点上,我们返回到最后一个"旧"包(存储在我们的stack)中并next()再次调用它.这个包从它所在的地方重新开始(紧接着yield)并继续,可能在另一个循环中while,直到它yield再次点击(或用完并加注StopIteration).

所以最后,代码就像yield没有那样!唯一的区别是我们不断制作这些捆绑包并将它们归还.这似乎毫无意义.除了我们不再使用堆栈!因为返回了包,堆栈没有"用完"!这就是为什么我们需要管理自己的堆栈(列表stack) - 否则无法知道之前的调用是什么.

好的,好的,我不希望你理解这一点.是的,这有点疯狂.现在你需要离开并谷歌为"python发电机".并编写一些自己的代码来测试它.但希望这指明了方向.

哦,我昨晚也在想.而且我怀疑,如果你正在耗尽堆栈,那实际上是因为你有循环,而不是因为链条太长了.你考虑过循环吗？A-> B,B-> C,C-> A,....