关于数据组装我有话要说

这个问题肯定不止我一个人遇到,也肯定不止我一个人想到;

我是菜鸟,觉得我写的水的话请轻喷^_^;

作为一个java程序猿,每天的工作就是和数据库打交道,把数据查出来拼装成前端需要的样子,并返回给前端;

如果只是简单的单表,或者是一对一的连表查询都还好说(不建议连表查询,之后会说),很多时候碰到一对多的表,或者是树形结构.就不能简单的用sql搞定,就需要查出来在内存中进行拼装.本篇文章就是想讲述下我对数据拼装的心得;

先说结论:

总体思想是先把一个集合转换成id->object的map,在遍历一个list,然后从map中找到关联类并组装

在我早些时候写一对多的数据拼装时是这样写的,现在也会见到很多同事这样写;

public Parents combinationWithLoop(List<Parent> parents,List<Sons> sons){
	for(Parent parent: parents){
		for(Son son: sons){
			if(Object.equals(son.getPid(), parent.getId()){
				parent.addson(son);
				break;
			}
		}
	}
	return parent;
}
           

嵌套循环.时间复杂度parent.size*sons.size;

而且对于每次sons的遍历只有一次是有实际数据操作的,其他情况就只是路过而已;做了无意义的事情;

接下来改写下:

public Parents combinationWithMap(List<Parent> parents,List<Sons> sons){
   Map<String,Parent> parentMap = parents.stream().collect(Parent::getId,t->t);
   		for(Son son:Sons){
   			parentMap.get(son.getPid()).addSon(son);
   		}
   return parents;
}
           

时间复杂度变成parents.size+sons.size;(忽略map的常数级时间复杂度)

虽然空间复杂度会增加(类本身没有复制,增加的只是map的指针数据)

简单的改写.效率提升一个数量级;

同样树形结构也是可以做一样的操作;

public Node buildTree(List<Node> nodes){
		Map<String,Node> nodeMap = nodes.stream().collect(Collectors.toMap(Node::getId,t->t);
		Node rootNode = null;
		for(Node node : nodes){
			Node pNode = nodeMap.get(node.getPid);
			if(pNode == null){
				rootNode = node; 
			} else{
				pNode.addSon(node);
			}
		}
		return rootNode;
	}
           

这样避免了递归,多重嵌套循环什么的问题.

总结

正如开题所说,把时间复杂度O(n^2)变成O(2n);

这个思想不仅仅只是后台有用,前端一样也可以使用,js的Object获取指定key的时间复杂度应该也是O(1) (我记得有查过);

同样的…作为树形结构的上下节点查找.使用遍历方法是很低效的.完全可以转换成两个Map;

nodeMap = id->node;

sonsMap = pid->List<node>;

这样你知道任意一个节点都可以很方便的找到

父节点(nodeMap.get(node.getPid())),

兄弟节点(sonsMap.get(node.getPid())),

子节点(sonsMap.get(node.getId()));