APP
1.背景
1.1 在日常開發時經常會在??Application??的??onCreate()??方法中對三方SDK，或者自己封裝的SDK進行初始化。
class Application{
...
onCreate(){
initSDKA();
initSDKB();
initSDKC();
....
}
...
}
上面是通常寫法，這里總結了幾個信息點
- 初始化耗時。整體都在主線程一條線程初始化。部分機型無法充分利用cpu資源。
- SDK依賴。部分sdk 存在順序依賴關系。比如SDKB用到了SDKA 中的服務。這時必須保證順序。
- 代碼開閉原則。對修改封閉，對擴展開放。如要刪除或者添加一個SDK，需增加或者刪除對應方法。又或者開發人員可以隨意刪除，抽取某個initSDK 方法中的部分內容，造成功能的不確定性。
2. 方案解決
2.1 針對以上總結的信息點?？梢杂貌⑿卸嗑€程解決耗時問題。引用指向關系解決SDK依賴問題。封裝初始化SDK代碼成TASK任務解決代碼混亂問題。在保證以上條件都成立的情況下，圖論中DAG（有向無環圖）是剛好符合以上解決問題的數據結構。
如何根據用戶指定的依賴關系生產有向無環圖呢？
- 為了確保遍歷的入口唯一，默認在圖中加入根節點Root
- 由于可能存在不依賴于任何其他SDK的SDK，而且不止一個。我們把不依賴于任何sdk 的TASK節點掛載在Root下。
- 把有依賴關系的Task掛在對應依賴的Task后繼幾點后面
假如有如下依賴關系
- A,C 不依賴任何其他節點
- B依賴于A。E依賴于A，C。D依賴于B，C。
根據上述依賴關系，會生成如下圖的有向圖。
生成圖后，把后繼節點為空的節點指向尾節點，如 圖3->圖4。保證了圖的完整以及出口的唯一，遍歷時作為圖遍歷結束的最后一個節點
TaskNode節點
public abstract class TaskNode implements Runnable,ITask {
public short inDegree; // 當前 Task 在有向圖中的入度，用于判斷圖中是否有環
HashSet<TaskNode> nextList = new HashSet<>(); // 后繼節點
List<TaskNode> depended = new ArrayList<>();
OnTaskResult onTaskResult;
}
根據依賴關系生成圖
/**
* 生成有向圖
*/
private void generateGraph() {
for (TaskNode taskNode : taskNodes) {
// 如果該節點沒有任何依賴關系，則直接掛載在 root 下
if (getPreNodes(taskNode) == null || getPreNodes(taskNode).size() == 0) {
root.nextList.add(taskNode);
// 計算入度
taskNode.inDegree = 1;
} else {
short inDegree = 0;
List<TaskNode> taskNodeList = getPreNodes(taskNode);
// 如果該節點有依賴關系，則掛載在依賴的Task 之后
for (TaskNode preNode : taskNodeList) {
preNode.nextList.add(taskNode);
inDegree++;
}
// 計算入度
taskNode.inDegree = inDegree;
}
}
}
/**
* 獲取該節點依賴的節點的集合
* @param taskNode
* @return
*/
private List<TaskNode> getPreNodes(TaskNode taskNode) {
if (taskNode.depended.isEmpty()) {
return null;
}
List<TaskNode> taskNodeList = new ArrayList<>();
for (TaskNode clazz : taskNode.depended) {
taskNodeList.add(node);
}
return taskNodeList;
}
2.2 判斷圖中是否有環
2.2.1拓補排序的特性
如果圖中有環，Task之間存在循環依賴，會造成遍歷無法結束，尾節點無法添加。
在圖論中，拓撲排序是一個有向無環圖（DAG）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：
- 每個頂點出現且只出現一次。
- 若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現在頂點 B 的前面。
那也就意味著如果一個圖的拓補排序無法輸出所有頂點，那么這個圖中必定存在環，或者循環依賴。
2.2.2拓補排序的算法實現
- 從 DAG 圖中選擇一個 沒有前驅（即入度為0）的頂點并輸出，同時把該節點的后繼節點都減1，然后查找后繼節點中入度為0的節點，找到后加入臨時棧中（臨時棧中都是入度為0的節點）。上圖4中只有一個入度0的節點，就是Root節點
- 從臨時棧中拿到入度為0的節點彈出元素加入拓補排序集合中，然后重復步驟1。直到臨時棧中元素為空。拓補排序結束
代碼如下
/**
* 判斷圖中是否有環
*
*/
private void isThereARing() {
// 臨時棧，用于存放入度為0的節點
Stack<TaskNode> nodeStack = new Stack<>();
nodeStack.push(root);
// 存放拓補排序排序的集合
ArrayList<TaskNode> topologicalSort = new ArrayList<>();
while (!nodeStack.isEmpty()) {
TaskNode taskNode = nodeStack.pop();
topologicalSort.add(taskNode);
if (taskNode.nextList.size() != 0) {
for (TaskNode nextNode : taskNode.nextList) {
// 當前節點指向下一節點，將下一節點的入度 減1
nextNode.inDegree--;
// 如果下一節點的入度是0，將入度為 0 的節點入棧，用于下一次遍歷
if (nextNode.inDegree == 0) {
nodeStack.push(nextNode);
}
}
}
}
// 拋出異常中斷程序異常信息中提示 存在環的相關 Task
if (taskCount != topologicalSort.size()) {
taskNodes.removeAll(topologicalSort);
StringBuilder builder = new StringBuilder();
builder.append(" [");
for (TaskNode taskNode : taskNodes) {
builder.append(taskNode.getClass().getSimpleName());
builder.append(",");
}
builder.append(" ]");
throw new RuntimeException("there is a ring among" + builder.toString());
}
}
上圖是一個有向無環圖，輸出的拖布排序序列為[1,2,4,3,5],如果 3，5 是循環依賴關系，則排序只會輸出[1,2,4]就結束了。圖中的元素無法全部遍歷完成。
2.3 多線程遍歷圖
因為牽扯子線程初始化任務，必須確保在跳轉第一個業務頁面時，所有的Task都初始化完成了。也就是說從遍歷開始到結束，主線程是不可以跳轉到閃屏頁面的，而且部分初始化會在主線程進行。阻塞主線程就成了必需要做的事。
多線程遍歷
runTask(root); // 開始遍歷
waitMain();
private void runTask(final TaskNode taskNode) {
// 只有入度為0的節點才能開始運行
if (taskNode.backupInDegree.get() == 0) {
// 當前Task運行完成回掉
taskNode.setOnTaskResult(new OnTaskResult() {
@Override
public void OnTaskEnd(HashSet<TaskNode> nextList) {
// 遍歷結束條件，尾節點遍歷完成
if (taskNode instanceof TaskTail) {
return;
}
// 尋找下一節點，嘗試運行。
for (TaskNode nextNode : taskNode.nextList) {
// 遞減入度，直到為0的時候，該Task 才可以執行
nextNode.backupInDegree.decrementAndGet();
runTask(nextNode);
}
}
});
if (taskNode.isMainThread()) {
// 主線程任務放入消費隊列，由主線程消費
try {
// 阻塞隊列，會阻塞主線程
// blockingQueueMain = new ArrayBlockingQueue<TaskNode>();
blockingQueueMain.put(taskNode);
} catch (InterruptedException e) {
e.printStackTrace();
}
} else {
// 子線程任務直接由線程池運行
executorService.execute(taskNode);
}
}
}
主線程阻塞代碼
/**
* 遍歷開始時，主線程阻塞，直到尾節點遍歷結束。
*/
private void waitMain() {
long startTime = SystemClock.uptimeMillis();
// 超時邏輯，防止主線程阻塞超時
while (SystemClock.uptimeMillis() - startTime < timeOut) {
try {
TaskNode taskNode = blockingQueueMain.poll(timeOut, TimeUnit.MILLISECONDS);
taskNode.run();
// 到達尾節點直接跳出循環，放開主線程
if (taskNode instanceof TaskTail) {
break;
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
遍歷完成，整個初始化結束。
3.時間對比
- 不使用圖組織關系，串行執行時。使用上文提到的A,B,C,D,E， 每個Task模擬耗時2s，依賴關系保持不變。
class Application{
...
onCreate(){
new TaskA().run();
new TaskC().run();
new TaskB().run();
new TaskD().run();
new TaskE().run();
....
}
...
}
- 使用圖組織依賴關系，開啟兩個子線程進行遍歷。
TasksManager.getInstance(this).addTask(new TaskA())
.addTask(new TaskB())
.addTask(new TaskC())
.addTask(new TaskC())
.addTask(new TaskE()).start();
時間對比
機型遍歷方式 | 不使用圖（主線程，時間ms） | 使用圖（2個線程，時間ms） | 優化比例 |
小米Mix2（10.0系統） | 10000左右 | 6020～6040 | 39.6% 左右 |
魅族mx6（7.0系統） | 10000左右 | 6020～6050 | 39.5%左右 |
初始化時間在實際項目中也會因為依賴關系不同造成圖的關系的不同。最差情況下，所有的Task會形成一個鏈表。最好的情況下所有的Task之間沒有依賴關系。所以優化的百分比時間還要根據具體的業務場景來進行比對總結。
后續接入公司項目后，項目中有大概30+ sdk數量，初始化速度提升大概在30%-40%之間
4.總結
- 使用圖的數據結構組織SDK之間的關系，更加合理有效。
- 多線程遍歷圖。在保證所有SDK在使用前初始化完成，SDK的初始化效率更高。
- 將SDK的初始化封裝抽象成Task的形式。插拔更加便利，代碼整體性更高，管理SDK更加便利。
- 后期可以通過添加xml配置文件的形式配置進程，線程，依賴關系的方式配置Task信息。統一管理
本文摘自 ：https://blog.51cto.com/u
