算法 - python 数据结构转换,将线性元祖转换成字典树

Question

有一个数据表

id   fid        title
1    -1          python
2    -1          ruby
3    -1          php
4    -1          lisp
5     1          flask
6     1          django
7     1          webpy
8     2          rails
9     3          zend
10    6          dblog

这是一个栏目表,title 是栏目名称, id 是栏目 id, fid 是栏目的父id.构建一个多级栏目分类

通过 python 查询处理,会得到下面的一个元祖,

    t = (
    (1, -1, 'python'),
    (2, -1, 'ruby'),
    (3, -1, 'php'),
    (4, -1, 'lisp'),
    (5,  1, 'flask'),
    (6,  1, 'django'),
    (7,  1, 'webpy'),
    (8,  2, 'rails'),
    (9,  3, 'zend'),
    (10, 6, 'dblog')
)

希望通过 python 处理,转换成下面的 list 字典树

    l = [
    {
        'id': 1,
        'fid': -1,
        'title': 'python',
        'son': [
            {
                'id': 5,
                'fid': 1,
                'title': 'flask',
            },
            {
                'id': 6,
                'fid': 1,
                'title': 'django',
                'son': [
                    {
                        'id': 10,
                        'fid': 6,
                        'title': 'dblog',
                    },
                ]
            },
            {
                'id': 7,
                'fid': 1,
                'title': 'webpy',
            },
        ]
    },
    {
        'id': 2,
        'fid': -1,
        'title': 'ruby',
        'son': [
            {
                'id': 8,
                'fid': 2,
                'title': 'rails',
            },
        ]
    },
    {
        'id': 3,
        'fid': -1,
        'title': 'php',
        'son': [
            {
                'id': 9,
                'fid': 3,
                'title': 'zend',
            },
        ]
    },
    {
        'id': 4,
        'fid': -1,
        'title': 'lisp',
    }
]

也就是类似网站的目录, 父栏目包含子栏目.
自己写了好几个,感觉效率不够好, 求大神更 pythonic 的方法

在 stackoverflow 有人回答 大概如下：

from pprint import pprint

l = []
entries = {}

for id, fid, title in t:
     entries[id] = entry = {'id': id, 'fid': fid, 'title': title}
     if fid == -1:
          l.append(entry)
     else:
          parent = entries[fid]
          parent.setdefault('son', []).append(entry)

pprint(l)

Answer 1

Let me ask a question first. Is the pid of the queried tuple increasing?
In other words, parent = entries[fid] must be able to get the value?

---

StackOverFlow’s master’s answer is already very efficient. . Although it is wrong...if your data is out of order, the output result of the code you posted will be incorrect.
Although I don’t know what pythonic you are talking about... If the purpose is not to understand, I wrote one...
In any case, it is not recommended to use this coding habit. Clarity and readability are the common characteristics of all programming. If you want to have fun, you can go to codeforece to see the answers to the problems solved by various experts.

---

e, l = {d[0]:{'id': d[0], 'fid': d[1], 'title': d[2]} for d in t}, []
for i in e: l.append(e[i]) if e[i]['fid'] == -1 else e[e[i]['fid']].setdefault('son', []).append(e[i])
print l

The first line formats the data first and stores it in e
The second line traverses e and adds it to the l array if e['fid'] == -1. Otherwise, find the corresponding e[e[fid]] and add its child node.

Because l.append(e[i]) is an address copy, the data change in e directly affects the data of l (because they all point to the same address~) For specific details, please refer to my other question. The answer to http://segmentfault.com/q/1010000000397465#a-1020000000397966

---

The following is the normal version of the code above:

l = []
entities= {d[0]:{'id': d[0], 'fid': d[1], 'title': d[2]} for d in t}
for e_id in entities:
  entitiy = entities[e_id]
  fid = entitiy['fid']
  if fid == -1:
    l.append(entitiy)
  else:
    entities[fid].setdefault('son',[]).append(entitiy)
print l

Answer 2

The answer on Stackoverflow requires that the parent element in t appears before the child element. If it cannot be guaranteed, you can use the following method:

from itertools import groupby
from operator import itemgetter as get
from pprint import pprint

# group by fid
tmp = dict([(k, list(rows)) for k, rows in groupby(sorted(t, key=get(1)), get(1))])

def map_fun(row):
  item = dict(zip(('id', 'fid', 'title'), row))
  if row[0] in tmp:
    item['son'] = find_children(row[0])
  return item;

def find_children(parent):
    return map(map_fun, tmp[parent])

pprint(find_children(-1))

Regarding pythonic, you can try this
>>> import this

PS: I am not a great god.

Answer 3

entries[id] = entry = {'id': id, 'fid': fid, 'title': title}
Will cause memory to explode