如何高效地将多个不同长度的列表合并为树形字典？

Question

给定

[
  ('object-top-1','object-lvl1-1','object-lvl2-1'),
  ('object-top-2','object-lvl1-1','object-lvl2-2','object-lvl3-1')
  ('object-top-1','object-lvl1-1','object-lvl2-3'),
  ('object-top-2','object-lvl1-2','object-lvl2-4','object-lvl3-2','object-lvl4-1'),
]

等等……这里面的每一组数据（元组）长度都是不固定的

有没有什么方法可以有效地把它们转换成

{'object-top-1': {
      'object-lvl1-1': {
                   'object-lvl2-1': {},
                   'object-lvl2-3':{}
                }
       },
 'object-top-2': {
       'object-lvl1-1':{
                'object-lvl2-2': { 
                     'object-lvl3-1' : {} 
                     }
                 }
       }
       'object-lvl1-2':{
                'object-lvl2-4': {
                         'object-lvl3-2' : { 
                              'object-lvl4-1': {}
                         }
                 }
        }
 }

我已经卡在这儿很久了，真是搞不懂>.<

谢谢！

Answer 1

这样做可以实现你的需求，并且允许你添加其他值，而不是在最底层只限于空字典：

def insert_in_dictionary_tree_at_address(dictionary, address, value):
    if (len(address) == 0):
        pass
    elif (len(address) == 1):
        dictionary[address[0]] = value
    else:
        this = address[0]
        remainder = address[1:]
        if not dictionary.has_key(this):
            dictionary[this] = dict()
        insert_in_dictionary_tree_at_address(dictionary[this], remainder, value)

addresses = [
  ('object-top-1','object-lvl1-1','object-lvl2-1'),
  ('object-top-2','object-lvl1-1','object-lvl2-2','object-lvl3-1'),
  ('object-top-1','object-lvl1-1','object-lvl2-3'),
  ('object-top-2','object-lvl1-2','object-lvl2-4','object-lvl3-2','object-lvl4-1'),
]

dictionary = dict()

for address in addresses:
    insert_in_dictionary_tree_at_address(dictionary, address, dict())

def print_dictionary_tree(dictionary, prefix="    ", accumulated=""):
    next_accumulated = accumulated + prefix
    if type(dictionary) is dict and len(dictionary) > 0:
        for (key, value) in dictionary.items():
            print accumulated + str(key) + ":"
            print_dictionary_tree(value, prefix, accumulated + prefix)
    else:
        print accumulated + str(dictionary)\

print_dictionary_tree(dictionary)

输出结果：

object-top-1:
    object-lvl1-1:
        object-lvl2-1:
            {}
        object-lvl2-3:
            {}
object-top-2:
    object-lvl1-2:
        object-lvl2-4:
            object-lvl3-2:
                object-lvl4-1:
                    {}
    object-lvl1-1:
        object-lvl2-2:
            object-lvl3-1:
                {}

Answer 2

def treeify(seq):
    ret = {}
    for path in seq:
        cur = ret
        for node in path:
            cur = cur.setdefault(node, {})
    return ret

例子：

>>> pprint.pprint(treeify(L))
{'object-top-1': {'object-lvl1-1': {'object-lvl2-1': {}, 'object-lvl2-3': {}}},
 'object-top-2': {'object-lvl1-1': {'object-lvl2-2': {'object-lvl3-1': {}}},
                  'object-lvl1-2': {'object-lvl2-4': {'object-lvl3-2': {'object-lvl4-1': {}}}}}}

dict.setdefault 是一个被低估的方法。