Cloud's Blog

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