Tree Structure in Python

在开发一个编译工具的时候,遇到了一个特殊的需求,要把一组已知绝对路径的文件,排列成一个树形结构。开发的工具是python,所以当然不能满足于代码能够工作就行了,一定要高效和优(zhuang)雅(bi)。结果发现动态语言的确在不停的颠覆CPPer的世界观。

借助python的defaultdict结构可以构造出一个一句话的复杂树形结构,这个结构虽然不好理解,但是可以神奇的动态增长。

1
2
3
4
5
6
7
8
9
10
from collections import defaultdict
Tree = lambda: defaultdict(Tree)
t = Tree()
t[1][2][3] = 4
t[1][3][3] = 5
t[1][2]['test'] = 6

上面代码可以得到如下图所示的结构

这么牛x的东西当然不是偶然出现的,而且有在计算机科学里还有一个不明觉厉的名字: autovivification。 这种最早出现在Perl中的语言特性,现在已经被引入到Python, PHP, Ruby等动态语言中。下面的例子中无处不体现着python独特的语言特性,非常值得学习。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import defaultdict
Tree = lambda: defaultdict(Tree)
t = Tree()
def add(t, keys):
for key in keys:
t = t[key]
def autovivify(levels=1, final=dict):
'''Returns a nested defaultdict with a set number of levels and defined final structure.
'''
return (defaultdict(final) if levels < 2 else
defaultdict(lambda: autovivify(levels - 1, final)))
words = autovivify(5, int)
words["sam"][2012][5][25]["hello"] += 1
words["sue"][2012][5][24]["today"] += 1
def convert_nested_dd(dd):
'''Converts a nested defaultdict back into a native dictionary.
'''
return {k:convert_nested_dd(v) for k,v in dd.items()} if isinstance(dd, defaultdict) else dd