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

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

01

—

Spark背景介紹

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

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

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

02

—

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

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

入度

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

出度

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

03

—

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

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

Algorithms課指向Theoretical CS，意思是選修后者需要先修完Algorithms這門課，Artificial Intelligence依賴Theoretical CS，Machine learning 依賴Artificial Intelligence，Neural Networks依賴Machine learning這門課，這稱為一條路徑。

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

04

—

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

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

05

—

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

那么，如何檢測一個有向圖是否是DAG呢？

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

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

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

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

1. 對訪問過的元素做標(biāo)記

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

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

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

網(wǎng)站名稱：Spark有向無環(huán)圖檢測的示例分析
分享URL：http://www.chinadenli.net/article24/ippece.html

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

廣告

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