Spark有向無(wú)環(huán)圖檢測(cè)的示例分析

這篇文章給大家介紹Spark有向無(wú)環(huán)圖檢測(cè)的示例分析，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

我們提供的服務(wù)有：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、加查ssl等。為千余家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢(xún)和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的加查網(wǎng)站制作公司

01

—

Spark背景介紹

Apache Spark 是專(zhuān)為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的快速通用的計(jì)算引擎。Spark 是一種與 Hadoop 相似的開(kāi)源集群計(jì)算環(huán)境，擁有Hadoop MapReduce所具有的優(yōu)點(diǎn)；但不同于MapReduce的是——Job中間輸出結(jié)果可以保存在內(nèi)存中，從而不再需要讀寫(xiě)HDFS，因此Spark能更好地適用于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)等需要迭代的MapReduce的算法。

RDD，全稱(chēng)為Resilient Distributed Datasets，中文翻譯彈性分布式數(shù)據(jù)集，是一個(gè)容錯(cuò)的、并行的數(shù)據(jù)結(jié)構(gòu)，可以讓用戶(hù)顯式地將數(shù)據(jù)存儲(chǔ)到磁盤(pán)和內(nèi)存中，并能控制數(shù)據(jù)的分區(qū)。RDD是Spark的靈魂，一個(gè)RDD代表一個(gè)可以被分區(qū)的只讀數(shù)據(jù)集。RDD內(nèi)部可以有許多分區(qū)(partitions)，每個(gè)分區(qū)又擁有大量的記錄(records)。

RDD之間的依賴(lài)關(guān)系是靠有向無(wú)環(huán)圖（DAG）表達(dá)的，下面看下有向無(wú)環(huán)圖的基本理論和算法。

02

—

有向無(wú)環(huán)圖（DAG）

在圖論中，邊沒(méi)有方向的圖稱(chēng)為無(wú)向圖，如果邊有方向稱(chēng)為有向圖。在無(wú)向圖的基礎(chǔ)上，任何頂點(diǎn)都無(wú)法經(jīng)過(guò)若干條邊回到該點(diǎn)，則這個(gè)圖就沒(méi)有環(huán)路，稱(chēng)為有向無(wú)環(huán)圖（DAG圖），如下圖所示，4->6->1->2是一個(gè)路徑，4->6->5也是一條路徑，并且圖中不存在頂點(diǎn)經(jīng)過(guò)若干條邊后能回到該點(diǎn)，可以得出下圖為DAG。

入度

入度是圖論算法中重要的概念之一。它通常指有向圖中某點(diǎn)作為圖中邊的終點(diǎn)的次數(shù)之和，也就是項(xiàng)點(diǎn)的入邊條數(shù)稱(chēng)為該項(xiàng)點(diǎn)的入度。如上圖所示，頂點(diǎn)4的入度為0.

出度

對(duì)應(yīng)于入度，頂點(diǎn)的出邊條數(shù)稱(chēng)為該頂點(diǎn)的出度。如上圖所示，頂點(diǎn)3的入度為2.

03

—

DAG應(yīng)用的另一個(gè)例子

在一些任務(wù)安排和調(diào)度的問(wèn)題里。不同的問(wèn)題或者任務(wù)之間又一些依賴(lài)的關(guān)系，有的任務(wù)需要在某些任務(wù)完成之后才能做。就像一些學(xué)校的教學(xué)課程安排。設(shè)置某一門(mén)課程需要依賴(lài)于一個(gè)前置的課程，只有學(xué)生學(xué)習(xí)了前置課程之后才能取學(xué)習(xí)該課程。如果將一門(mén)課程當(dāng)做一個(gè)節(jié)點(diǎn)，從它引出一個(gè)指針指向后序依賴(lài)它的課程。就可能有一個(gè)類(lèi)似這樣的圖：

Algorithms課指向Theoretical CS，意思是選修后者需要先修完Algorithms這門(mén)課，Artificial Intelligence依賴(lài)Theoretical CS，Machine learning 依賴(lài)Artificial Intelligence，Neural Networks依賴(lài)Machine learning這門(mén)課，這稱(chēng)為一條路徑。

還可以看到，上圖中入度為0的節(jié)點(diǎn)有 Introduction to CS，這個(gè)節(jié)點(diǎn)在有向圖遍歷中具有重要意義，下面會(huì)說(shuō)到。

04

—

如果上圖有環(huán)，還正確嗎？

如上所示，如果Machine learning再指向Theoretical CS，意思是選修Theoretical CS的同學(xué)需要先修Machine learning，這個(gè)就和原來(lái)的路徑Artificial Intelligence依賴(lài)Theoretical CS，Machine learning 依賴(lài)Artificial Intelligence，違背！，并且也不合常理，Theoretical CS是一門(mén)基礎(chǔ)性的理論課，怎么可能選修它之前要先修完machine learning呢？所以不能有環(huán)路，這個(gè)圖是不正確的。所以，這個(gè)圖必須為有向無(wú)環(huán)圖！

05

—

有向圖如何檢測(cè)有、無(wú)環(huán)？

那么，如何檢測(cè)一個(gè)有向圖是否是DAG呢？

有向圖的環(huán)檢測(cè)，首先對(duì)照著無(wú)向圖的環(huán)檢測(cè)來(lái)理解，在無(wú)向圖中，我們要檢測(cè)一個(gè)圖中間是否存在環(huán)，需要通過(guò)深度優(yōu)先或廣度優(yōu)先的方式，對(duì)訪問(wèn)過(guò)的元素做標(biāo)記。如果再次碰到前面訪問(wèn)過(guò)的元素，則說(shuō)明可能存在環(huán)。只做標(biāo)記，在有向圖中檢測(cè)環(huán)路的辦法可行嗎？

如下圖所示，深度優(yōu)先遍歷方法，已經(jīng)遍歷了節(jié)點(diǎn)2和6，并marked了，現(xiàn)在遍歷節(jié)點(diǎn)1的另一條邊，依次遍歷3,4,5,6，因?yàn)?已經(jīng)遍歷，所以說(shuō)形成了環(huán)路，但是實(shí)際上并沒(méi)有，因此，與實(shí)際不符合，只對(duì)訪問(wèn)過(guò)的元素做標(biāo)記判斷有無(wú)環(huán)路是錯(cuò)誤的。

感覺(jué)是要加條件，加什么條件？ 如果我們加一個(gè)數(shù)組保存當(dāng)前節(jié)點(diǎn)是否位于遞歸棧onStack中，就可以排除上面的問(wèn)題，因?yàn)?,6被標(biāo)記后，依次遞歸出棧，然后到1，深度遍歷1的另一條邊（3->4->5->6），所以6此時(shí)不在onStack上，第一次被檢測(cè)到，所以沒(méi)有環(huán)路。

因此，有向圖的無(wú)環(huán)檢測(cè)，需要同時(shí)借助兩個(gè)限制條件：

1. 對(duì)訪問(wèn)過(guò)的元素做標(biāo)記

2. 當(dāng)前節(jié)點(diǎn)是否位于遞歸棧onStack中

在上圖的基礎(chǔ)上，增加節(jié)點(diǎn)7和8，如下圖所示，可以預(yù)見(jiàn)，按照深度優(yōu)先搜索到節(jié)點(diǎn)4時(shí)，會(huì)找到子節(jié)點(diǎn)5，節(jié)點(diǎn)5的其中一個(gè)邊找到7，找到8，找到4,節(jié)點(diǎn)4此時(shí)已經(jīng)位于onStack中，所以構(gòu)成環(huán)路，是有環(huán)圖。

關(guān)于Spark有向無(wú)環(huán)圖檢測(cè)的示例分析就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

網(wǎng)站名稱(chēng)：Spark有向無(wú)環(huán)圖檢測(cè)的示例分析
分享URL：http://muchs.cn/article24/ippece.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、定制網(wǎng)站、外貿(mào)建站、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)