Spark|有向无环图(DAG)检测

01

Spark背景介绍

Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环境,拥有Hadoop MapReduce所具有的优点;但不同于MapReduce的是——Job中间输出结果可以保存在内存中,从而不再需要读写HDFS,因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法。

RDD,全称为Resilient Distributed Datasets,中文翻译弹性分布式数据集,是一个容错的、并行的数据结构,可以让用户显式地将数据存储到磁盘和内存中,并能控制数据的分区。RDD是Spark的灵魂,一个RDD代表一个可以被分区的只读数据集。RDD内部可以有许多分区(partitions),每个分区又拥有大量的记录(records)。

RDD之间的依赖关系是靠有向无环图(DAG)表达的,下面看下有向无环图的基本理论和算法。

02

有向无环图(DAG)

在图论中,边没有方向的图称为无向图,如果边有方向称为有向图。在无向图的基础上,任何顶点都无法经过若干条边回到该点,则这个图就没有环路,称为有向无环图(DAG图),如下图所示,4->6->1->2是一个路径,4->6->5也是一条路径,并且图中不存在顶点经过若干条边后能回到该点,可以得出下图为DAG。

入度

入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和,也就是项点的入边条数称为该项点的入度。如上图所示,顶点4的入度为0.

出度

对应于入度,顶点的出边条数称为该顶点的出度。如上图所示,顶点3的入度为2.

03

DAG应用的另一个例子

在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系,有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程,只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点,从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图:

Algorithms课指向Theoretical CS,意思是选修后者需要先修完Algorithms这门课,Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,Neural Networks依赖Machine learning这门课,这称为一条路径。

还可以看到,上图中入度为0的节点有 Introduction to CS,这个节点在有向图遍历中具有重要意义,下面会说到。

04

如果上图有环,还正确吗?

如上所示,如果Machine learning再指向Theoretical CS,意思是选修Theoretical CS的同学需要先修Machine learning,这个就和原来的路径Artificial Intelligence依赖Theoretical CS,Machine learning 依赖Artificial Intelligence,违背!,并且也不合常理,Theoretical CS是一门基础性的理论课,怎么可能选修它之前要先修完machine learning呢?所以不能有环路,这个图是不正确的。所以,这个图必须为有向无环图!

05

有向图如何检测有、无环?

那么,如何检测一个有向图是否是DAG呢?

有向图的环检测,首先对照着无向图的环检测来理解,在无向图中,我们要检测一个图中间是否存在环,需要通过深度优先或广度优先的方式,对访问过的元素做标记。如果再次碰到前面访问过的元素,则说明可能存在环。只做标记,在有向图中检测环路的办法可行吗?

如下图所示,深度优先遍历方法,已经遍历了节点2和6,并marked了,现在遍历节点1的另一条边,依次遍历3,4,5,6,因为6已经遍历,所以说形成了环路,但是实际上并没有,因此,与实际不符合,只对访问过的元素做标记判断有无环路是错误的。

感觉是要加条件,加什么条件? 如果我们加一个数组保存当前节点是否位于递归栈onStack中,就可以排除上面的问题,因为2,6被标记后,依次递归出栈,然后到1,深度遍历1的另一条边(3->4->5->6),所以6此时不在onStack上,第一次被检测到,所以没有环路。

因此,有向图的无环检测,需要同时借助两个限制条件:

  1. 对访问过的元素做标记
  2. 当前节点是否位于递归栈onStack中

在上图的基础上,增加节点7和8,如下图所示,可以预见,按照深度优先搜索到节点4时,会找到子节点5,节点5的其中一个边找到7,找到8,找到4,节点4此时已经位于onStack中,所以构成环路,是有环图。

总结,以上就是有向图有环,无环检测算法的基本思想。关于有向图有环判断检测的java版源码请参考github之spark文件夹中的directedCycle类(代码参考princeton源码)。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2018-01-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

你真的懂数据分析吗?一文读懂数据分析的流程、基本方法和实践

导读:无论你的工作内容是什么,掌握一定的数据分析能力,都可以帮你更好的认识世界,更好的提升工作效率。数据分析除了包含传统意义上的统计分析之外,也包含寻找有效特征...

1412
来自专栏张俊的专栏

【SPA大赛】机场客流量的时空分布预测比赛经验分享

1. 问题描述机场拥有巨大的旅客吞吐量,与巨大的人员流动相对应的则是巨大的服务压力。安防、安检、突发事件应急、值机、行李追踪等机场服务都希望能够预测未来的旅客吞...

6660
来自专栏编程札记

协同过滤Item-based算法实现电影推荐系统

1.6K3
来自专栏斑斓

Spark 1.4为DataFrame新增的统计与数学函数

Spark一直都在快速地更新中,性能越来越快,功能越来越强大。我们既可以参与其中,也可以乐享其成。 目前,Spark 1.4版本在社区已经进入投票阶段,在Gi...

3617
来自专栏小樱的经验随笔

BZOJ 2038: [2009国家集训队]小Z的袜子(hose)【莫队算法裸题&&学习笔记】

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MB Submit: 9...

3066
来自专栏大数据文摘

手把手|如何用Python绘制JS地图?

52813
来自专栏数说工作室

海量文本用 Simhash, 2小时变4秒! | 文本分析:大规模文本处理(2)

这是一个相似匹配的问题(文本相似匹配基础→ 词频与余弦相似度)。但是,亿级数据库,用传统的相似度计算方法太慢了,我们需要一个文本查询方法,可以快速的把一段文本的...

4533
来自专栏about云

使用Spark MLlib给豆瓣用户推荐电影

问题导读: 1.常用的推荐算法有哪些? 2.推荐系统是什么样的流程? 3.从这个推荐系统我们能学到什么? 推荐算法就是利用用户的一些行为,通过一些数学算法,推测...

8227
来自专栏机器之心

资源 | 囊括欧亚非大陆多种语言的25个平行语料库数据集(拿走不谢!)

原文链接:https://gengo.ai/datasets/25-best-parallel-text-datasets-for-machine-transl...

2353
来自专栏鸿的学习笔记

写给开发者的机器学习指南(九)

正如你所看到的,最高的权重给予了几乎立即得到电子邮件回复的电子邮件,而最低权重给予具有非常长的时间范围的电子邮件。这允许具有非常低频率的电子邮件仍然基于它们被发...

1041

扫码关注云+社区

领取腾讯云代金券