关于android:启动优化-有向无环图

34次阅读

共计 2203 个字符,预计需要花费 6 分钟才能阅读完成。

前言

说到 Android 启动优化,大家第一工夫可能会想到异步加载。将耗时工作放到子线程加载,等到所有加载工作加载实现之后,再进入首页。

多线程异步加载计划的确是 ok 的。但如果遇到 前后依赖 的关系呢。比方工作 2 依赖于工作 1,这时候要怎么解决呢。

最简略的计划是将工作 1 丢到主线程加载,而后再启动多线程异步加载。

如果遇到更简单的依赖呢。

工作 3 依赖于工作 2,工作 2 依赖于工作 1 呢,这时候你要怎么解决。更简单的依赖关系呢

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

有没有更好的计划呢?

答案必定是有的,应用有向无环图。它能够完满解决先后依赖关系。

重要概念

有向无环图(Directed Acyclic Graph, DAG)是有向图的一种,字面意思的了解就是图中没有环。经常被用来示意事件之间的驱动依赖关系,治理工作之间的调度。

顶点:图中的一个点,比方顶点 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 与所有节点数量相等,则证实不存在环。否则,存在环

实例解说

下图所示的有向无环图,采纳入度表的办法获取拓扑排序过程。

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

这时候,顶点 2 和顶点 4 的入度都为 0,咱们能够轻易删除一个顶点。(这也就是为什么图的拓扑排序不是惟一的起因)。这里咱们删除顶点 2,图变成如下:

这时候,咱们再删除顶点 4,图变成如下:

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

最初残余顶点 5,输入顶点 5,拓扑排序过程完结。最终的输入后果为:

到此,优先无环图的入度法的流程曾经解说结束。你分明了嘛。

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

工夫复杂度

设 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 算法的过程。

(1) 从顶点 1 开始登程,开始执行深度优先搜寻。程序为 1 ->2->3->5。

(2)深度优先搜寻达到顶点 5 时,顶点 5 出度为 0。将顶点 5 入栈。

(3)深度优先搜寻执行回退,回退至顶点 3。此时顶点 3 的出度为 0,将顶点 3 入栈。

(4)回退至顶点 2,顶点 2 出度为 0,顶点 2 入栈。

(5)回退至顶点 1,顶点 1 能够后退地位为顶点 4,程序为 1 ->4。

(6)顶点 4 出度为 0,顶点 4 入栈。

(7)回退至顶点 1,顶点 1 出度为 0,顶点 1 入栈。

(8)栈的逆序为 1 ->4->2->3->5。此程序为拓扑排序后果。

工夫复杂度

工夫复杂度剖析:首先深度优先搜寻的工夫复杂度为 O(V+E),而每次只需将实现拜访的顶点存入数组中,须要 O(1),因此总复杂度为 O(V+E)。

小结

有向无环图的拓扑排序其实并不难,难度中等。通常,咱们个别应用 BFS 算法来解决,DFS 算法比拟少用。

对于 BFS(入度表法),它的核心思想是

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

https://github.com/gdutxiaoxu…

Android 高级开发零碎进阶笔记、最新面试温习笔记 PDF,我的 GitHub

文末

您的点赞珍藏就是对我最大的激励!
欢送关注我,分享 Android 干货,交换 Android 技术。
对文章有何见解,或者有何技术问题,欢送在评论区一起留言探讨!

正文完
 0