Рекурсивная функция Python превышает предел рекурсии. Как я могу преобразовать это в итерацию

Question

Я создал функцию, которая читает списки пар идентификаторов (то есть [("A","B"),("B","C"),("C","D"),...] и последовательности). идентификаторы от начала до конца, включая любые ветви.

Каждый список упорядоченных идентификаторов содержится в классе, называемом выравниванием, и эта функция использует рекурсию для обработки ветвей путем создания нового выравнивания, начиная с идентификатора, при котором ветвь отделяется от основного списка.

Я обнаружил, что при определенных входных данных можно достичь максимального предела рекурсии, установленного Python. Я знаю, что мог бы просто увеличить этот лимит с помощью sys.setrecursionlimit(), но, поскольку я не знаю, сколько возможных комбинаций ветвей, я бы хотел избежать этой тактики.

Я читал несколько статей о преобразовании рекурсивных функций в итеративные функции, но я не смог определить лучший способ обработки этой конкретной функции, потому что рекурсия происходит в середине функции и может быть экспоненциальной.

Кто-нибудь из вас может предложить какие-либо предложения?

Спасибо Брайан

Код размещен ниже:

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

РЕДАКТИРОВАТЬ: я должен указать, что предоставленные идентификаторы являются лишь небольшой выборкой, которую я использовал для тестирования этого алгоритма. В действительности, последовательности идентификаторов могут быть длиной в несколько тысяч с множеством ответвлений и ответвлений.

РЕШЕНИЕ: Спасибо Эндрю Кук. Новый метод выглядит намного проще и намного проще в стеке вызовов. Я внес небольшие изменения в его код, чтобы лучше соответствовать моим целям. Я включил законченное решение ниже:

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

РЕЗЮМЕ ИЗМЕНЕНИЙ: поменялись местами ссылки и добавлены have_successors для создания списка от начала до конца if line in known: known.remove(line) развернуть, чтобы сохранить только строку измененной строки переменной из строки в список, чтобы обрабатывать несколько символов в одном идентификаторе.

ОБНОВЛЕНИЕ: Таким образом, я только что обнаружил причину, по которой у меня возникла проблема со всем этим, в первую очередь, это круговые ссылки в списке предоставленных мне идентификаторов. Теперь, когда круговая ссылка зафиксирована, любой из методов работает как положено. - Еще раз спасибо за вашу помощь.

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, что является просто вопросом опыта / практики, и "аккуратностью". я не ожидаю, что вы узнаете о дефолте - это придет со временем.

но то, что вы должны сейчас сделать, это написать чистый, простой код:

• Я думаю, что у вас есть комментарии о более ранних версиях кода. упоминается "максимальная длина", но я не вижу никаких расчетов длины. поэтому либо комментарий устарел (в таком случае, почему он там есть), либо он должен быть более четким (почему эти вещи имеют максимальную длину?). в общем, вы должны комментировать как можно меньше, потому что в противном случае он устареет. но в то же время вы должны использовать комментарии, где неясно, какие "идеи" стоят за кодом. код должен говорить сам за себя, поэтому не говорите "я добавляю два числа здесь", но говорите "фрагменты здесь должны быть максимальной длины, потому что...", если есть какая-то "скрытая" логика.

• будьте осторожны с фотографиями, которые вы используете. по какой-то причине ваш код начинается с известных терминалов. Таким образом, вы строите вещи с конца обратно к началу. Зачем? это странный взгляд на проблему. Разве не было бы яснее начать с точек, которые находятся в начале, но не в конце? а затем использовать "startIDs" для их роста? таким образом, вы "идете вперед". это может показаться мелочью, но это делает чтение кода запутанным.

• Используйте правильные инструменты для работы. вы не использовали startID, так почему вы строите карту? все, что вам было нужно, это набор. возможно, вы не знали о сетах, в этом случае все в порядке (но вы знаете сейчас!:o). но в остальном это также сбивает с толку - кто-то, читающий ваш код, ожидает, что вы будете делать что-то по какой-то причине. поэтому, когда вы делаете больше, чем необходимо, они задаются вопросом, почему.

• избегайте считать вещи, когда вам не нужно. у тебя есть i а также index а также count, они все нужны? Эти виды счетчиков - самый простой способ иметь ошибки, потому что они могут иметь маленькие глупые логические ошибки. и они делают код неясным. является if i < count - 1: на самом деле говорят "это последняя ветка"? если так, было бы гораздо приятнее написать if branch == branches [-1]: потому что ясно, о чем ты думаешь.

• Аналогично с циклическим выравниванием в main. с помощью 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где он возвращает новый пакет. trampoline() Затем команда сохраняет старый пакет и начинает работать с новым, вызывая next() на этом, начиная это... и т. д. и т. д.

когда у генератора "кончается чем заняться", он поднимает StopIteration, поэтому, когда мы достигаем точки, где выражение больше не может расти, мы видим это исключение в trampoline(), в этот момент мы возвращаемся к последнему "старому" пакету (хранится в нашем stack) и позвоните next() снова на этом. этот пакет перезапускается с того места, где он был (сразу после yield) и продолжается, вероятно, делая еще один цикл в whileдо тех пор, пока не достигнет yield снова (или выбегает и поднимает StopIteration).

поэтому, в конце концов, код делает то же самое, как если бы yield там не было! единственное отличие состоит в том, что мы продолжаем делать эти связки и возвращать их. что кажется бессмысленным. за исключением того, что мы больше не используем стек! поскольку пакет возвращается, стек не "израсходован"! вот почему нам нужно управлять собственным стеком (список stack) - иначе нет способа узнать, каким был предыдущий звонок.

хорошо, хорошо, я не ожидаю, что вы поймете это вообще. да, это безумие теперь вам нужно уйти и гуглить для "генераторов питона". и написать свой собственный код, чтобы проверить его. но, надеюсь, это указывает путь.

---

о, я тоже думал прошлой ночью и я подозреваю, что если вы исчерпали стек, это было на самом деле потому, что у вас есть петли, а не потому, что цепочки такие длинные. Вы рассматривали петли? A->B, B->C, C->A, ....