前言
以前写算法绝大多数情况是为了考试，写出来的代码通常仅仅只是为了可用性，很多细节都没有考虑。而数据量达到一定数量集时，对算法的效率和资源开销需要重点考虑。
正文
问题来源
公司代码中有部分是关于将具有相关属性的数据放在同一个集合内，以便更好的计算。
问题简要描述
一条记录中具有三个关键非常重要属性，busiId（long），servId（long），type（int），而其中type通常为形如101十进制数，其中type的百位代表busiId的属性，而type的个位代表servId的属性，现在的需求是具有相同busiId和其属性或者具有相同servId及其属性的记录要分为一组。
原有做法
原有的做法是，用两个vector分别存下以busiId和type联合排序（busiId为主，type为辅，以后称B vector）后的结果和以servId和type联合排序（servId为主，type为辅，以后称S vector）后的结果。 初始化时，加入一条记录数据，记录其在两个排序结果数组的位置，先以在S vector中上下查找与刚加入记录是否含有相同的servId和type，一、如果没有查到有相同servId和type则，停止查询；二、如果查到，首先标记该记录，随后在B vector中上下查询是否有与刚加入的记录具有相同的busiId和type记录。查询结果与servId的方式类似。（深度优先遍历）
并查集思路
并查集 英文：Disjoint Set，即“不相交集合”
将编号分别为1…N的N个对象划分为不相交集合，
在每个集合中，选择其中某个元素代表所在集合。
常见两种操作：
合并两个集合
查找某元素属于哪个集合
并查集实现的程序代码:
int set[MAXN],rank[MAXN]; //set[i]=k表示i的父节点是k，rank[]存储树的深度。
int FindSet(int x)
{
if(set[x]!=x)
set[x]=FindSet(set[x]);
return set[x];
}//寻找x的根节点
void MakeSet(int x)
{
set[x]=x;
rank[x]=1;
}//初始化，各节点都是孤立的
void Link(int a,int b)
{ //合并时判段rank[a],rank[b]的大小，以减小树的高度
if(rank[a]>rank[b])
set[b]=a;
else if(rank[a]<rank[b])
set[a]=b;
else
{
set[a]=b;
rank[b]++;
}
}
void Union(int a,int b)
{
Link(FindSet(a),FindSet(b));
}
Find的时间复杂度取决于树的高度.在实际中,由于多次Union操作,容易导致树的高度越来越大,从而降低Find的执行效率. 实际上在并查集中,树的具体结构并不重要,只要维持树所包含的结点不变即可
思路
一开始总是受制于busi Id和serv Id分别作为key，并且想把busi Id和serv Id组成集合，然后把相同的busi或者serv id的记录放一起。
现有思路是busi Id+其type位和serv Id+其type作为key值存储在map中，而map中的value存放的是跟随人的ID（key同类型），被多少人跟随（被跟随者有效，即并查集树根有效，而非map红黑树根）rank，和该并查集内的记录ID集合（被跟随者有效，同上）。重点：在并查集Union的时候，会将记录号加在被跟随者（rank值大）上。若Union时的跟随者（rank值小）上有记录（原先是一个并查集的树根，即被跟随者），将跟随者上的记录全部交由被跟随者。
具体实现
测试
数据量小的情况，二者效率相差不大
数据量 1667982842（10亿数量集）
原有算法执行用时 大约一个半小时
尝试改进算法执行用时 大约五个小时
总结
map大量插入效率不高，并查集算法需要多次查map，并且这些部分不太好优化。
写并查集时涉及到的路径压缩，最好用递归，一方面代码的可读性非常好，另一方面，可以更直观的理解路径压缩时在回溯时完成的巧妙。
地图涂色问题好像可以将所有不接壤的国家放在同一个组，然后求排列组合。接下来抽空可以看看地图涂色问题。
结语
任重道远。
