Python - сопоставление зависимостей заданий в древовидной структуре

Question

У меня есть список вакансий с зависимостями и там статус. Я хочу пройти каждую работу и наметить там зависимости как дерево. Конец дерева будет, когда оба родительских зависимостей являются статусом выполненного. Тогда нет необходимости далеко ходить. Я не уверен, следует ли мне использовать рекурсию, или если это действительно единственная возможность. Есть ли встроенные инструменты отображения или структуры данных, которые могут мне помочь? Я буду повторяться, возможно, около 10 000 рабочих мест.

псевдопользователей Код

def map_depends(job_depends): 
    for job in job_depends: 
     if job.status = done: 
      job_tree_map.append(job.name) 
     else: 
      map_depends(job.get('dependencies')) 

def main():  
    for job in batch: 
       if job.get('dependencies'): 
        map_depends(job.get('dependencies')) 

Визуальное описание того, что я говорю.

  -> job_depends1.status = done 
main_job            -> job_depends3 = running -> job_depends6 = done 
     -> job_depends2 = running......job_depends2 -> jon_depends4 = done 
                 -> job_depends5 = done 

Answer 1

Если дерево достаточно глубоко, используя рекурсивный алгоритм может вызвать переполнение стека, потому что CPython по умолчанию имеет предел 1000 вложенных вызовов. Вы можете установить собственное предельное значение с sys.setrecursionlimit, но обычно это не рекомендуется. Итак, в вашем случае может быть лучше переписать обход дерева в итеративном режиме.

Например, вы можете написать функцию, как то, что для фильтрации дерева и обхода (не в псевдокоде):

def walkjob(job): 
    if job is None: 
     return [] 

    result = [job, ] 
    cursor = 0 

    while cursor < len(result): 
     job = result[cursor] 
     result.extend(list(
      filter(lambda j: j.done, 
      job.children))) 
     cursor += 1 

    return result 

Вот его использования в РЕПЛ:

>>> from bunch import Bunch 
>>> job = Bunch(value=1, done=True, children=[ 
...   Bunch(value=2, done=True, children=[]), 
...   Bunch(value=3, done=True, children=[ 
...    Bunch(value=4, done=False, children=[]), 
...    Bunch(value=5, done=True, children=[])])]) 
... 
>>> map(lambda j: (j.value, j.done), walkjob(job)) 
[(1, True), (2, True), (3, True), (5, True)] 

Возможно смежные вопросы:

• What is the maximum recursion depth in Python, and how to increase it?

Answer 2

Деревья - это, естественно, рекурсивные структуры данных, однако все, что можно записать рекурсивно, можно сделать итеративно, используя явные стеки.

К сожалению, вы не получаете «урона от» до CPython 3. [34], что делает рекурсивные генераторы непрактичными в более ранних версиях.

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

Для стека многие разработчики Python будут использовать append и pop в списке или acollections.deque. Я мог бы использовать http://stromberg.dnsalias.org/~strombrg/linked-list/ ради абстракции, хотя это часто медленнее в CPython.