算法之生成评论树
本节内容
- 问题由来
- 递归实现
- 高效实现
- 总结
1. 问题由来
项目中用到了展示用户多级评论的功能，但是在数据库中存储的每行数据之前是通过parent_id来标示他们之间的关系。
从数据库中取出这一行行的数据，需要转换成类似于json数据格式的类型（其实就是通过parent_id将评论关联起来生成一颗一颗的评论树），再将数据传递给前端进行渲染。
[
{"id":"4","pid":"1","name":"大家电"},
{"id":"5","pid":"1","name":"生活电器"},
{"id":"1","pid":"0","name":"家用电器"},
{"id":"2","pid":"0","name":"服饰"},
{"id":"3","pid":"0","name":"化妆"},
{"id":"7","pid":"4","name":"空调"},
{"id":"8","pid":"4","name":"冰箱"},
{"id":"9","pid":"4","name":"洗衣机"},
{"id":"10","pid":"4","name":"热水器"},
{"id":"11","pid":"3","name":"面部护理"},
{"id":"12","pid":"3","name":"口腔护理"},
{"id":"13","pid":"2","name":"男装"},
{"id":"14","pid":"2","name":"女装"},
{"id":"15","pid":"7","name":"海尔空调"},
{"id":"16","pid":"7","name":"美的空调"},
{"id":"19","pid":"5","name":"加湿器"},
{"id":"20","pid":"5","name":"电熨斗"}
]
类似这样的数据要转换成下面这种的数据：
[
{"id":"1","pid":"0","name":"家用电器", "chindren":[
{"id":"4","pid":"1","name":"大家电", "chindren":[
{"id":"7","pid":"4","name":"空调", "chindren":[
{"id":"15","pid":"7","name":"海尔空调"},
{"id":"16","pid":"7","name":"美的空调"}
]},
{"id":"8","pid":"4","name":"冰箱"},
{"id":"9","pid":"4","name":"洗衣机"},
{"id":"10","pid":"4","name":"热水器"}
]},
{"id":"5","pid":"1","name":"生活电器","chindren":[
{"id":"19","pid":"5","name":"加湿器"},
{"id":"20","pid":"5","name":"电熨斗"}
]}
]},
{"id":"2","pid":"0","name":"服饰","chindren":[
{"id":"13","pid":"2","name":"男装"},
{"id":"14","pid":"2","name":"女装"}
]},
{"id":"3","pid":"0","name":"化妆","chindren":[
{"id":"11","pid":"3","name":"面部护理"},
{"id":"12","pid":"3","name":"口腔护理"}
]}
]
实现这种需求有两种方式，下面就这两种方式进行一下分析。
2. 递归实现
class Node:
@staticmethod
def digui(rst,row):
for i in rst: # 如果在第一层能找到匹配的值，则直接放进去
if row["parent_id"]==i["id"]:
row["children"]=[]
i["children"].append(row)
else: # 否则，递归寻找该行数据的子孙
Node.digui(i["children"],row)
@staticmethod
def build_tree(comment_list):
rst=[]
for row in comment_list:
if row["parent_id"]==None: # 如果没有父亲，则直接入列表
row["children"]=[] # 先把该行数据添加一个children键对应一个空列表（之后可能有数据要插入进来）
rst.append(row) # 将根插入到rst列表的最外层
else: # 否则进入递归函数
Node.digui(rst,row)
return rst
comment_list=models.Comment.objects.filter(news_id=new_id)
print(Node.build_tree(comment_list))
这样虽然能实现效果，但是存在了一些问题：
- 使用了递归，使得程序的执行效率大大降低。
- 并且这还存在一个缺陷，那就是父亲行必须在儿子行前面，否则儿子数据将会丢失。（当然，可以通过数据库查询出评论数据来之后对评论时间进行排序，但是这样做又会消耗时间在对数据进行排序上，对数据库也是一个压力）
那么有没有其他更高效的解决这个问题的办法呢？
答案是有的，就在下一节。
3. 高效实现
在说明高效实现之前，先补充两个知识点：
- python中的字典和列表都是引用数据类型，里面就是指针指向的内存地址，当修改实际的内存中的值时，所有指向该地址的指针对应的值都被改变。
- python中的dict数据类型是键值对的形式，内部实现是通过hash实现的，所以通过key获取值的速度比列表获取值的速度快很多。
接下来就是代码实现了：
comment_list=models.Comment.objects.filter(news_id=new_id)
ret=[] # 最终拿到的数据
comment_list_dict={} # 构建的中间字典
for row in comment_list: # 通过查到的数据中的id作为key，每一行数据作为value生成一个字典
row.update({"children":[]}) # 构建一个键children对应一个空列表
comment_list_dict[row["id"]]=row # 将id作为键，当前行作为值存到该字典中
for item in comment_list: # 遍历一遍取到的数据列表
parrent_row=comment_list_dict.get(item["parent_id"]) # 拿到当前行对应的父亲的地址
if not parrent_row: # 如果父亲是None，则直接进入ret中
ret.append(item)
else: # 否则，将这行append到父亲的children中
parrent_row["children"].append(item) # 重点在这一行，用到了上面提到的第一个知识点
print(ret)
上面的重点那行无法理解可以先看下面的解释的小例子：
In [1]: a=[1,2,3]
In [2]: b=[4,5,6]
In [3]: a.append(b)
In [4]: a
Out[4]: [1, 2, 3, [4, 5, 6]]
In [5]: b.append(7)
In [6]: b
Out[6]: [4, 5, 6, 7]
In [7]: a
Out[7]: [1, 2, 3, [4, 5, 6, 7]]
数组a中引用了数组b，当数组b的值发生改变的时候，数组a中的对应的数组b中的值也相应的发生了改变，因为a中的引用和b指向了同一块内存地址。
使用这种方式只需要对取到的数据列表进行两次遍历就能实现，第一次遍历是为了创建dict，通过dict的key获取值的时间复杂度基本是个常量，不会随着数据量的增长而增长O(1)。第二次遍历数据列表用到了列表和字典的引用知识。
这种方式解决了上面递归实现中的两个问题：
- 没有使用递归实现，效率将会大大提升。
- 父亲评论和子评论的顺序之间没有前后关系的约束。
4. 总结
平时在写代码过程中，需要思考性能带来的问题，当涉及到频繁调用以及大量数据处理时，更是要考虑性能造成的瓶颈。善于思考使用更少的资源实现相同效果将能大大提升程序的执行效率。