Start optimization - directed acyclic graph

Preface

Speaking of Android Startup optimization , You may think of asynchronous loading for the first time . Put the time-consuming task into the child thread to load , When all the loading tasks are finished , Go back to the home page .

The multithreaded asynchronous loading scheme is really ok Of . But if you meet Back and forth dependence What about the relationship . For example, tasks 2 Depending on the task 1, How to solve it at this time .

The simplest solution is to put the task 1 Drop it to the main thread to load , Then start multithreading asynchronous loading .

If you encounter more complex dependencies .

Mission 3 Depending on the task 2, Mission 2 Depending on the task 1 Well , What are you going to do at this time . More complex dependencies

You can't put the task 2, Mission 3 Put it all on the main thread to load , In this way, the significance of multithreading loading is not so great .

Is there a better plan ？

The answer is yes , Using directed acyclic graphs . It's the perfect solution to dependency .

Important concepts

Directed acyclic graph （Directed Acyclic Graph, DAG） It's a kind of digraph , There is no ring in the picture . It is often used to represent the driving dependencies between events , Manage scheduling between tasks .

The vertices ： A point in the picture , Such as vertices 1, The vertices 2.

edge ： A line segment connecting two vertices is called an edge ,edge.

The degree of ： Represents how many edges are currently pointing to it .

In the diagram above , Topple 1 My penetration is 0, Because no edge points to it . Topple 2 My penetration is 1, because Topple 1 Point to Topple 2. In the same way, it can be concluded that 5 My penetration is 2, Because the roof falls 4 And vertex 3 Pointing to it

A topological sort ： Topological ordering is the process of constructing topological sequences for a directed graph . It has the following characteristics .

• Every vertex appears and only once .
• If there is one from the top A To the top B The path of , So the vertices in the sequence A Appear at the top B In front of

Because of this characteristic , Therefore, the data structure of directed acyclic graph is often used to solve the dependency relationship .

Above picture , After topological sorting , Mission 2 It must be on the list 1 after , Because of the task 2 rely on Mission 1, Mission 3 It must be on the mission 2 after , Because of the task 3 Depending on the task 2.

There are two algorithms for topological sorting , The first is the penetration meter method , The second is DFS Method . below , Let's take a look at how to achieve it .

The penetration meter method

The in degree table method is based on the in degree of a vertex to determine whether there is a dependency . If the penetration of a vertex is not 0, That means it has a pre dependency . It is also often called BFS Algorithm

Algorithmic thought

• Set up an entry scale , The degree of 0 Join the team first
• When the queue is not empty , Make a circular judgment
• Node out of the team , Add to results list among
• Reduce the number of neighbors in the node 1
• If the neighbor node's degree of penetration is 0, Join the queue
• If it turns out list Equal to the number of all nodes , Then we prove that there is no ring . otherwise , Existential ring

Instance to explain

The directed acyclic graph shown in the figure below , Using the method of entering into the table to get the topological sorting process .

First , We choose to be 0 The summit of , Here's the top 1 The degree of entry is 0, Delete vertex 1 after , The picture becomes as follows .

Now , The vertices 2 And vertex 4 All of them are 0, We can delete any vertex .（ This is why the topological ordering of graphs is not the only one ）. Here we delete the vertex 2, The picture becomes as follows ：

Now , Let's delete the vertex again 4, The picture becomes as follows ：

Select entry as 0 The summit of 3, Delete vertex 3 after , The icon is called as follows ,

Finally, the remaining vertices 5, Output vertex 5, The topological sorting process is over . The final output is ：

Here we are , The process of entering degree method of priority acyclic graph has been explained . You know .

code , We'll give it together next time .

Time complexity

set up AOE Net has n Events ,e An activity , Then the main execution of the algorithm is ：

• For each event ve Values and vl value ： The time complexity is O(n+e) ;
• according to ve Values and vl Find the key activities ： The time complexity is O(n+e) ;

therefore , The time complexity of the whole algorithm is O(n+e)

DFS Algorithm

From the entry meter method above , We can know , To get the topological ordering of directed acyclic graphs , Our key point is to find the degree of penetration 0 The summit of . Then delete all the adjacent edges of the node . Go through all the nodes . Until the entrance is 0 The queue for is empty . This method is actually BFS.

Speaking of BFS, The first time we thought of DFS. And BFS The difference is ,DFS The key to success is to find , The degree of 0 The summit of .

Summarized below , In the process of depth first search , When it reaches the exit degree of 0 At the top of , Need to go back . When the fallback is executed, the recording degree is 0 The summit of , Stack it . The reverse order of the final stack order is the topological sort sequence .

Algorithmic thought

• Perform a depth first search on the graph .
• When performing a depth first search , If a vertex can't move on , That is to say, the degree of vertex out is 0, Put this vertex on the stack .
• Finally, the reverse order of the order in the stack is the topological sort order .

Instance to explain

Again , The following figure explains DFS Algorithm process .

(1) From the top 1 Start off , Start a depth first search . In sequence 1->2->3->5.

（2） Depth first search to the top 5 when , The vertices 5 The degree of 0. Put the vertex 5 Push .

（3） Depth first search performs fallback , Back to the top 3. Now the vertex 3 The degree of departure is 0, Put the vertex 3 Push .

（4） Back to the top 2, The vertices 2 The degree of 0, The vertices 2 Push .

（5） Back to the top 1, The vertices 1 The forward position can be the vertex 4, In sequence 1->4.

（6） The vertices 4 The degree of 0, The vertices 4 Push .

（7） Back to the top 1, The vertices 1 The degree of 0, The vertices 1 Push .

（8） The reverse order of the stack is 1->4->2->3->5. This order is the result of topological sorting .

Time complexity

Time complexity analysis ： First, the time complexity of depth first search is O(V+E), And each time you just need to save the vertex that has been accessed into the array , need O(1), So the total complexity is O(V+E).

Summary

Topological ordering of directed acyclic graphs is not difficult , Medium difficulty . Usually , We usually use BFS Algorithm to solve ,DFS The algorithm is less used .

about BFS（ The penetration meter method ）, Its core idea is

1. Select an edge without input （ The degree of 0） The source vertex of （ If there are more than one, choose any one ）,
2. Delete it and its output side . Repeat the deletion of the source vertex , Until there is no such thing as 0 Until the source vertex of .
3. Final , Check the number of vertices in the graph , If there are vertices, the algorithm has no solution , Otherwise, the deletion order of vertices is the output order of topological sorting .

https://github.com/gdutxiaoxu/AnchorTask

Android Advanced development system notes 、 The latest interview review notes PDF, my GitHub

At the end of the article

Your favorite collection is my greatest encouragement ！ Welcome to follow me , Share Android dried food , communication Android technology . What's your opinion on the article , Or any technical problems , Welcome to leave a message and discuss in the comment area ！