Android 启动优化（一） - 有向无环图

待我称王封你为后i 2022-10-31 14:57 234阅读 0赞

## 前言 ##

说到 Android 启动优化，大家第一时间可能会想到异步加载。将耗时任务放到子线程加载，等到所有加载任务加载完成之后，再进入首页。

多线程异步加载方案确实是 ok 的。但如果遇到**前后依赖**的关系呢。比如任务2 依赖于任务 1，这时候要怎么解决呢。

*最简单的方案是将任务1 丢到主线程加载，然后再启动多线程异步加载。*

如果遇到更复杂的依赖呢。

任务3 依赖于任务 2， 任务 2 依赖于任务 1 呢，这时候你要怎么解决。更复杂的依赖关系呢

![format_png][]

总不能将任务 2，任务 3 都放到主线程加载吧，这样多线程加载的意义就不大了。

有没有更好的方案呢？

**答案肯定是有的，使用有向无环图。它可以完美解决先后依赖关系。**

## 重要概念 ##

**有向无环图（Directed Acyclic Graph, DAG**）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。

![format_png 1][]

**顶点**：图中的一个点，比如顶点 1，顶点 2。

**边**：连接两个顶点的线段叫做边，edge。

**入度**：代表当前有多少边指向它。

在上图中，顶掉 1 的入度是 0，因为没有任何边指向它。顶掉 2 的入度是 1， 因为 顶掉 1 指向 顶掉 2. 同理可得出 5 的入度是 2，因为顶掉 4 和顶点 3 指向它

**拓扑排序**：拓扑排序是对一个有向图构造拓扑序列的过程。它具有如下特点。

*  每个顶点出现且只出现一次。
 *  若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面

由于有这个特点，因此常常用有向无环图的数据结构用来解决依赖关系。

上图中，拓扑排序之后，任务2肯定排在任务1之后，因为任务2依赖 任务1， 任务3肯定在任务2之后，因为任务3依赖任务2。

拓扑排序一般有两种算法，第一种是入度表法，第二种是 DFS 方法。下面，让我们一起来看一下怎么实现它。

## 入度表法 ##

入度表法是根据顶点的入度来判断是否有依赖关系的。若顶点的入度不为 0，则表示它有前置依赖。它也常常被称作 BFS 算法

### 算法思想 ###

*  建立入度表，入度为 0 的节点先入队
 *  当队列不为空，进行循环判断
 *   *  节点出队，添加到结果 list 当中
     *  将该节点的邻居入度减 1
     *  若邻居节点入度为 0，加入队列
 *  若结果 list 与所有节点数量相等，则证明不存在环。否则，存在环

### 实例讲解 ###

下图所示的有向无环图，采用入度表的方法获取拓扑排序过程。

![format_png 2][]

首先，我们选择入度为 0 的顶点，这里顶点 1 的入度为 0，删除顶点 1 之后，图变成如下。

![format_png 3][]

这时候，顶点 2 和顶点 4 的入度都为 0，我们可以随便删除一个顶点。（**这也就是为什么图的拓扑排序不是唯一的原因**）。这里我们删除顶点 2，图变成如下：

![format_png 4][]

这时候，我们再删除顶点 4，图变成如下：

![format_png 5][]

选择入度为 0 的顶点 3，删除顶点 3 之后，图标称如下，

![format_png 6][]

最后剩余顶点5，输出顶点5，拓扑排序过程结束。最终的输出结果为：

![format_png 7][]

到此，优先无环图的入度法的流程已经讲解完毕。你清楚了嘛。

代码的话，下期会一起给出。

### 时间复杂度 ###

设 AOE 网有 n 个事件，e 个活动，则算法的主要执行是：

*  求每个事件的ve值和vl值：时间复杂度是O(n+e) ；
 *  根据ve值和vl值找关键活动：时间复杂度是O(n+e) ；

因此，整个算法的时间复杂度是O(n+e)

## DFS 算法 ##

从上面的入度表法，我们可以知道，要得到有向无环图的拓扑排序，我们的关键点要找到入度为 0 的顶点。然后接着删除该结点的相邻所有边。再遍历所有结点。直到入度为 0 的队列为空。这种方法其实是 BFS。

说到 BFS，我们第一时间就想到 DFS。**与 BFS 不同的是，DFS 的关键点在于找到，出度为0的顶点。**

总结如下，深度优先搜索过程中，当到达出度为0的顶点时，需要进行回退。在执行回退时记录出度为0的顶点，将其入栈。则最终出栈顺序的逆序即为拓扑排序序列。

### 算法思想 ###

*  对图执行深度优先搜索。
 *  在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈。
 *  最后得到栈中顺序的逆序即为拓扑排序顺序。

### 实例讲解 ###

同样，以下图讲解 DFS 算法的过程。

![format_png 8][]

(1) 从顶点 1 开始出发，开始执行深度优先搜索。顺序为1->2->3->5。

（2）深度优先搜索到达顶点5时，顶点5出度为0。将顶点5入栈。

（3）深度优先搜索执行回退，回退至顶点3。此时顶点3的出度为0，将顶点3入栈。

![format_png 9][]

（4）回退至顶点2，顶点2出度为0，顶点2入栈。

![format_png 10][]

（5）回退至顶点1，顶点1可以前进位置为顶点4，顺序为1->4。

（6）顶点4出度为0，顶点4入栈。

![format_png 10][]

（7）回退至顶点1，顶点1出度为0，顶点1入栈。

![format_png 11][]

（8）栈的逆序为1->4->2->3->5。此顺序为拓扑排序结果。

![format_png 12][]

### 时间复杂度 ###

时间复杂度分析：首先深度优先搜索的时间复杂度为O(V+E)，而每次只需将完成访问的顶点存入数组中，需要O(1)，因而总复杂度为O(V+E)。

## 小结 ##

有向无环图的拓扑排序其实并不难，难度中等。通常，我们一般使用 BFS 算法来解决，DFS 算法比较少用。

对于 BFS（入度表法），它的核心思想是

1.  选择一个没有输入边（入度为0）的源顶点（若有多个则任选一个），
2.  将它和它的输出边删除。重复源顶点的删除操作，直到不存在入度为0的源顶点为止。
3.  最终，检测图中的顶点个数，若还有顶点存在则算法无解，否则顶点的删除顺序就是拓扑排序的输出顺序。

https://github.com/gdutxiaoxu/AnchorTask

**如果你觉得对你有所帮助，可以关注我的微信公众号*程序员徐公*，下一篇，将输出 Android 启动优化（二） - 拓扑排序的原理以及解题思路**

## 推荐阅读 ##

[致刚入职场的你 - 程序员的成长笔记][-]

[职场上这四件事，越早知道越好][Link 1]

[拼夕夕事件反思，底层逆袭，靠拼命加班行吗][Link 2]

[面试官：手写生产者消费者模型][Link 3]

[format_png]: /images/20221024/3409b402ea13407fb0c65a21c14654ef.png
[format_png 1]: /images/20221024/9beb8fd641e64e39bc3c9aece6e82150.png
[format_png 2]: /images/20221024/8ccaa4652982404caed72c6ad91aa109.png
[format_png 3]: /images/20221024/da13d9be533847cabf6959fc0619c2a4.png
[format_png 4]: /images/20221024/878cdfb8c45a4c87b5ee2f604ad0300b.png
[format_png 5]: /images/20221024/2ed28da47886443baf8c73c1cffb773d.png
[format_png 6]: /images/20221024/f3e8b61da9ae40de8ab17e20f123a3df.png
[format_png 7]: /images/20221024/1dd74931e11a400ca26882d02c7d6a58.png
[format_png 8]: /images/20221024/ba973d93586a453295814447af391722.png
[format_png 9]: /images/20221024/8429ccc9d4dd407287e4ced65b2fb608.png
[format_png 10]: /images/20221024/4d393b0276d3419a98e346985c9c5e54.png
[format_png 11]: /images/20221024/c3a78ef4aba749e2b0229377f445e080.png
[format_png 12]: /images/20221024/c1ae79dcc37944189ec1ab1332b02478.png
[-]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95dcccdaed4da0943d1ee7cd878112e7c5c41808948a7f777192deda713c007d2af105edc&idx=2&mid=2247484044&scene=21&sn=2cdd885d352636524e86fa71c742382e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95daacdaed4bc0b7445db3db62a64894957be350bc87f9bc4b3eff2d0f425c54ed5422a8f&idx=2&mid=2247484138&scene=21&sn=5685e895e85ad1a08b30750885f78644#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95953cdaed045b1f7da333bc9efeb4b4458d3a802cbe341c3b6fc5b40dd2f564773cec783&idx=1&mid=2247484947&scene=21&sn=56ce85925bee8637b0a90938d21785ac#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95aadcdaed3bb707f2ed96306ea5462ea1e9ce20b71b6af158372d53644396998b78416e9&idx=1&mid=2247484909&scene=21&sn=e83b7b0e69fb630c4549ef9b23c79793#wechat_redirect