精华内容
下载资源
问答
  • 鲍亮|编辑:卢凯瑞1 名词解释DAG,全称:Directed Acyclic Graph,中文:无环图入度:有向图中某点作为图中边的终点的次数之和出度:对于有向图来说,顶点的出边条数即为该顶点的出度2 调度系统中的无环图...

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    点击上方蓝字关注DolphinScheduler(海豚调度)

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    |作者:鲍亮

    |编辑:卢凯瑞

    1 名词解释

    DAG,全称:Directed Acyclic Graph,中文:有向无环图

    入度:有向图中某点作为图中边的终点的次数之和

    出度:对于有向图来说,顶点的出边条数即为该顶点的出度

    2 调度系统中的有向无环图

    数据调度系统中,多个任务之间的依赖关系,用图可以表示,如下图所示,每个顶点表示一个任务,箭头方向表示任务的执行顺序。任何顶点都无法经过边回到该顶点,则该图就是无环图,即为有向无环图(DAG图)。

    b443b5a95f6c269b286cd2775d888e4a.png

    图一

    那么在有向图中,如果有环的存在,如图示:

    68e1d311288483fabc7e5afeb7d4b683.png

    图二

    在有环的情况下,任务3的执行需要任务5完成,而5的执行又需要3,4依次执行完成,这样就会造成死循环,此调度任务永远无法成功执行。所以在调度系统中,对于无环的检测就非常重要。

    3 无环检测

    在调度系统中,检查图是否有环,分两种场景:1. 编辑图的过程中每一步操作都需要对其做无环检测;2. 对已经存在的图进行拓扑排序,检测是否有环。

    3.1 编辑时检测

    对于新创建的图来说,每增加一条边,都需要检测,这条边是否导致环的存在 思路:如图1到图2, 如果要加一条5到3的边,就从3开始遍历后续顶点,如果能回到顶点5的话就证明新加的边导致环的产生;如果不能回到5,证明新添加的边不会导致有环。检测代码如下:

    /**

    * 判断增加边(fromVertex --> toVertex)是否合法,需要判断是否符合无环的约束

    *

    * @param fromVertex     起点

    * @param toVertex       终点

    * @param createVertex 是否创建结点

    * @return

    */

    private boolean isLegalAddEdge(Vertex fromVertex, Vertex toVertex, boolean isCreate){

    if (fromVertex.equals(toVertex)) {

    logger.error("edge fromVertex({}) can't equals toVertex({})",fromVertex,toVertex);

    return false;

    }

    if (!isCreate) {

    if (!hasVertex(fromVertex) || !hasVertex(toVertex)){

    logger.error("edge fromVertex({}) or toVertex({}) is not in vertices map",fromVertex,toVertex);

    return false;

    }

    }

    Queue queue = new LinkedList<>();

    queue.add(toVertex);

    int verticesCount = getVerticesCount();

    //如果没有找到fromVertex, 表示无环;

    while (!queue.isEmpty() && verticesCount > 0) {

    verticesCount -= 1;

    Vertex key = queue.poll();

    // 遍历后续顶点

    for (Vertex subsequentVertex : getSubsequentNodes(key)) {

    if (subsequentVertex.equals(fromVertex)) {

    return false;

    }

    queue.add(subsequentVertex);

    }

    }

    return true;

    }

    3.2 拓扑排序检测

    有向图的拓扑排序,思路如下:

    遍历图中所有的顶点,将入度为0的顶点入队列(如果多个顶点入度为0,取顶点顺序可能不一样,所以此处排序结果可能是多个)。

    从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    一直执行第2步,直到队列为空。

    如果无法遍历完所有的结点,则意味着当前的图不是无环图。不存在拓扑排序。

    例如图1 入度出度:

    顶点

    入度

    出度

    顶点1

    0

    2

    顶点2

    1

    1

    顶点3

    1

    1

    顶点4

    2

    1

    顶点5

    1

    0

    拓扑排序流程如下:

    7f3795e399931f583c0b65c6ecec4700.png

    图三

    java实现如下:

    /**

    * 判断是否有环及拓扑排序结果

    *

    * 有向无环图(DAG)才有拓扑(topological)排序

    * 广度优先遍历的主要做法:

    *    1、遍历图中所有的顶点,将入度为0的顶点入队列。

    *    2、从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    *    3、一直执行第2步,直到队列为空。

    * 如果无法遍历完所有的结点,则意味着当前的图不是有向无环图。不存在拓扑排序。

    *

    *

    * @return key返回的是状态, 如果成功(无环)为true, 失败则有环, value为拓扑排序结果(可能是其中一种)

    */

    private Map.Entry> topologicalSortImpl() {

    //入度为0的结点队列

    Queue zeroIndegreeVertexQueue = new LinkedList<>();

    //保存结果

    List topoResultList = new ArrayList<>();

    //保存入度不为0的结点

    Map notZeroIndegreeVertexMap = new HashMap<>();

    //扫描所有的顶点,将入度为0的顶点入队列

    for (Map.Entry vertices : verticesMap.entrySet()) {

    Vertex vertex = vertices.getKey();

    int inDegree = getIndegree(vertex);

    if (inDegree == 0) {

    zeroIndegreeVertexQueue.add(vertex);

    topoResultList.add(vertex);

    } else {

    notZeroIndegreeVertexMap.put(vertex, inDegree);

    }

    }

    //扫描完后,没有入度为0的结点,说明有环,直接返回

    if(zeroIndegreeVertexQueue.isEmpty()){

    return new AbstractMap.SimpleEntry(false, topoResultList);

    }

    //采用topology算法, 删除入度为0的结点和它的关联边

    while (!zeroIndegreeVertexQueue.isEmpty()) {

    Vertex v = zeroIndegreeVertexQueue.poll();

    //得到相邻结点

    Set subsequentNodes = getSubsequentNodes(v);

    for (Vertex subsequentVertex : subsequentNodes) {

    Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

    if(--degree == 0){

    topoResultList.add(subsequentVertex);

    zeroIndegreeVertexQueue.add(subsequentVertex);

    notZeroIndegreeVertexMap.remove(subsequentVertex);

    }else{

    notZeroIndegreeVertexMap.put(subsequentVertex, degree);

    }

    }

    }

    //notZeroIndegreeVertexMap如果为空, 表示没有环

    AbstractMap.SimpleEntry resultMap = new AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == 0 , topoResultList);

    return resultMap;

    }

    }

    输出每个顶点的同时还要删除以它为起点的边。如果图有V个顶点,E条边,则一般该算法的时间复杂度为O(V+E)。这里实现的算法最终key返回的是状态, 如果成功(无环)为true, 失败则有环, 无环时value为拓扑排序结果(可能是其中一种)。

    展开全文
  • 因为有向图中一个点经过两种路线到达另一个点未必形成,因此无环图未必能转化成树,但任何有向树均为无环图。 DAG 的拓扑排序 拓扑排序是一个可以把所有的顶点排序的算法,它排序的依据是深度优先搜索...

    当我们学习数据结构的时候,总是觉得很枯燥,而当我们解决实际问题的时候,又往往因为对数据结构了解的匮乏而束手无策。从问题中来,到问题中去,在某一点上的深入思考并且不断的实践积累,或许是个笨办法,但笨办法总是比没办法好一些。本文是老码农对DAG的随手笔记,积累成文。

    什么是DAG?

    DAG,Directed Acyclic Graph即「有向无环图」。

    从计算机的视角来看,DAG 是一个图,图与数组、队列、链表等一样,都是是一种数据结构。图是由顶点和连接顶点的边构成的数据结构,在计算机科学中,图是最灵活的数据结构之一,很多问题都可以使用图模型进行建模求解。例如,人与人之间的社交网络、分析计算机网络的拓扑结构已确定两台计算机是否可以通信、物流系统中找到两个地点之间的最短路径等等。

    回顾一下图的相关概念:

    • 顶点:图中的一个点

    • 边:连接两个顶点的线段

    • 相邻:一个边的两头顶点成为相邻

    • 度数:由一个顶点出发,有几条边就称该顶点有几度

    • 路径:通过边来连接,按顺序的从一个顶点到另一个顶点中间经过的顶点集合

    • 简单路径:没有重复顶点的路径

    • 环:至少含有一条边,并且起点和终点都是同一个顶点的路径

    • 简单环:不含有重复顶点和边的环

    • 无环图:是一种不包含环的图

    • 连通图:如果一个图中,从任意顶点均存在一条路径可以到达另一个任意顶点,该图称为连通图

    • 稀疏图:图中每个顶点的度数都不较小

    • 稠密图:图中每个顶点的度数都较大

    如果图中的边可以是有方向的,边的方向性表明了两个顶点直接的不同不关系。例如,地图应用中必须存储单行道的信息,避免给出错误的方向。如果图中任意两个顶点之间的边都是有向边,这个图就是有向图。如果有一个非有向无环图,且A点出发向B经C可回到A,形成一个环。将从C到A的边方向改为从A到C,则变成有向无环图,即DAG。

    按照数学上的定义,DAG是一个没有有向循环的、有限的有向图。具体来说,它由有限个顶点和有向边组成,每条有向边都从一个顶点指向另一个顶点;从任意一个顶点出发都不能通过这些有向边回到原来的顶点。也就是说,它由 顶点 Vertex 和 边 Edge (也称为弧)组成,每条边都从一个顶点指向另一个顶点,沿着这些顶点的方向 不会形成一个闭合的环 。DAG与代数拓扑学中的偏序集(Partially Ordered Set,Poset)有紧密联系。偏序关系相同的任意两个图会有相同的拓扑排序集。事实上,任何一个DAG都唯一对应一个Poset, 而所有的Poset都是DAG,所以它们在本质上是一种事物。

    DAG具有一些很好性质,比如很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题。

    DAG的特性

    DAG 具有空间结构和时间序列的混合特性,与数据结构中的树密切相关,其拓扑排序和最短路径的计算,都有着独到的特点。

    DAG 与树的关系

    DAG是树的泛化,也是ploy tree的泛化。tree 是层次化,按照类别或者特性可以细分到原子单元,树其实就是一种无环连通图。DAG 从源开始细分,但是中间可以有合,有汇总。D就是可以合的点。

    因为有向图中一个点经过两种路线到达另一个点未必形成环,因此有向无环图未必能转化成树,但任何有向树均为有向无环图。

    DAG 的拓扑排序

    拓扑排序是一个可以把所有的顶点排序的算法,它排序的依据是深度优先搜索算法的完成时间。可以根据拓扑排序来计算有向无环图(的单源最短路径),因为拓扑排序正好是建立在无环的基础上,在这个图中没有负权重边以及回路边。

    拓扑排序是将图中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

    对于一个DAG,可以这样确定一个图中顶点的顺序:对于所有的u、v,若存在有向路径u-->v,则在最后的顶点排序中u就位于v之前。这样确定的顺序就是一个DAG的拓扑排序。拓扑排序的特点如下:(1)所有可以到达顶点v的顶点u都位于顶点v之前;(2)所有从顶点v可以到达的顶点u都位于顶点v之后。

    另外,只有有向无环图才存在拓扑排序,一个图的拓扑顺序不唯一。

    实现拓扑排序主要有两种方法:入度表和DFS。在DFS实现拓扑排序时,用栈来保存拓扑排序的顶点序列;并且保证在某顶点入栈前,其所有邻接点已入栈。下面列出的是用C语言实现的入度表拓扑排序示例代码:

    #define MAX_NODE 1000
    #define MAX_EDGE_NUM 100000
    struct Edge{
        int to;
        int w;
        int next;
    };
    Edge gEdges[MAX_EDGE_NUM];
    int gHead[MAX_NODE];
    bool gVisited[MAX_NODE];
    int gInDegree[MAX_NODE];
    int gEdgeCount;
    void InsertEdge(int u,int v,int w){
        int e = gEdgeCount++;
        gEdges[e].to = v;
        gEdges[e].w = w;
        gEdges[e].next = gHead[u];
        gHead[u] = e;
        gInDegree[v] ++;   //入度加1
    }
    void TopoSort(int n/*节点数目*/){
        queue<int> zero_indegree_queue;
        for (int i = 0; i < n; i++){
          if (gInDegree[i] == 0)
                  zero_indegree_queue.push(i);
        }
        memset(gVisited,false,sizeof(gVisited));
        while (!zero_indegree_queue.empty()){
            int u = zero_indegree_queue.front();
            zero_indegree_queue.pop();
            gVisited[u] =true;
            //输出u
            for (int e = gHead[u]; e != -1; e = gEdges[e].next){
                int v = gEdges[e].to;
                gInDegree[v] --;
                if (gInDegree[v] == 0){
                    zero_indegree_queue.push(v);
                }
            }
        }
        for (int i = 0; i < n; i++){
            if (!gVisited[i]){
                //环!无法形成拓扑序
            }
        }
    }

    DAG 的单源最短路径

    图中节点的单源最短路径可以使用Dijkstra,BellmanFord, SPFA算法,而对于有向无环图DAG来说,可以通过简单的动态规划来进行求解。DAG的独特之处是所有节点可以线性化(拓扑序列),使得所有边保持从左到右的方向。

    给定一个DAG和一个源点,可以得到该源点到其他所有的顶点的最短路径。如果是无负权,可以用djistra算法完成。但如果存在负权,则不行。同时,djistra算法效率并不高,既然是DAG,则可以利用拓扑排序的结果求出给定源点的最短路径,其时间复杂度是线性时间复杂度O(V+E)。

    DAG 的单源最短路径算法原理如下:

    1) 初始化dist[] = {INF, INF, ….} ,dist[s] = 0 是单源顶点 

    2)创建所有定点的拓扑排序

    3) 对拓扑排序中的每个顶点u 做如下处理,即处理u 的每个相邻顶点:if (dist[v] > dist[u] + weight(u, v)) dist[v] = dist[u] + weight(u, v) 

    具体地, 用Python 实现的DAG最短路径算法代码示例如下:

    # Python program to find single source shortest paths
    # for Directed Acyclic Graphs Complexity :OV(V+E)
    from collections import defaultdict
     
    # Graph is represented using adjacency list. Every
    # node of adjacency list contains vertex number of
    # the vertex to which edge connects. It also contains
    # weight of the edge
    class Graph:
        def __init__(self,vertices):
     
            self.V = vertices # No. of vertices
     
            # dictionary containing adjacency List
            self.graph = defaultdict(list)
     
        # function to add an edge to graph
        def addEdge(self,u,v,w):
            self.graph[u].append((v,w))
        # A recursive function used by shortestPath
        def topologicalSortUtil(self,v,visited,stack):
     
            # Mark the current node as visited.
            visited[v] = True
     
            # Recur for all the vertices adjacent to this vertex
            if v in self.graph.keys():
                for node,weight in self.graph[v]:
                    if visited[node] == False:
                        self.topologicalSortUtil(node,visited,stack)
     
            # Push current vertex to stack which stores topological sort
            stack.append(v)
         ''' The function to find shortest paths from given vertex.
            It uses recursive topologicalSortUtil() to get topological
            sorting of given graph.'''
        def shortestPath(self, s):
     
            # Mark all the vertices as not visited
            visited = [False]*self.V
            stack =[]
     
            # Call the recursive helper function to store Topological
            # Sort starting from source vertice
            for i in range(self.V):
                if visited[i] == False:
                    self.topologicalSortUtil(s,visited,stack)
     
            # Initialize distances to all vertices as infinite and
            # distance to source as 0
            dist = [float("Inf")] * (self.V)
            dist[s] = 0
     
            # Process vertices in topological order
            while stack:
     
                # Get the next vertex from topological order
                i = stack.pop()
     
                # Update distances of all adjacent vertices
                for node,weight in self.graph[i]:
                    if dist[node] > dist[i] + weight:
                        dist[node] = dist[i] + weight
     
                # Print the calculated shortest distances
                for i in range(self.V):
                     print ("%d" %dist[i]) if dist[i] != float("Inf") else  "Inf" ,
         g = Graph(6)
    g.addEdge(0, 1, 5)
    g.addEdge(0, 2, 3)
    g.addEdge(1, 3, 6)
    g.addEdge(1, 2, 2)
    g.addEdge(2, 4, 4)
    g.addEdge(2, 5, 2)
    g.addEdge(2, 3, 7)
    g.addEdge(3, 4, -1)
    g.addEdge(4, 5, -2)
     
    # source = 1
    s = 1
     
    print ("Following are shortest distances from source %d " % s)
    g.shortestPath(s)
     
    # This code is contributed by Neelam Yadav
    

    DAG的应用

    鉴于DAG的一般性,具有广泛的应用场景。

    DAG 的存储结构用例

    作为数据结构,DAG 在数据存储方面非常著名的使用场景就是Git。Git采用了Merkle Tree+ DAG作为一个组合的数据结构Merkle DAG,来实现了分布式的的版本控制。

    IPFS 参考了Git的实现思想,同样使用了Merkle DAG 作为核心的数据结构,即后来称为IPLD, 在 IPFS 生态系统的“蜂腰”模型中处于腰的位置,如下图所示: 

    Merkle Tree通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。在Merkle Tree 的基础上,Merkle DAG是一个有向无环图,可以简单的理解成一棵树,且没有Merkle Tree那样严格的限制(例如平衡树),其特点是:

    • 父节点的哈希值由子节点的哈希值决定,即父节点的哈希值是由子节点的哈希值拼接得来的字符串哈希而成。

    • 父节点中包含指向子节点的信息。

    Merkle DAG保留了Merkle Tree的精华部分,即任何一个下层节点改动,都将导致上层节点的哈希值变动,最终的根节点的哈希值也变动。在IPFS网络中,存储文件时,首先会将文件切片,切割成256KB大小的文件。之后循环调用(MerkleDAG.Add)方法构建文件MerkleDAG。文件hash值创建流程如下: 

    1. 将切片之后的文件进行sha-256运算 

    2. 将运算结果选取0~31位 

    3. 将选取结果根据base58编码,运算结果前追加Qm 即为最后结果作为文件的46位hash值。

    在IPFS中,使用DAGService维护MerkleDAG,为MerkleDAG提供删除和增加的权限。其中的Merkle DAG为多叉树结构,最多为174叉树。

    通过Merkle DAG, IPFS能够轻松确保和验证P2P格式的计算机之间共享数据的完整性,这使得它们对系统非常有用。

    DAG 的因果关系用例

    以探讨影响因素或者控制偏倚为目的回归模型,要求自变量和因变量往往存在着因果关系,所以自变量筛选首先需要考虑自变量能否纳入到模型,严格挑选自变量进入模型。

    DAG可以说是回归分析的灵魂所在,是最高指导方针。基于DAG构建因果关系网络,从而找到合适进入模型的自变量。箭头发出对象为因,箭头指向为果。所有变量因果关系通过方向线形成的单向网络,即DAG。

    例如,贝叶斯网络是表示多个概率事件的关联网络。顶点表示事件,后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。

    动态规划的DAG 实现

    什么是动态规划呢?问题可以分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。

    将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序去求每阶段的解。各阶段开始时的客观条件叫做状态。当各段的状态取定以后,就可以做出不同的决定,从而确定下一阶段的状态,这种决定称为决策。具体地,动态规划的递推需要一个线性或者树形的顺序,对于DAG,可以将节点按照拓扑顺序来进行线性化。具体地,对于当前的节点v,在拓扑序列中向前查找,可能找到一些可以到达该顶点的其他节点,然后利用 dist[v] = min{dist[u] + w[u][v] | u 可以到达v}来进行动态规划的递推。

    基于DAG 调度用例

    在有相互依赖的调度系统中,DAG 有着非常典型的应用。这里以Spark 为例进行说明。

    在Spark中的每一个操作生成一个RDD,RDD之间形成一条边,最后这些RDD和他们之间的边组成一个有向无环图,这个就是DAG。

    Spark中的RDD依赖关系分为两种:窄依赖(Narrow Dependencies)与宽依赖(Wide Dependencies,源码中称为Shuffle Dependencies)会根据宽依赖窄依赖来划分具体的Stage,而依赖有2个作用:

    • 用来解决数据容错的高效性;

    • 其二用来划分stage。


    原始的RDD通过一系列的转换就形成了DAG,有了可计算的DAG,Spark内核下一步的任务就是根据DAG图将计算划分成任务集,也就是Stage,这样可以将任务提交到计算节点进行真正的计算。Spark计算的中间结果默认是保存在内存中的,Spark在划分Stage的时候会充分考虑在分布式计算中可流水线计算的部分来提高计算的效率,而在这个过程中Spark根据RDD之间依赖关系的不同将DAG划分成不同的Stage。对于窄依赖,partition的转换处理在一个Stage中完成计算。对于宽依赖,由于有Shuffle的存在,只能在parent RDD处理完成后,才能开始接下来的计算,因此宽依赖是划分Stage的依据。

    Spark 执行时的处理流程如下:

    1)用户代码定义RDD的有向无环图

    RDD上的操作会创建新的RDD,并引用它们的父节点,这样就创建了一个图。

    2)行动操作把有向无环图强制转译为执行计划

    当调用RDD的一个行动操作时,这个RDD就必须被计算出来。这也要求计算出该RDD的父节点。Spark调度器提交一个作业来计算出所有必要的RDD。这个作业会包含一个或多个步骤,每个步骤其实也就是一波并行执行的计算任务。一个步骤对应有向五环图中的一个或多个RDD,一个步骤对应多个RDD是因为发生了流水线执行。

    3)任务于集群中调度并执行 

    步骤是按顺序处理的,任务则独立的启动来计算出RDD的一部分。一旦作业的最后一个步骤结束,一个行动操作也就执行完了。

    DAG 的区块链用例

    最早在区块链中引入DAG概念作为共识算法是在2013年,bitcointalik.org由ID为avivz78的以色列希伯来大学学者提出,也就是GHOST协议,作为比特币的交易处理能力扩容解决方案;Vitalik在以太坊紫皮书描述的POS共识协议Casper,也是基于GHOST POW协议的POS变种。

    后来,有人提出用DAG的拓扑结构来存储区块,解决区块链的效率问题。区块链只有一条单链,打包出块无法并发执行。如果改变区块的链式存储结构,变成DAG的网状拓扑就可以实现并发写入。在区块打包时间不变的情况下,网络中可以并行打包N个区块,网络中的交易效率就提升了N倍。

    那个时候,DAG跟区块链的结合依旧停留在类似侧链的解决思路,交易打包可以并行在不同的分支链条进行,达到提升性能的目的。此时,DAG还是区块的概念。

    2015年9月,Sergio Demian Lerner发表了 《DagCoin: a cryptocurrency without blocks》一文,提出了DAG-Chain的概念,首次把DAG网络从区块打包这样粗粒度提升到了基于交易层面。DagCoin的思路,让每一笔交易都直接参与维护全网的交易顺序。交易发起后,直接广播全网,这样省去了打包交易出块的时间。也就是说,交易发起后直接广播网络确认,理论上效率得到了质的飞跃。

    进一步,DAG演变成了完全抛弃区块链的一种解决方案。2016年7月,基于IOTA横空出世,随后ByteBall也登场了,IOTA和Byteball是头一次DAG网络的真正技术实现,此时,号称无块之链、独树一帜的DAG链家族雏形基本形成。

    从某种程度上说,DAG可能是面向未来的新一代区块链,从单链进化到树状和网状、从区块粒度细化到交易粒度、从单点跃迁到并发写入,这是区块链从容量到速度的一次革新。

    一句话小结

    有向无环图有许多科学的和计算的应用,从生物学到社会学再到我们所熟悉的计算机领域,而且,DAG的原理并不复杂,关键在于把目标问题抽象为DAG,进而使用DAG的相关特性来解决问题。

    【参考资料与关联阅读】 

    展开全文
  • 重要概念 无环图(Directed Acyclic Graph, DAG)是有向图的一种,字面意思的理解就是图中没有。常常被用来表示事件之间的驱动依赖关系,管理任务之间的调度。 顶点:图中的一个点,比如顶点 1,顶点 2。 边...

    前言

    说到 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/AnchorTask

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

    推荐阅读

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

    职场上这四件事,越早知道越好

    拼夕夕事件反思,底层逆袭,靠拼命加班行吗

    面试官:手写生产者消费者模型

    展开全文
  • 在一个程序中,两种执行关系,一种是a执行完了才能执行b,也就是串行;另外一种是a和b没有依赖关系,a和b可以同时执行,也就是并行。 如上图所示,这是一个无环图,箭头表示事件之间的...(对于有向图:节点(..

    在一个程序中,有两种执行关系,一种是a执行完了才能执行b,也就是串行;另外一种是a和b没有依赖关系,a和b可以同时执行,也就是并行。

    如上图所示,这是一个有向无环图,箭头表示事件之间的驱动依赖关系。比如A和B事件执行完了才可以执行F事件,F和G事件执行完了才可以执行I事件。A、B、C、D、E、K事件可以同时执行。

    我在工作中遇到的问题就是把可以一起执行的事件名字放到一起,以便后面可以一起调度,这个时候就需要拓扑排序算法啦。拓扑排序的流程如下:

    step1:先统计所有节点的入度。(对于有向图:节点(顶点)的入度是指进入该节点(顶点)的边的条数;节点(顶点)的出度是指从该节点(顶点)出发的边的条数。)可以看出:

     此时入度为0的顶点有:A、B、C、D、E、K

    入度为1的顶点有:L、N

     入度为2的顶点有:F、G、H、I

    入度为3的顶点有:J

    step2:从图中选择一个入度为0的顶点,输出该顶点。从图中删除该节点及其所有出边(即与之邻接的所有顶点入度-1)。

    结合我要写的程序,我每次是把图中所有的入度为0的顶点都输出,然后把相邻的顶点的入度-1。

    step3:反复执行这两个步骤,直至所有节点都输出,即整个拓扑排序完成。

    我要做的具体工作:

    (1)我要做的是第一步把入度为0的顶点A、B、C、D、E、K输出为调度1,然后与他们相邻的节点是F、G、H、L,把他们的入度-1,删除顶点A、B、C、D、E、K,此时入度表变为:

     入度为0的顶点有:F、G、H、L(因为F/G/H同时和两个删除的顶点相邻,所以入度-2)

    入度为1的顶点有:N

    入度为2的顶点有:I

    入度为3的顶点有:J

    (2)我要做的是第二步把入度为0的顶点F、G、H、L输出为调度2,然后与他们相邻的节点是I、G、N,把他们的入度-1,删除顶点F、G、H、L,此时入度表变为:

     入度为0的顶点有:N、I(因为I同时和两个删除的顶点相邻,所以入度-2)

    入度为1的顶点有:J(因为J同时和两个删除的顶点相邻,所以入度-2)

    (3)省略。。。反正就是重复以上步骤啦。最后我们可以得到一个调度表:

    调度1:A、B、C、D、E、K

    调度2:F、G、H、L

    调度3:N、I

    调度4:J

    调度一样的事件就是可以一起并行执行的。

    代码明天再更嗷~~~~博主好懒~~~~

     

    展开全文
  • 重要概念 无环图(Directed Acyclic Graph, DAG)是有向图的一种,字面意思的理解就是图中没有。常常被用来表示事件之间的驱动依赖关系,管理任务之间的调度。 顶点:图中的一个点,比如顶点 1,顶点 2。 边...
  • 文章目录无环图拓扑排序AOV-网AOE-网关键路径的概念事件的最早/晚...将这些子工程之间的先后关系用有向图表示,其中顶点表示活动,向边表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网。
  • 基于《算法4》的描述,在之前有向图数据结构基础上,实现无环图(DAG)、拓扑排序、强连通分量(Kosaraju)算法; 一些概念 无环图(DAG):不含有有向图;拓扑排序: 给定一幅有向图,使得向边均从排...
  • 在现实中,我们经常会遇到如图所示问题 这张图指明了想要完成指定的任务所需完成...很明显,当有向图种存在时,调度问题是解的。 检测 //寻找 class directedcycle { public: directedcycle(digraph
  • 这是我的第70篇原创拼奢侈品装名媛,实在是太LOW了。真正的奢侈品不是外物,而是知识!是科学!你看我,从来没告诉过任何人,我开过私人飞机。所以,今天要给大家分享一个可以在朋友圈装X的词:...
  • 业务场景调度系统的任务可视化界面需要完成用户可在界面上连线作为任意两个job间的依赖关系,也就是DAG图DAG也就是无环图,无环图指的是一个回路的有向图是一条至少含有一条边且起点和终点相同的路径...
  • 1. 引言无环图(Directed Acyclic Graph, DAG)是有向图的一种,字面意思的理解就是图中没有。常常被用来表示事件之间的驱动依赖关系,管理任务之间的调度。拓扑排序是对DAG的顶点进行排序,使得对每一条向边...
  • 调度问题 是什么

    2021-09-27 00:35:28
    调 度 问 题 可 描 述 为 生 产 加  过 程 中 在满足 生 产 境 及 各类 约 束条件 下 将 问 题 中 的 所有 王 件 分 配 到 各 个机 器 上 进 行加 工 但 各 个 工 件要 根 据 既 定 规 则 进 行 排序 其 最...
  • 电网调度厂站端调试员高级工技能鉴定试题整理(包括).doc技能鉴定试题库(高级)一、选择题:1.8251(C)8位I/O口A.2个; B.16个; C.4个; D.5个。2.在WIN98中,应用程序之间的信息传递经常 通过(C)完成。A.屏幕; B...
  • TDH 配置yarn调度策略scheduler 不生效问题1:在yarn配置界面修改scheduler策略不生效问题2:新增yarn队列后,提交任务提示对应用户没有权限 问题1:在yarn配置界面修改scheduler策略不生效 楼主想增加yarn的...
  • 文章目录手把手教你设计一个任务调度器先从一道简单的面试题说起题目分析参考实现我们项目中的任务调度角色说明taskJobScheduler如何描述 task 之间的执行顺序设计思路有向多叉树有向无环图设计整体结构实现分析接口...
  • 手把手教您玩转开源大数据调度器Apache DolphinScheduler安装维护与实践,学不会你来打我。
  • 本发明涉及任务调度系统技术领域,尤其是涉及一种能够加速保证算法的效率,同时提高算法搜索效率的基于蒙特卡洛树搜索的DAG任务调度方法。...其模型如下:用一个有向无环图(DAG)G(V,E)代表一个计算应用。其中V代表应...
  • DolphinScheduler 架构 作为强大的带有有向无环图(DAG)可视化界面的分布式大数据工作流调度平台,DolphinScheduler解决了复杂的任务依赖关系和简化了数据任务编排的工作。它以开箱即用的、易于扩展的方式将众多...
  • 浅谈大数据任务调度平台

    千次阅读 热门讨论 2020-12-28 13:54:35
    谈到大数据,避免不了hadoop, hive, spark 这些基础套件,但是在整个大数据开发的时候,我们面对的基本上都是数据开发平台和任务调度系统。数据开发平台一般直接面对业务同学,很大程度上影响业务同学的开发效率和...
  • Agv、Rgv 车辆控制调度系统开发第一篇

    千次阅读 热门讨论 2021-06-19 22:35:37
    Agv、Rgv 车辆控制调度系统第一篇为什么要做这个系统先看作品从头讲起算法讲解编程语言从哪里开始继续深入预告 为什么要做这个系统 说白了是为了赚钱,在一个项目中发现公司买别人家的调度系统要几十万,还只是一个...
  • 调度算法

    2021-01-18 23:04:22
    先来先服务 例如:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。 ...
  • 前言 在上一篇 xxl-job 执行器原理分析 一文中,我们提到了 xxl-job 框架中包含了两个核心模块:调度中心 和 执行器, 其中调度中心主要负责 ...再看一遍 xxl-job 架构调度中心主要提供了两个功能: 系统管理 和
  • 作者 | 高光轩 ...但是我们不难发现几个问题,随着用户脚本(dag文件)和工程目录数量越来越多,我们可能面临整任务出现了延时调度的现象。 举个例子说明下,假设你设置了一个任务是每天8:00跑,但是你发现到了...
  • 新一代大数据任务调度 - Apache DolphinScheduler(incubator) 在经过社区 30 多位小伙伴的贡献与努力下于发布了 1.3.4 版本,1.3.4 作为 1.3.x 的 bug 修复版本,本次共修复了 1.3.3 发现的 10 多处 bug,其中多数 ...
  • 资源描述:生产调度问题及其优化算法 (采用遗传算法与MATLAB编程) 信息014 孙卓明 二零零三年八月十四日 生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要...
  • flink任务调度原理

    2021-10-28 13:51:24
    任务调度原理 客户端不是运行时和程序执行 的一部分,但它用于准备并发送 dataflow(JobGraph)给 Master(JobManager),然后,客户端断开连接或者维持连接以 等待接收计算结果。 当 Flink 集 群 启 动 后...
  • 五一节前面试的时候被问到 Android 启动任务依赖怎么做调度。当时随口给了一个方案,后来想想觉得有意思就自己花了两天的时间写了一个。思路展现在写这个库之前只是看了下 Jetpack 的 Startup. 毕竟,如果这个库已经...
  • 实验概述:【实验目的及要求】理解并掌握处理机调度算法【实验原理】基于先来先服务调度和最短作业优先调度算法思想用C语言编程实现【实验环境】(使用的软件)Visual C++实验内容:本实验模拟在单处理机情况下处理机...
  • 1.区别ETL作业调度工具和任务流调度工具kettle是一个ETL工具,ETL(Extract-Transform-Load的缩写,即数据...所以他的重心是用于数据oozie是一个工作流,Oozie工作流是放置在控制依赖DAG(有向无环图 Direct Acyclic ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,967
精华内容 17,586
关键字:

有向无环图调度

友情链接: lcd1602.rar