Перемещение и изменение древовидного списка структуры 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.

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 

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

selected = dict(zip(selected, selected)) 

Answer 2

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

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

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

(О, и вы даже не нужно держать детей в определенном порядке Имея список dicts, которые все содержат ключ «идентификатор» неестественна,? Это имеет смысл иметь Dict, где ключи - это идентификаторы, а значения - без знака «id».)

Answer 3

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

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)