擅长:python、mysql、java
<p>前面的所有解决方案都递归地构建了大量列表,然后将它们扩展回越来越大的列表,直到得到最终答案。虽然它可以工作,但从性能的角度来看,它并不是最优的,因为它创建了许多您真正不需要的列表,并且涉及到将相同的项多次扩展到其父列表中。有些解决方案还忘了按键排序。</p>
<pre><code>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)
</code></pre>
<p>根据<code>python -m timeit -s "import flatten" "flatten.test()"</code>,该方法在更新以正确排序输出时,每个循环使用8.57个usecs,而对于Cédrics应答,每个循环使用14.4个usecs(<code>for key, value in sorted(father.items()):</code>)</p>