Android Startup Optimization (1) - Directed acyclic graph

My CSDN blog: blog.csdn.net/gdutxiaoxu my nuggets: juejin. Cn/user / 220747… Github: github.com/gdutxiaoxu/ wechat official account: Programmer Xu Gong (Stormjun94)

Android Startup Optimization (1) – Directed acyclic graph

Android startup optimization (2) – Topology sort principle and solution ideas

Android startup optimization (III) – AnchorTask open source now

Android Startup Optimization (4) – AnchorTask is implemented

Android Startup Optimization (5) – AnchorTask version 1.0.0 is now available

Android Startup Optimization (VI) – In-depth understanding of layout optimization

This series of articles, from 0 to 1, will explain how DAG directed acyclic graphs are implemented and how to launch optimized applications on Android.

Recommendation: There are a lot of articles talking about startup optimization, always talk about topology structure, this article from data structure to algorithm, to design are clear to everyone, open source projects also have very strong reference significance.

preface

When it comes to Android startup optimization, the first thing that comes to mind is asynchronous loading. Load time-consuming tasks in sub-threads and enter the home page after all loading tasks are completed.

Multithreaded asynchronous loading schemes are indeed OK. But what if you have a dependency relationship. Let’s say task 2 depends on task 1.

The simplest solution is to dump task 1 onto the main thread for loading, and then start multi-threaded asynchronous loading.

What about more complex dependencies.

Task 3 depends on task 2, task 2 depends on task 1, how do you solve that? More complex dependencies

You can’t load tasks 2 and 3 into the main thread, so there’s not much point in multi-threaded loading.

Is there a better plan?

The answer is definitely yes. Use directed acyclic graphs. It is the perfect way to resolve sequential dependencies.

Important concepts

Directed Acyclic Graph (DAG) is a type of Directed Graph, which literally means there are no rings in a Graph. Often used to represent driver dependencies between events and manage scheduling between tasks.

Vertex: A point in a graph, such as vertex 1, vertex 2.

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

Entry: Represents how many edges currently point to it.

In the figure above, the top off of 1 is 0 because there are no edges pointing to it. The entry of top 2 is 1, because top 1 points to top 2. Similarly, the entry of 5 is 2, because top 4 and vertex 3 point to it

Topological sort: Topological sort is the process of constructing a topological sequence of a directed graph. It has the following characteristics.

Each vertex occurs only once.
If there is A path from vertex A to vertex B, then vertex A precedes vertex B in the sequence

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

In the figure above, after topological sorting, task 2 must come after task 1 because task 2 depends on task 1, and task 3 must come after task 2 because task 3 depends on task 2.

Topological sorting generally has two algorithms, the first is the entry table method, the second is DFS method. Let’s take a look at how to implement it.

The table method

Entry table method is based on the entry degree of vertices to judge whether there are dependencies. If a vertex has a non-zero degree of entry, it has a predependency. It is also often referred to as the BFS algorithm

Algorithm thought

Set up the entry degree table, and the node whose entry degree is 0 joins the queue first
When the queue is not empty, the loop checks
- The node exits the queue and is added to the result list
- Reduce the neighbor entry of this node by 1
- If the neighbor node’s inbound degree is 0, the neighbor node is added to the queue
If the resulting list is equal to all nodes, then there is no ring. Otherwise, there are rings

Instance to explain

The directed acyclic graph shown below uses the method of entry table to obtain the topological sorting process.

First, we select a vertex with zero degree of entry, where vertex 1 has zero degree of entry. After deleting vertex 1, the graph becomes the following.

At this point, vertex 2 and vertex 4 both have zero degree of entry, so we can delete any vertex we want. This is why topological ordering of graphs is not the only reason. Here we delete vertex 2 and the graph looks like this:

At this point, we delete vertex 4 again, and the graph becomes as follows:

After selecting vertex 3 with an entry degree of 0 and deleting vertex 3, the graph is labeled as follows:

Finally, the remaining vertex 5, output vertex 5, the topological sorting process ends. The final output is:

At this point, priority acyclic graph entry method of the process has been explained. You get the idea.

I’ll show you the code in the next video.

Time complexity

Suppose there are N events and E activities in AOE network, then the main execution of the algorithm is as follows:

Calculate the VE value and VL value of each event: time complexity is O(n+ E);
Find key activities according to ve and VL values: time complexity is O(n+ E);

So the time of the whole algorithm is order n+e.

DFS algorithm

From the entry table method above, we can know that to get topological ordering of directed acyclic graphs, our key point is to find vertices with 0 entry. Then delete all adjacent edges of the node. Let’s go through all the nodes again. Until the queue of zero entry is empty. This method is actually BFS.

When we think of BFS, we immediately think of DFS. Unlike BFS, the key point of DFS is to find vertices that have an out degree of zero.

In the process of depth-first search, when a vertex with an outdegree of 0 is reached, a rollback is required. Vertices with degree 0 are recorded and pushed to the stack during the rollback. The final reverse of the stack removal order is the topological sort sequence.