递推关联的工程实现与复杂度考量——一道小米面试题的思考

递推关联的工程实现与复杂度考量——一道小米面试题的思考

16 2019-11-19 19:38:17

## 背景
几个月前在面试小米时，三面面试官问了一个问题：如何快速计算人群的朋友圈子？

### 详细描述
A与B是朋友，C与D是朋友，E与F是朋友，F与A是朋友，那么我们可以计算出这个朋友圈子 ABEF 和圈子 CD
即输入为`(A, B) (C, D) (E, F) (F, A)`，输出为`(A, B, E, F)`和`(C, D)`
其实这个问题很容易用逻辑推断，只需要利用归并的思想，将多个小圈子逐步合并为大圈子就可以了。但是在深入分析时，会发现其中有很多的坑：
1. 合并是个复杂的过程，如第一趟遍历合并(E, F)与(F, A)，第二趟合并(A, B)与(E, F, A)...... 在极端情况下可能要经历多次循环遍历，时间复杂度为O(n^2)
![](/img/pic/2019111920203820807_png_1189_274_164971)
2. 计算集合交集也是一个复杂的过程，每次合并过程中可能需要计算集合1中每个元素在集合2中是否存在，综合第1条复杂度粗略估计整体可能达到O(n^3)
![](/img/pic/2019111920202427106_png_235_229_43875)
3. 数据量较大时矩阵计算空间复杂度很高，S(n^2)

类似的问题可以推广到很多场景，比如如何将大规模的有向边转为有向无环图，如何计算两种商品之间存在关联......

刚好，近期的工作就遇到了一个类似的问题：
描述：
- 集合中有一些点，附带其关联点信息，即(dot -> referDotId)；
- dot带有时间戳
- 修改其中一个点时，需要同时修改这个集合中的所有直接或间接关联点；
- referDot不一定都在集合中，即关联双方均在集合中的记录点比较稀疏，直接导致高时间复杂度的计算会非常得不偿失

在实际工程实现中，自然是时间复杂度、空间复杂度越低越好。

## 思路
### 方案一 集合运算
首先想到的还是利用Set计算是否存在交集，如果存在交集则将两个Set合并。

**问题1 数据结构**

dot中仅保存了referDotId信息，也就是说不是“点与点”两个实体而是“点与指向”一个实体点，那么Set的初始化就是一个大问题。
![](/img/pic/2019111920200493805_png_255_172_34663)

不能直接生成(A, B)的小集合，只能遍历后将所有有关联的点添加到Set中，那么就会产生之前分析的n重循环问题。
![](/img/pic/2019111920332347310_png_600_417_132912)

**问题2 资源使用**

即使可以直接生成小集合逐步归并，在实际工程中归并过程中不断产生后回收的中间Set对象也可能加快gc频率。
![](/img/pic/2019111920385771611_png_446_363_86546)

**问题3 有关联的点稀疏**
即便优化归并过程，每趟只要有合并动作，就需要继续进行下一趟的遍历，在数据量大的情况下的最后一趟空跑遍历所有集合也是非常浪费的。

鉴于该思路存在比较多的问题，那么只能换个方向尝试突破了。

### 方案二 排序+集合
考虑到数据集带有时间戳，我们其实可以在排序后一趟遍历中找到所有有关联的数据，随后添加到对应的一组集合中。
![](/img/pic/2019111920420565312_png_393_406_95053)

这样可以解决集合运算的部分问题，但是仍然有自身的缺点。

**问题1 关联点稀疏**
可能大多数点都找不到关联的点，导致最终创建了过多不必要的小集合。
![](/img/pic/2019111920463626013_png_411_525_152514)

**问题2 多对一关联**
在有多对一关联的情况下复杂度仍然很高，即使排序过后时间复杂度最差仍然可能是O(n^2)，当然在本场景中由于关联点稀疏这种最差情况可以忽略。
![](/img/pic/2019111920500074314_png_238_215_39521)

### 方案三 排序+划分
在数据集有序的前提下，通过标记的方式将每行数据“划分”到不同的“集合”中，无需真正的创建或合并集合，还可以通过一张映射表完成同一个划分空间中对象的对应修改。
![](/img/pic/2019111921053054615_png_800_799_366361)

整体思路就是建立两个映射表，其中划分映射表用来记录dot和其所属划分空间，属性表用于记录划分空间与带修改数据之间的关系。

- 在一次遍历过程中，就可以完成划分映射表的查找与更新、属性表的查找与更新，最终实现将更新的时间复杂度控制在O(n)，算上排序，总的时间复杂度在O(nlogn)；
- 而额外使用的空间为一个size为n的HashMap划分映射表，和一个size为m（划分数量，如果关联数据稀疏那么大致等于n）的HashMap属性映射表
	- 在我的场景中，由于要修改的属性为long类型且每个划分空间的值相同，最终直接使用要修改的属性值代替划分空间的编号，省略了属性映射表

综上，方案三不仅时间复杂度低O(nlogn)，空间复杂度低S(n)，而且实现比较简单，避免了大量的小对象创建，最终得以敲定。

## 总结
最初面试时想到的是使用集合的方式解答，而在真正遇到并经过工程实践后发现这类问题的实现方式与常规的思考模式有较大出入。

总的来说，解决递推关联比较好的流程是：
1. 排序，保证被关联的点在前
2. 建立划分表和属性修改表（或者其他形式的，根据划分id映射的内容），在一趟遍历的过程中完成操作，降低时间复杂度与空间复杂度

当时面试官给我的思路建议：

为每个朋友圈选一个领导者，将所有的“人-人”之间的关系转变为“人-领导者”的关系可以大大简化计算量。仔细想想，与标记划分思想似乎有相同也有不同。

不知道是否还有更好的方法？