Python Конвертировать плоский список диктов в иерархическое дерево - PullRequest
Новая
       37

Python Конвертировать плоский список диктов в иерархическое дерево

0 голосов
/ 06 февраля 2019

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

lst = [
    {"id": 0, "job": "CEO", "ManagerID": 0, "name": "John Smith"},
    {"id": 1, "job": "Medical Manager", "ManagerID": 0, "name": "Medic 1"},
    {"id": 2, "job": "Medical Assist", "ManagerID": 1, "name": "Medic 2"},
    {"id": 3, "job": "ICT Manager", "ManagerID": 0, "name": "ICT 1"},
    {"id": 4, "job": "ICT Assist", "ManagerID": 3, "name": "ICT 2"},
    {"id": 5, "job": "ICT Junior", "ManagerID": 4, "name": "ICT 3"}
]

В формат, подобный 

output = [
    {"id": 0, "job": "CEO", "ManagerID": 0, "name": "John Smith", "children" : [
        { "id":1, "job": "Medical Manager", "name": "Medic 1", "children" : [
            {"id": 2, "job": "Medical Assist", "name": "Medic 2"}
            ]
        },
        {"id": 3, "job": "ICT Manager", "name": "ICT 1", "children":[
            {"id": 4, "job": "ICT Assist", "name": "ICT 2", "children" : [
                {"id": 5, "job": "ICT Junior", "name": "ICT 3"}
            ]}
        ]}
    ],
}]

Был ли один корневой узел (ManagerID = 0) любойвсе остальное ответвляется.

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

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

classes = [] #everyones id
for item in lst:
    name = item['id']
    if name not in classes:
        classes.append(name)

treenodes = {}
root_node = None

for item in lst: # Create  tree nodes
    item['children'] = []
    name = item['id']
    treenodes[name] = item
    parent = item['ManagerID']
    if parent not in classes: # parent is root node, create
        if parent not in treenodes:
            node = {}
            node['ManagerID'] = 0 #set manager to root
            node['children'] = []
            node['id'] = parent
            root_node = node
            treenodes[parent] = node

# Connect parents and children
for item in lst: # Create  tree nodes
    parent = item['ManagerID']
    parent_node = treenodes[parent]
    parent_node['children'].append(item)

output = treenodes

Любая помощь с благодарностью.

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

Вот рекурсивная версия для построения иерархии.

Рекурсивная версия 

from pprint import pprint


def to_lookup(employees):
    employee_lookup = dict()
    for employee in employees:
        if employee["id"] != employee["ManagerID"]:
            manager_id = employee["ManagerID"]
            children = employee_lookup.get(manager_id)
            if not children:
                children = employee_lookup[manager_id] = list()
            children.append(employee.copy())
        else:
            manager = employee.copy()
    return manager, employee_lookup


def build_hierarchy(manager, employee_lookup):
    employees = employee_lookup.get(manager["id"], list())
    for employee in employees:
        build_hierarchy(employee, employee_lookup)
    if employees:
        manager['children'] = employees
    return manager


employees = [
    {"id": 0, "job": "CEO", "ManagerID": 0, "name": "John Smith"},
    {"id": 1, "job": "Medical Manager", "ManagerID": 0, "name": "Medic 1"},
    {"id": 2, "job": "Medical Assist", "ManagerID": 1, "name": "Medic 2"},
    {"id": 3, "job": "ICT Manager", "ManagerID": 0, "name": "ICT 1"},
    {"id": 4, "job": "ICT Assist", "ManagerID": 3, "name": "ICT 2"},
    {"id": 5, "job": "ICT Junior", "ManagerID": 4, "name": "ICT 3"}
]

manager, employee_lookup = to_lookup(employees)
hierarchy = build_hierarchy(manager, employee_lookup)
pprint(hierarchy)

Вывод 

{'ManagerID': 0,
 'children': [{'ManagerID': 0,
               'children': [{'ManagerID': 1,
                             'id': 2,
                             'job': 'Medical Assist',
                             'name': 'Medic 2'}],
               'id': 1,
               'job': 'Medical Manager',
               'name': 'Medic 1'},
              {'ManagerID': 0,
               'children': [{'ManagerID': 3,
                             'children': [{'ManagerID': 4,
                                           'id': 5,
                                           'job': 'ICT Junior',
                                           'name': 'ICT 3'}],
                             'id': 4,
                             'job': 'ICT Assist',
                             'name': 'ICT 2'}],
               'id': 3,
               'job': 'ICT Manager',
               'name': 'ICT 1'}],
 'id': 0,
 'job': 'CEO',
 'name': 'John Smith'}

Тест производительности 

hierarchy_size = 2000000

employees = [
    {"id": 0, "ManagerID": 0},
]
for idx in range(1, hierarchy_size):
    manager_id = random.randint(0, idx - 1)
    employees.append({"id": idx, "ManagerID": manager_id})

start = datetime.datetime.now()

manager, employee_lookup = to_lookup(employees)
hierarchy = build_hierarchy(manager, employee_lookup)

print(datetime.datetime.now() - start)
0 голосов
/ 06 февраля 2019

Ваш код на самом деле работает, но вам нужно принять запись treenodes[0] (генеральный директор).Остальные пары ключ-значение в treenodes предназначены только для бухгалтерии, чтобы легко найти данного менеджера для данной записи сотрудника.

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

Вы также добавили генерального директора в свой собственный список children (идентификатор менеджера для генерального директора является их собственным идентификатором), поэтому у вас естьрекурсивная ссылка в вашем дереве.

Код, который вы нашли, не самый ясный и не самый эффективный.Я построил бы словарь из id для скопированного объекта (так что ваши исходные словари lst не изменились), затем перебрал бы эту структуру и добавил бы записи к их записи идентификатора менеджера.Я использую правило «ссылки на корневые узлы» (таким образом, идентификатор менеджера равен их собственному идентификатору): 

employees = {}
managers = set()
root_id = None
for emp in lst:
    id, mid = emp['id'], emp['ManagerID']
    # create a copy of emp, and add a "children" list
    employees[id] = {**emp, 'children': []}
    managers.add(mid)
    if id == mid:
        # the root of the tree references itself as the manager
        root_id = id

# add empty manager entries for missing manager IDs, reporting to root ID.
for id in managers - employees.keys():
    employees[id] = {
        'id': id, 'ManagerID': root_id, 'children': [],
        'job': None, 'name': None
    }

for id, emp in employees.items():
    manager = employees[emp.pop('ManagerID')]
    if id != root_id:  # don't add the root to anything
        manager['children'].append(emp)

output = employees[root_id]

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

Для вашего ввода, который выдает: 

{'id': 0, 'job': 'CEO', 'name': 'John Smith', 'children':
    [{'id': 1, 'job': 'Medical Manager', 'name': 'Medic 1', 'children':
        [{'id': 2, 'job': 'Medical Assist', 'name': 'Medic 2', 'children': []}],
     },
     {'id': 3, 'job': 'ICT Manager', 'name': 'ICT 1', 'children':
        [{'id': 4, 'job': 'ICT Assist', 'name': 'ICT 2', 'children':
            [{'id': 5, 'job': 'ICT Junior', 'name': 'ICT 3', 'children': []}]
         }]
     }]
}
...