Обход и изменение древовидного списка структуры dict

Question

У меня есть структура, которая выглядит следующим образом:

[ {'id': 4, 'children': None},
  {'id': 2, 'children': 
    [ {'id': 1, 'children':
        [ {'id': 6, 'children': None},
          {'id': 5, 'children': None} ]
      },
      {'id': 7, 'children':
        [ {'id': 3, 'children': None} ]
      }
    ]
  }
]

У меня также есть список выбранных идентификаторов, [4, 5, 6, 7].Я хочу просмотреть список и для каждого объекта в списке добавить ключ selected со значением 1, если он выбран, и 0, если это не так.

В настоящее время я являюсьделать это рекурсивно с помощью этой функции:

def mark_selected(tree, selected):
    for obj in tree:
        obj['selected'] = 1 if obj['id'] in selected else 0
        if obj['children'] is not None:
            obj['children'] = mark_selected(obj['children'], selected)
    return tree

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

Может кто-нибудь придумать для этого более изящное решение?

Answer 1

Рекурсия совершенно элегантна. Понимания списка не применяются, когда вы изменяете структуру на месте, а не производите новую последовательность. Что касается генераторов, вы можете написать DFS или BFS traverser.

def dfs(nodes):
    if nodes is not None:
        for node in nodes:
            yield node
            for child in dfs(node['children']):
                yield child

for node in dfs(tree):
    if node['id'] in selected:
        node['selected'] = true

Если список идентификаторов для выбора большой, было бы более целесообразно преобразовать его в dict с идентификаторами в качестве ключей, что ускорит поиск (node['id'] in selected).

selected = dict(zip(selected, selected))

Answer 2

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

def mark_selected(tree, selected):
    def recur(tree):
        for obj in tree:
                obj['selected'] = 1 if obj['id'] in selected else 0
                if obj['children'] is not None:
                    recur(obj['children'])
    recur(tree)

Answer 3

Поскольку вы работаете, изменяя входной объект, и поскольку объекты имеют ссылочную семантику в Python, вам не нужно возвращать значение или использовать возвращаемое значение в рекурсивном шаге.Кроме того, если вы можете заменить записи «None» для детей на «[]» (еще лучше использовать кортежи по всему списку, а не по спискам), тогда вы можете упростить логику - тогда вам вообще не нужен базовый случай,потому что вы можете вернуться к «пустому дереву», и оно просто запустит цикл for для всех нулевых элементов, то есть ничего не делать - то, что вам нужно.

И FFS, почему вы не используетеВстроенный в Python логический тип?

def mark_selected(tree, selected):
    for obj in tree:
        obj['selected'] = obj['id'] in selected
        mark_selected(obj['children'], selected)

(О, и вам даже нужно держать детей в определенном порядке? Наличие списка слов, в которых есть ключ 'id', является неестественным;имеет больше смысла иметь слово, где ключи - это идентификаторы, а значения - это слова без идентификатора.)