将嵌套字典转换为列表

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

我说的是递归，不是梦境的开始。试试这个：

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

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 微秒，而Cédrics的答案在更新后（也对输出进行了正确排序 for key, value in sorted(father.items()):）每次循环需要 14.4 微秒。

Answer 3

我觉得递归可以成为你的好帮手：

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)