Преобразование вложенного словаря в список

Question

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

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

Вот мои данные, в древовидной структуре:

1
-1.1
--1.1.1
---1.1.1.1
--1.1.2
-1.2
--1.2.1
--1.2.2
-1.3

Вот вложенный словарь, который я получаю в результате

{
 <Part: 1.1>:
 {
   <Part: 1.1.1>:
     {
       <Part: 1.1.1.1>: {}
     }, 
   <Part: 1.1.2>: {}
 },
 <Part: 1.2>: 
 {
   <Part: 1.2.1>: {},
   <Part: 1.2.2>: {}
 }, 
 <Part: 1.3>: {}
}

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

{<Part: 1.1>: {<Part: 1.1.1>: {<Part: 1.1.1.1>: {}}, <Part: 1.1.2>: {}}, <Part: 1.2>: {<Part: 1.2.1>: {}, <Part: 1.2.2>: {}}, <Part: 1.3>: {}}

Что я хотел бы получить:

[<Part: 1.1>, <Part: 1.1.1>, <Part: 1.1.1.1>, <Part: 1.1.2>, <Part: 1.2>, <Part: 1.2.2>, <Part: 1.2.1>, <Part: 1.3>,]

Я пробовал просто перебирать ключ в dict.items, но потом я получаю только ключи верхнего уровня (1.1, 1.2, 1.3)

Что мне нужно сделать, чтобы углубиться?

спасибо!

Answer 1

Я думаю, что рекурсия может быть вашим другом:

top = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}

 def grab_children(father):
    local_list = []
    for key, value in father.iteritems():
        local_list.append(key)
        local_list.extend(grab_children(value))
    return local_list

print grab_children(top)

Answer 2

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

top = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}

def flatten(d, ret=None):
    if ret is None:
        ret = []
    for k, v in sorted(d.items()):
        ret.append(k)
        if v:
            flatten(v, ret)
    return ret

def test():
    flatten(top)

Согласно python -m timeit -s "import flatten" "flatten.test()", этот метод использует 8.57 usecs на цикл, по сравнению с 14.4 usecs на цикл для ответа Cédrics, когда обновляется, чтобы также сортировать выходные данные.правильно (for key, value in sorted(father.items()):)

Answer 3

Начало ... э-э, я имею в виду рекурсию. Попробуйте это:

def recurse(dict):
    result = []
    for key in dict:
        result.append(key)
        result.extend(recurse(dict[key]))
    return result

Answer 4

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

def recurse(d):
    result = []
    for key in sorted(d.keys()):
        result.append(key)
        result.extend(recurse(d[key]))
    return result

Answer 5

Эта проблема не может быть решена простой итерацией по словарю. Вам нужен тип алгоритма под названием рекурсивный спуск

def getKeys(D, answer):
    if not D:
        return
    else:
        for k in D:
            answer.append(k)
            getKeys(D[k], answer)

if __name__ == "__main__":
    d = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}
    answer = []
    getKeys(d, answer)
    print answer

Это было проверено и работает

Надеюсь, это поможет