如何用 Python 實現(xiàn)一個圖數(shù)據(jù)庫（Graph Database）？

本文章是 重寫 500 Lines or Less 系列的其中一篇，目標(biāo)是重寫 500 Lines or Less 系列的原有項目：Dagoba: an in-memory graph database。

創(chuàng)新新互聯(lián)，憑借10余年的成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)經(jīng)驗，本著真心·誠心服務(wù)的企業(yè)理念服務(wù)于成都中小企業(yè)設(shè)計網(wǎng)站有成百上千家案例。做網(wǎng)站建設(shè)，選創(chuàng)新互聯(lián)。

Dagoba 是作者設(shè)計用來展示如何從零開始自己實現(xiàn)一個圖數(shù)據(jù)庫（ Graph Database ）。該名字似乎來源于作者喜歡的一個樂隊，另一個原因是它的前綴 DAG 也正好是有向無環(huán)圖 （ Directed Acyclic Graph ） 的縮寫。本文也沿用了該名稱。

圖是一種常見的數(shù)據(jù)結(jié)構(gòu)，它將信息描述為若干獨立的節(jié)點（ vertex ，為了和下文的邊更加對稱，本文中稱為 node ），以及把節(jié)點關(guān)聯(lián)起來的邊（ edge ）。我們熟悉的鏈表以及多種樹結(jié)構(gòu)可以看作是符合特定規(guī)則的圖。圖在路徑選擇、推薦算法以及神經(jīng)網(wǎng)絡(luò)等方面都是重要的核心數(shù)據(jù)結(jié)構(gòu)。

既然圖的用途如此廣泛，一個重要的問題就是如何存儲它。如果在傳統(tǒng)的關(guān)系數(shù)據(jù)庫中存儲圖，很自然的做法就是為節(jié)點和邊各自創(chuàng)建一張表，并用外鍵把它們關(guān)聯(lián)起來。這樣的話，要查找某人所有的子女，就可以寫下類似下面的查詢：

還好，不算太復(fù)雜。但是如果要查找孫輩呢？那恐怕就要使用子查詢或者 CTE(Common Table Expression) 等特殊構(gòu)造了。再往下想，曾孫輩又該怎么查詢？孫媳婦呢？

這樣我們會意識到，SQL 作為查詢語言，它只是對二維數(shù)據(jù)表這種結(jié)構(gòu)而設(shè)計的，用它去查詢圖的話非常笨拙，很快會變得極其復(fù)雜，也難以擴展。針對圖而言，我們希望有一種更為自然和直觀的查詢語法，類似這樣：

為了高效地存儲和查詢圖這種數(shù)據(jù)結(jié)構(gòu)，圖數(shù)據(jù)庫（ Graph Database ）應(yīng)運而生。因為和傳統(tǒng)的關(guān)系型數(shù)據(jù)庫存在極大的差異，所以它屬于新型數(shù)據(jù)庫也就是 NoSql 的一個分支（其他分支包括文檔數(shù)據(jù)庫、列數(shù)據(jù)庫等）。圖數(shù)據(jù)庫的主要代表包括 Neo4J 等。本文介紹的 Dagoba 則是具備圖數(shù)據(jù)庫核心功能、主要用于教學(xué)和演示的一個簡單的圖數(shù)據(jù)庫。

原文代碼是使用 JavaScript 編寫的，在定義調(diào)用接口時大量使用了原型（ prototype ）這種特有的語言構(gòu)造。對于其他主流語言的用戶來說，原型的用法多少顯得有些別扭和不自然。

考慮到本系列其他數(shù)據(jù)庫示例大多是用 Python 實現(xiàn)的，本文也按照傳統(tǒng)，用 Python 重寫了原文的代碼。同樣延續(xù)之前的慣例，為了讓讀者更好地理解程序是如何逐步完善的，我們用迭代式的方法完成程序的各個組成部分。

原文在 500lines 系列的 Github 倉庫中只包含了實現(xiàn)代碼，并未包含測試。按照代碼注釋說明，測試程序位于作者的另一個代碼庫中，不過和 500lines 版本的實現(xiàn)似乎略有不同。

本文實現(xiàn)的代碼參考了原作者的測試內(nèi)容，但跳過了北歐神話這個例子——我承認(rèn)確實不熟悉這些神祇之間的親緣關(guān)系，相信中文背景的讀者們多數(shù)也未必了解，雖然作者很喜歡這個例子，想了想還是不要徒增困惑吧。因此本文在編寫測試用例時只參考了原文關(guān)于家族親屬的例子，放棄了神話相關(guān)的部分，盡管會減少一些趣味性，相信對于入門級的代碼來說這樣也夠用了。

本文實現(xiàn)程序位于代碼庫的 dagoba 目錄下。按照本系列程序的同意規(guī)則，要想直接執(zhí)行各個已完成的步驟，讀者可以在根目錄下的 main.py 找到相應(yīng)的代碼位置，取消注釋并運行即可。

本程序的所有步驟只需要 Python3 ，測試則使用內(nèi)置的 unittest , 不需要額外的第三方庫。原則上 Python3.6 以上版本應(yīng)該都可運行，但我只在 Python3.8.3 環(huán)境下完整測試過。

本文實現(xiàn)的程序從最簡單的案例開始，通過每個步驟逐步擴展，最終形成一個完整的程序。這些步驟包括：

接下來依次介紹各個步驟。

回想一下，圖數(shù)據(jù)庫就是一些點（ node ）和邊（ edge ）的集合?，F(xiàn)在我們要做出的一個重大決策是如何對節(jié)點/邊進(jìn)行建模。對于邊來說，必須指定它的關(guān)聯(lián)關(guān)系，也就是從哪個節(jié)點指向哪個節(jié)點。大多數(shù)情況下邊是有方向的——父子關(guān)系不指明方向可是要亂套的！

考慮到擴展性及通用性問題，我們可以把數(shù)據(jù)保存為字典（ dict ），這樣可以方便地添加用戶需要的任何數(shù)據(jù)。某些數(shù)據(jù)是為數(shù)據(jù)庫內(nèi)部管理而保留的，為了明確區(qū)分，可以這樣約定：以下劃線開頭的特殊字段由數(shù)據(jù)庫內(nèi)部維護，類似于私有成員，用戶不應(yīng)該自己去修改它們。這也是 Python 社區(qū)普遍遵循的約定。

此外，節(jié)點和邊存在互相引用的關(guān)系。目前我們知道邊會引用到兩端的節(jié)點，后面還會看到，為了提高效率，節(jié)點也會引用到邊。如果僅僅在內(nèi)存中維護它們的關(guān)系，那么使用指針訪問是很直觀的，但數(shù)據(jù)庫必須考慮到序列化到磁盤的問題，這時指針就不再好用了。

為此，最好按照數(shù)據(jù)庫的一般要求，為每個節(jié)點維護一個主鍵（ _id ），用主鍵來描述它們之間的關(guān)聯(lián)關(guān)系。

我們第一步要把數(shù)據(jù)庫的模型建立起來。為了測試目的，我們使用一個最簡單的數(shù)據(jù)庫模型，它只包含兩個節(jié)點和一條邊，如下所示：

按照 TDD 的原則，首先編寫測試：

與原文一樣，我們把數(shù)據(jù)庫管理接口命名為 Dagoba 。目前，能夠想到的最簡單的測試是確認(rèn)節(jié)點和邊是否已經(jīng)添加到數(shù)據(jù)庫中：

assert_item 是一個輔助方法，用于檢查字典是否包含預(yù)期的字段。相信大家都能想到該如何實現(xiàn)，這里就不再列出了，讀者可參考 Github 上的完整源碼。

現(xiàn)在，測試是失敗的。用最簡單的辦法實現(xiàn)數(shù)據(jù)庫：

需要注意的是，不管添加節(jié)點還是查詢，程序都使用了拷貝后的數(shù)據(jù)副本，而不是直接使用原始數(shù)據(jù)。為什么要這樣做？因為字典是可變的，用戶可以在任何時候修改其中的內(nèi)容，如果數(shù)據(jù)庫不知道數(shù)據(jù)已經(jīng)變化，就很容易發(fā)生難以追蹤的一致性問題，最糟糕的情況下會使得數(shù)據(jù)內(nèi)容徹底混亂。

拷貝數(shù)據(jù)可以避免上述問題，代價則是需要占用更多內(nèi)存和處理時間。對于數(shù)據(jù)庫來說，通常查詢次數(shù)要遠(yuǎn)遠(yuǎn)多于修改，所以這個代價是可以接受的。

現(xiàn)在測試應(yīng)該正常通過了。為了讓它更加完善，我們可以再測試一些邊緣情況，看看數(shù)據(jù)庫能否正確處理異常數(shù)據(jù)，比如：

例如，如果用戶嘗試添加重復(fù)主鍵，我們預(yù)期應(yīng)拋出 ValueError 異常。因此編寫測試如下：

為了滿足以上測試，代碼需要稍作修改。特別是按照 id 查找主鍵是個常用操作，通過遍歷的方法效率太低了，最好是能夠通過主鍵直接訪問。因此在數(shù)據(jù)庫中再增加一個字典：

完整代碼請參考 Github 倉庫。

在上個步驟，我們在初始化數(shù)據(jù)庫時為節(jié)點明確指定了主鍵。按照數(shù)據(jù)庫設(shè)計的一般原則，主鍵最好是不具有業(yè)務(wù)含義的代理主鍵（ Surrogate key ），用戶不應(yīng)該關(guān)心它具體的值是什么，因此讓數(shù)據(jù)庫去管理主鍵通常是更為合理的。當(dāng)然，在部分場景下——比如導(dǎo)入外部數(shù)據(jù)——明確指定主鍵仍然是有用的。

為了同時支持這些要求，我們這樣約定：字段 _id 表示節(jié)點的主鍵，如果用戶指定了該字段，則使用用戶設(shè)置的值（當(dāng)然，用戶有責(zé)任保證它們不會重復(fù)）；否則，由數(shù)據(jù)庫自動為它分配一個主鍵。

如果主鍵是數(shù)據(jù)庫生成的，事先無法預(yù)知它的值是什么，而邊（ edge ）必須指定它所指向的節(jié)點，因此必須在主鍵生成后才能添加。由于這個原因，在動態(tài)生成主鍵的情況下，數(shù)據(jù)庫的初始化會略微復(fù)雜一些。還是先寫一個測試：

為支持此功能，我們在數(shù)據(jù)庫中添加一個內(nèi)部字段 _next_id 用于生成主鍵，并讓 add_node 方法返回新生成的主鍵：

接下來，再確認(rèn)一下邊是否可以正常訪問：

運行測試，一切正常。這個步驟很輕松地完成了，不過兩個測試（ DbModelTest 和 PrimaryKeyTest ）出現(xiàn)了一些重復(fù)代碼，比如 get_item 。我們可以把這些公用代碼提取出來。由于 get_item 內(nèi)部調(diào)用了 TestCase.assertXXX 等方法，看起來應(yīng)該使用繼承，但從 TestCase 派生基類容易引起一些潛在的問題，所以我轉(zhuǎn)而使用另一個技巧 Mixin ：

實現(xiàn)數(shù)據(jù)庫模型之后，接下來就要考慮如何查詢它了。

在設(shè)計查詢時要考慮幾個問題。對于圖的訪問來說，幾乎總是由某個節(jié)點（或符合條件的某一類節(jié)點）開始，從與它相鄰的邊跳轉(zhuǎn)到其他節(jié)點，依次類推。所以鏈?zhǔn)秸{(diào)用對查詢來說是一種很自然的風(fēng)格。舉例來說，要知道 Tom 的孫子養(yǎng)了幾只貓，可以使用類似這樣的查詢：

可以想象，以上每個方法都應(yīng)該返回符合條件的節(jié)點集合。這種實現(xiàn)是很直觀的，不過存在一個潛在的問題：很多時候用戶只需要一小部分結(jié)果，如果它總是不計代價地給我們一個巨大的集合，會造成極大的浪費。比如以下查詢：

為了避免不必要的浪費，我們需要另外一種機制，也就是通常所稱的“懶式查詢”或“延遲查詢”。它的基本思想是，當(dāng)我們調(diào)用查詢方法時，它只是把查詢條件記錄下來，而并不立即返回結(jié)果，直到明確調(diào)用某些方法時才真正去查詢數(shù)據(jù)庫。

如果讀者比較熟悉流行的 Python ORM，比如 SqlAlchemy 或者 Django ORM 的話，會知道它們幾乎都是懶式查詢的，要調(diào)用 list(result) 或者 result[0:10] 這樣的方法才能得到具體的查詢結(jié)果。

在 Dagoba 中把觸發(fā)查詢的方法定義為 run 。也就是說，以下查詢執(zhí)行到 run 時才真正去查找數(shù)據(jù)：

和懶式查詢（ Lazy Query ）相對應(yīng)的，直接返回結(jié)果的方法一般稱作主動查詢（ Eager Query ）。主動查詢和懶式查詢的內(nèi)在查找邏輯基本上是相同的，區(qū)別只在于觸發(fā)機制不同。由于主動查詢實現(xiàn)起來更加簡單，出錯也更容易排查，因此我們先從主動查詢開始實現(xiàn)。

還是從測試開始。前面測試所用的簡單數(shù)據(jù)庫數(shù)據(jù)太少，難以滿足查詢要求，所以這一步先來創(chuàng)建一個更復(fù)雜的數(shù)據(jù)模型：

此關(guān)系的復(fù)雜之處之一在于反向關(guān)聯(lián)：如果 A 是 B 的哥哥，那么 B 就是 A 的弟弟/妹妹，為了查詢到他們彼此之間的關(guān)系，正向關(guān)聯(lián)和反向關(guān)聯(lián)都需要存在，因此在初始化數(shù)據(jù)庫時需要定義的邊數(shù)量會很多。

當(dāng)然，父子之間也存在反向關(guān)聯(lián)的問題，為了讓問題稍微簡化一些，我們目前只需要向下（子孫輩）查找，可以稍微減少一些關(guān)聯(lián)數(shù)量。

因此，我們定義數(shù)據(jù)模型如下。為了減少重復(fù)工作，我們通過 _backward 字段定義反向關(guān)聯(lián)，而數(shù)據(jù)庫內(nèi)部為了查詢方便，需要把它維護成兩條邊：

然后，測試一個最簡單的查詢，比如查找某人的所有孫輩：

這里 outcome/income 分別表示從某個節(jié)點出發(fā)、或到達(dá)它的節(jié)點集合。在原作者的代碼中把上述方法稱為 out/in 。當(dāng)然這樣看起來更加簡潔，可惜的是 in 在 Python 中是個關(guān)鍵字，無法作為函數(shù)名。我也考慮過加個下劃線比如 out_.in_ 這種形式，但看起來也有點怪異，權(quán)衡之后還是使用了稍微啰嗦一點的名稱。

現(xiàn)在我們可以開始定義查詢接口了。在前面已經(jīng)說過，我們計劃分別實現(xiàn)兩種查詢，包括主動查詢（ Eager Query ）以及延遲查詢（ Lazy Query ）。

它們的內(nèi)在查詢邏輯是相通的，看起來似乎可以使用繼承。不過遵循 YAGNI 原則，目前先不這樣做，而是只定義兩個新類，在滿足測試的基礎(chǔ)上不斷擴展。以后我們會看到，與繼承相比，把共同的邏輯放到數(shù)據(jù)庫本身其實是更為合理的。

接下來實現(xiàn)訪問節(jié)點的方法。由于 EagerQuery 調(diào)用查詢方法會立即返回結(jié)果，我們把結(jié)果記錄在 _result 內(nèi)部字段中。雖然 node 方法只返回單個結(jié)果，但考慮到其他查詢方法幾乎都是返回集合，為統(tǒng)一起見，讓它也返回集合，這樣可以避免同時支持集合與單結(jié)果的分支處理，讓代碼更加簡潔、不容易出錯。此外，如果查詢對象不存在的話，我們只返回空集合，并不視為一個錯誤。

查詢輸入/輸出節(jié)點的方法實現(xiàn)類似這樣：

查找節(jié)點的核心邏輯在數(shù)據(jù)庫本身定義：

以上使用了內(nèi)部定義的一些輔助查詢方法。用類似的邏輯再定義 income ，它們的實現(xiàn)都很簡單，讀者可以直接參考源碼，此處不再贅述。

在此步驟的最后，我們再實現(xiàn)一個優(yōu)化。當(dāng)多次調(diào)用查詢方法后，結(jié)果可能會返回重復(fù)的數(shù)據(jù)，很多時候這是不必要的。就像關(guān)系數(shù)據(jù)庫通常支持 unique/distinct 一樣，我們也希望 Dagoba 能夠過濾重復(fù)的數(shù)據(jù)。

假設(shè)我們要查詢某人所有孩子的祖父，顯然不管有多少孩子，他們的祖父應(yīng)該是同一個人。因此編寫測試如下：

現(xiàn)在來實現(xiàn) unique 。我們只要按照主鍵把重復(fù)數(shù)據(jù)去掉即可：

在上個步驟，初始化數(shù)據(jù)庫指定了雙向關(guān)聯(lián)，但并未測試它們。因為我們還沒有編寫代碼去支持它們，現(xiàn)在增加一個測試，它應(yīng)該是失敗的：

運行測試，的確失敗了。我們看看要如何支持它?；叵胍幌?，當(dāng)從邊查找節(jié)點時，使用的是以下方法：

這里也有一個潛在的問題：調(diào)用 self.edges 意味著遍歷所有邊，當(dāng)數(shù)據(jù)庫內(nèi)容較多時，這是巨大的浪費。為了提高性能，我們可以把與節(jié)點相關(guān)的邊記錄在節(jié)點本身，這樣要查找邊只要看節(jié)點本身即可。在初始化時定義出入邊的集合：

在添加邊時，我們要同時把它們對應(yīng)的關(guān)系同時更新到節(jié)點，此外還要維護反向關(guān)聯(lián)。這涉及對字典內(nèi)容的部分復(fù)制，先編寫一個輔助方法：

然后，將添加邊的實現(xiàn)修改如下：

這里的代碼同時添加正向關(guān)聯(lián)和反向關(guān)聯(lián)。有的朋友可能會注意到代碼略有重復(fù)，是的，但是重復(fù)僅出現(xiàn)在該函數(shù)內(nèi)部，本著“三則重構(gòu)”的原則，暫時不去提取代碼。

實現(xiàn)之后，前面的測試就可以正常通過了。

在這個步驟中，我們來實現(xiàn)延遲查詢（ Lazy Query ）。

延遲查詢的要求是，當(dāng)調(diào)用查詢方法時并不立即執(zhí)行，而是推遲到調(diào)用特定方法，比如 run 時才執(zhí)行整個查詢，返回結(jié)果。

延遲查詢的實現(xiàn)要比主動查詢復(fù)雜一些。為了實現(xiàn)延遲查詢，查詢方法的實現(xiàn)不能直接返回結(jié)果，而是記錄要執(zhí)行的動作以及傳入的參數(shù)，到調(diào)用 run 時再依次執(zhí)行前面記錄下來的內(nèi)容。

如果你去看作者的實現(xiàn)，會發(fā)現(xiàn)他是用一個數(shù)據(jù)結(jié)構(gòu)記錄執(zhí)行操作和參數(shù)，此外還有一部分邏輯用來分派對每種結(jié)構(gòu)要執(zhí)行的動作。這樣當(dāng)然是可行的，但數(shù)據(jù)處理和分派部分的實現(xiàn)會比較復(fù)雜，也容易出錯。

本文的實現(xiàn)則選擇了另外一種不同的方法：使用 Python 的內(nèi)部函數(shù)機制，把一連串查詢變換成一組函數(shù)，每個函數(shù)取上個函數(shù)的執(zhí)行結(jié)果作為輸入，最后一個函數(shù)的輸出就是整個查詢的結(jié)果。由于內(nèi)部函數(shù)同時也是閉包，盡管每個查詢的參數(shù)形式各不相同，但是它們都可以被閉包“捕獲”而成為內(nèi)部變量，所以這些內(nèi)部函數(shù)可以采用統(tǒng)一的形式，無需再針對每種查詢設(shè)計額外的數(shù)據(jù)結(jié)構(gòu)，因而執(zhí)行過程得到了很大程度的簡化。

首先還是來編寫測試。 LazyQueryTest 和 EagerQueryTest 測試用例幾乎是完全相同的（是的，兩種查詢只在于內(nèi)部實現(xiàn)機制不同，它們的調(diào)用接口幾乎是完全一致的）。

因此我們可以把 EagerQueryTest 的測試原樣不變拷貝到 LazyQueryTest 中。當(dāng)然拷貝粘貼不是個好注意，對于比較冗長而固定的初始化部分，我們可以把它提取出來作為兩個測試共享的公共函數(shù)。讀者可參考代碼中的 step04_lazy_query/tests/test_lazy_query.py 部分。

程序把查詢函數(shù)的串行執(zhí)行稱為管道（ pipeline ），用一個變量來記錄它：

然后依次實現(xiàn)各個調(diào)用接口。每種接口的實現(xiàn)都是類似的：用內(nèi)部函數(shù)執(zhí)行真正的查詢邏輯，再把這個函數(shù)添加到 pipeline 調(diào)用鏈中。比如 node 的實現(xiàn)類似下面：

其他接口的實現(xiàn)也與此類似。最后， run 函數(shù)負(fù)責(zé)執(zhí)行所有查詢，返回最終結(jié)果；

完成上述實現(xiàn)后執(zhí)行測試，確保我們的實現(xiàn)是正確的。

在前面我們說過，延遲查詢與主動查詢相比，最大的優(yōu)勢是對于許多查詢可以按需要訪問，不需要每個步驟都返回完整結(jié)果，從而提高性能，節(jié)約查詢時間。比如說，對于下面的查詢：

以上查詢的意思是從孫輩中找到一個符合條件的節(jié)點即可。對該查詢而言，主動查詢會在調(diào)用 outcome('son') 時就遍歷所有節(jié)點，哪怕最后一步只需要第一個結(jié)果。而延遲查詢?yōu)榱颂岣咝?，?yīng)在找到符合條件的結(jié)果后立即停止。

目前我們尚未實現(xiàn) take 方法。老規(guī)矩，先添加測試：

主動查詢的 take 實現(xiàn)比較簡單，我們只要從結(jié)果中返回前 n 條記錄：

延遲查詢的實現(xiàn)要復(fù)雜一些。為了避免不必要的查找，返回結(jié)果不應(yīng)該是完整的列表（ list ），而應(yīng)該是個按需返回的可迭代對象，我們用內(nèi)置函數(shù) next 來依次返回前 n 個結(jié)果：

寫完后運行測試，確保它們是正確的。

從外部接口看，主動查詢和延遲查詢幾乎是完全相同的，所以用單純的數(shù)據(jù)測試很難確認(rèn)后者的效率一定比前者高，用訪問時間來測試也并不可靠。為了測試效率，我們引入一個節(jié)點訪問次數(shù)的概念，如果延遲查詢效率更高的話，那么它應(yīng)該比主動查詢訪問節(jié)點的次數(shù)更少。

為此，編寫如下測試：

我們?yōu)? Dagoba 類添加一個成員來記錄總的節(jié)點訪問次數(shù)，以及兩個輔助方法，分別用于獲取和重置訪問次數(shù)：

然后瀏覽代碼，查找修改點。增加計數(shù)主要在從邊查找節(jié)點的時候，因此修改部分如下：

此外還有 income/outcome 方法，修改都很簡單，這里就不再列出。

實現(xiàn)后再次運行測試。測試通過，表明延遲查詢確實在效率上優(yōu)于主動查詢。

不像關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)那樣固定，圖的形式可以千變?nèi)f化，查詢機制也必須足夠靈活。從原理上講，所有查詢無非是從某個節(jié)點出發(fā)按照特定方向搜索，因此用 node/income/outcome 這三個方法幾乎可以組合出任意所需的查詢。

但對于復(fù)雜查詢，寫出的代碼有時會顯得較為瑣碎和冗長，對于特定領(lǐng)域來說，往往存在更為簡潔的名稱，例如：母親的兄弟可簡稱為舅舅。對于這些場景，如果能夠類似 DSL （領(lǐng)域特定語言）那樣允許用戶根據(jù)專業(yè)要求自行擴展，從而簡化查詢，方便閱讀，無疑會更為友好。

如果讀者去看原作者的實現(xiàn)，會發(fā)現(xiàn)他是用一種特殊語法 addAlias 來定義自己想要的查詢，調(diào)用方法時再進(jìn)行查詢以確定要執(zhí)行的內(nèi)容，其接口和內(nèi)部實現(xiàn)都是相當(dāng)復(fù)雜的。

而我希望有更簡單的方法來實現(xiàn)這一點。所幸 Python 是一種高度動態(tài)的語言，允許在運行時向類中增加新的成員，因此做到這一點可能比預(yù)想的還要簡單。

為了驗證這一點，編寫測試如下：

無需 Dagoba 的實現(xiàn)做任何改動，測試就可以通過了！其實我們要做的就是動態(tài)添加一個自定義的成員函數(shù)，按照 Python 對象機制的要求，成員函數(shù)的第一個成員應(yīng)該是名為 self 的參數(shù)，但這里已經(jīng)是在 UnitTest 的內(nèi)部，為了和測試類本身的 self 相區(qū)分，新函數(shù)的參數(shù)增加了一個下劃線。

此外，函數(shù)應(yīng)返回其所屬的對象，這是為了鏈?zhǔn)秸{(diào)用所要求的。我們看到，動態(tài)語言的靈活性使得添加新語法變得非常簡單。

到此，一個初具規(guī)模的圖數(shù)據(jù)庫就形成了。

和原文相比，本文還缺少一些內(nèi)容，比如如何將數(shù)據(jù)庫序列化到磁盤。不過相信讀者都看到了，我們的數(shù)據(jù)庫內(nèi)部結(jié)構(gòu)基本上是簡單的原生數(shù)據(jù)結(jié)構(gòu)（列表+字典），因此序列化無論用 pickle 或是 JSON 之類方法都應(yīng)該是相當(dāng)簡單的。有興趣的讀者可以自行完成它們。

我們的圖數(shù)據(jù)庫實現(xiàn)為了提高查詢性能，在節(jié)點內(nèi)部存儲了邊的指針（或者說引用）。這樣做的好處是，無論數(shù)據(jù)庫有多大，從一個節(jié)點到相鄰節(jié)點的訪問是常數(shù)時間，因此數(shù)據(jù)訪問的效率非常高。

但一個潛在的問題是，如果數(shù)據(jù)庫規(guī)模非常大，已經(jīng)無法整個放在內(nèi)存中，或者出于安全性等原因要實現(xiàn)分布式訪問的話，那么指針就無法使用了，必須要考慮其他機制來解決這個問題。分布式數(shù)據(jù)庫無論采用何種數(shù)據(jù)模型都是一個棘手的問題，在本文中我們沒有涉及。有興趣的讀者也可以考慮 500lines 系列中關(guān)于分布式和集群算法的其他一些文章。

本文的實現(xiàn)和系列中其他數(shù)據(jù)庫類似，采用 Python 作為實現(xiàn)語言，而原作者使用的是 JavaScript ，這應(yīng)該和作者的背景有關(guān)。我相信對于大多數(shù)開發(fā)者來說， Python 的對象機制比 JavaScript 基于原型的語法應(yīng)該是更容易閱讀和理解的。

當(dāng)然，原作者的版本比本文版本在實現(xiàn)上其實是更為完善的，靈活性也更好。如果想要更為優(yōu)雅的實現(xiàn)，我們可以考慮使用 Python 元編程，那樣會更接近于作者的實現(xiàn)，但也會讓程序的復(fù)雜性大為增加。如果讀者有興趣，不妨對照著去讀讀原作者的版本。

python可視化數(shù)據(jù)分析常用圖大集合（收藏）

python數(shù)據(jù)分析常用圖大集合：包含折線圖、直方圖、垂直條形圖、水平條形圖、餅圖、箱線圖、熱力圖、散點圖、蜘蛛圖、二元變量分布、面積圖、六邊形圖等12種常用可視化數(shù)據(jù)分析圖，后期還會不斷的收集整理，請關(guān)注更新！

以下默認(rèn)所有的操作都先導(dǎo)入了numpy、pandas、matplotlib、seaborn

一、折線圖

折線圖可以用來表示數(shù)據(jù)隨著時間變化的趨勢

Matplotlib

plt.plot(x,?y)

plt.show()

Seaborn

df?=?pd.DataFrame({'x':?x,?'y':?y})

sns.lineplot(x="x",?y="y",?data=df)

plt.show()

二、直方圖

直方圖是比較常見的視圖，它是把橫坐標(biāo)等分成了一定數(shù)量的小區(qū)間，然后在每個小區(qū)間內(nèi)用矩形條（bars）展示該區(qū)間的數(shù)值

Matplotlib

Seaborn

三、垂直條形圖

條形圖可以幫我們查看類別的特征。在條形圖中，長條形的長度表示類別的頻數(shù)，寬度表示類別。

Matplotlib

Seaborn

1plt.show()

四、水平條形圖

五、餅圖

六、箱線圖

箱線圖由五個數(shù)值點組成：最大值 (max)、最小值 (min)、中位數(shù) (median) 和上下四分位數(shù) (Q3, Q1)。

可以幫我們分析出數(shù)據(jù)的差異性、離散程度和異常值等。

Matplotlib

Seaborn

七、熱力圖

力圖，英文叫 heat map，是一種矩陣表示方法，其中矩陣中的元素值用顏色來代表，不同的顏色代表不同大小的值。通過顏色就能直觀地知道某個位置上數(shù)值的大小。

通過 seaborn 的 heatmap 函數(shù)，我們可以觀察到不同年份，不同月份的乘客數(shù)量變化情況，其中顏色越淺的代表乘客數(shù)量越多

八、散點圖

散點圖的英文叫做 scatter plot，它將兩個變量的值顯示在二維坐標(biāo)中，非常適合展示兩個變量之間的關(guān)系。

Matplotlib

Seaborn

九、蜘蛛圖

蜘蛛圖是一種顯示一對多關(guān)系的方法，使一個變量相對于另一個變量的顯著性是清晰可見

十、二元變量分布

二元變量分布可以看兩個變量之間的關(guān)系

十一、面積圖

面積圖又稱區(qū)域圖，強調(diào)數(shù)量隨時間而變化的程度，也可用于引起人們對總值趨勢的注意。

堆積面積圖還可以顯示部分與整體的關(guān)系。折線圖和面積圖都可以用來幫助我們對趨勢進(jìn)行分析，當(dāng)數(shù)據(jù)集有合計關(guān)系或者你想要展示局部與整體關(guān)系的時候，使用面積圖為更好的選擇。

十二、六邊形圖

六邊形圖將空間中的點聚合成六邊形，然后根據(jù)六邊形內(nèi)部的值為這些六邊形上色。

原文至：

Python 里為什么函數(shù)可以返回一個函數(shù)內(nèi)部定義的函數(shù)

“在Python中，函數(shù)本身也是對象”

這一本質(zhì)。那不妨慢慢來，從最基本的概念開始，討論一下這個問題：

1. Python中一切皆對象

這恐怕是學(xué)習(xí)Python最有用的一句話。想必你已經(jīng)知道Python中的list, tuple, dict等內(nèi)置數(shù)據(jù)結(jié)構(gòu)，當(dāng)你執(zhí)行：

alist = [1, 2, 3]

時，你就創(chuàng)建了一個列表對象，并且用alist這個變量引用它：

當(dāng)然你也可以自己定義一個類:

class House(object):

def __init__(self, area, city):

self.area = area

self.city = city

def sell(self, price):

[...] #other code

return price

然后創(chuàng)建一個類的對象：

house = House(200, 'Shanghai')

OK，你立馬就在上海有了一套200平米的房子，它有一些屬性(area, city)，和一些方法(__init__, self)：

2. 函數(shù)是第一類對象

和list, tuple, dict以及用House創(chuàng)建的對象一樣，當(dāng)你定義一個函數(shù)時，函數(shù)也是對象：

def func(a, b):

return a+b

在全局域，函數(shù)對象被函數(shù)名引用著，它接收兩個參數(shù)a和b，計算這兩個參數(shù)的和作為返回值。

所謂第一類對象，意思是可以用標(biāo)識符給對象命名，并且對象可以被當(dāng)作數(shù)據(jù)處理，例如賦值、作為參數(shù)傳遞給函數(shù)，或者作為返回值return 等

因此，你完全可以用其他變量名引用這個函數(shù)對象：

add = func

這樣，你就可以像調(diào)用func(1, 2)一樣，通過新的引用調(diào)用函數(shù)了：

print func(1, 2)

print add(1, 2) #the same as func(1, 2)

或者將函數(shù)對象作為參數(shù)，傳遞給另一個函數(shù)：

def caller_func(f):

return f(1, 2)

if __name__ == "__main__":

print caller_func(func)

可以看到，

函數(shù)對象func作為參數(shù)傳遞給caller_func函數(shù)，傳參過程類似于一個賦值操作f=func；

于是func函數(shù)對象，被caller_func函數(shù)作用域中的局部變量f引用，f實際指向了函數(shù)func；cc

當(dāng)執(zhí)行return f(1, 2)的時候，相當(dāng)于執(zhí)行了return func(1, 2)；

因此輸出結(jié)果為3。

3. 函數(shù)對象 vs 函數(shù)調(diào)用

無論是把函數(shù)賦值給新的標(biāo)識符，還是作為參數(shù)傳遞給新的函數(shù)，針對的都是函數(shù)對象本身，而不是函數(shù)的調(diào)用。

用一個更加簡單，但從外觀上看，更容易產(chǎn)生混淆的例子來說明這個問題。例如定義了下面這個函數(shù)：

def func():

return "hello,world"

然后分別執(zhí)行兩次賦值：

ref1 = func #將函數(shù)對象賦值給ref1

ref2 = func() #調(diào)用函數(shù)，將函數(shù)的返回值("hello,world"字符串)賦值給ref2

很多初學(xué)者會混淆這兩種賦值，通過Python內(nèi)建的type函數(shù)，可以查看一下這兩次賦值的結(jié)果：

In [4]: type(ref1)

Out[4]: function

In [5]: type(ref2)

Out[5]: str

可以看到，ref1引用了函數(shù)對象本身，而ref2則引用了函數(shù)的返回值。通過內(nèi)建的callable函數(shù)，可以進(jìn)一步驗證ref1是可調(diào)用的，而ref2是不可調(diào)用的：

In [9]: callable(ref1)

Out[9]: True

In [10]: callable(ref2)

Out[10]: False

傳參的效果與之類似。

4. 閉包LEGB法則

所謂閉包，就是將組成函數(shù)的語句和這些語句的執(zhí)行環(huán)境打包在一起時，得到的對象

聽上去的確有些復(fù)雜，還是用一個栗子來幫助理解一下。假設(shè)我們在foo.py模塊中做了如下定義：

#foo.py

filename = "foo.py"

def call_func(f):

return f() #如前面介紹的，f引用一個函數(shù)對象，然后調(diào)用它

在另一個func.py模塊中，寫下了這樣的代碼：

#func.py

import foo #導(dǎo)入foo.py

filename = "func.py"

def show_filename():

return "filename: %s" % filename

if __name__ == "__main__":

print foo.call_func(show_filename) #注意：實際發(fā)生調(diào)用的位置，是在foo.call_func函數(shù)中

當(dāng)我們用python func.py命令執(zhí)行func.py時輸出結(jié)果為：

chiyu@chiyu-PC:~$ python func.py

filename:func.py

很顯然show_filename()函數(shù)使用的filename變量的值，是在與它相同環(huán)境(func.py模塊)中定義的那個。盡管foo.py模塊中也定義了同名的filename變量，而且實際調(diào)用show_filename的位置也是在foo.py的call_func內(nèi)部。

而對于嵌套函數(shù)，這一機制則會表現(xiàn)的更加明顯：閉包將會捕捉內(nèi)層函數(shù)執(zhí)行所需的整個環(huán)境：

#enclosed.py

import foo

def wrapper():

filename = "enclosed.py"

def show_filename():

return "filename: %s" % filename

print foo.call_func(show_filename) #輸出：filename: enclosed.py

實際上，每一個函數(shù)對象，都有一個指向了該函數(shù)定義時所在全局名稱空間的__globals__屬性：

#show_filename inside wrapper

#show_filename.__globals__

{

'__builtins__': module '__builtin__' (built-in), #內(nèi)建作用域環(huán)境

'__file__': 'enclosed.py',

'wrapper': function wrapper at 0x7f84768b6578, #直接外圍環(huán)境

'__package__': None,

'__name__': '__main__',

'foo': module 'foo' from '/home/chiyu/foo.pyc', #全局環(huán)境

'__doc__': None

}

當(dāng)代碼執(zhí)行到show_filename中的return "filename: %s" % filename語句時，解析器按照下面的順序查找filename變量：

Local - 本地函數(shù)(show_filename)內(nèi)部，通過任何方式賦值的，而且沒有被global關(guān)鍵字聲明為全局變量的filename變量；

Enclosing - 直接外圍空間(上層函數(shù)wrapper)的本地作用域，查找filename變量(如果有多層嵌套，則由內(nèi)而外逐層查找，直至最外層的函數(shù))；

Global - 全局空間(模塊enclosed.py)，在模塊頂層賦值的filename變量；

Builtin - 內(nèi)置模塊(__builtin__)中預(yù)定義的變量名中查找filename變量；

在任何一層先找到了符合要求的filename變量，則不再向更外層查找。如果直到Builtin層仍然沒有找到符合要求的變量，則拋出NameError異常。這就是變量名解析的：LEGB法則。

總結(jié)：

閉包最重要的使用價值在于：封存函數(shù)執(zhí)行的上下文環(huán)境；

閉包在其捕捉的執(zhí)行環(huán)境(def語句塊所在上下文)中，也遵循LEGB規(guī)則逐層查找，直至找到符合要求的變量，或者拋出異常。

5. 裝飾器語法糖(syntax sugar)

那么閉包和裝飾器又有什么關(guān)系呢？

上文提到閉包的重要特性：封存上下文，這一特性可以巧妙的被用于現(xiàn)有函數(shù)的包裝，從而為現(xiàn)有函數(shù)更加功能。而這就是裝飾器。

還是舉個例子，代碼如下：

#alist = [1, 2, 3, ..., 100] -- 1+2+3+...+100 = 5050

def lazy_sum():

return reduce(lambda x, y: x+y, alist)

我們定義了一個函數(shù)lazy_sum，作用是對alist中的所有元素求和后返回。alist假設(shè)為1到100的整數(shù)列表：

alist = range(1, 101)

但是出于某種原因，我并不想馬上返回計算結(jié)果，而是在之后的某個地方，通過顯示的調(diào)用輸出結(jié)果。于是我用一個wrapper函數(shù)對其進(jìn)行包裝：

def wrapper():

alist = range(1, 101)

def lazy_sum():

return reduce(lambda x, y: x+y, alist)

return lazy_sum

lazy_sum = wrapper() #wrapper() 返回的是lazy_sum函數(shù)對象

if __name__ == "__main__":

lazy_sum() #5050

這是一個典型的Lazy Evaluation的例子。我們知道，一般情況下，局部變量在函數(shù)返回時，就會被垃圾回收器回收，而不能再被使用。但是這里的alist卻沒有，它隨著lazy_sum函數(shù)對象的返回被一并返回了(這個說法不準(zhǔn)確，實際是包含在了lazy_sum的執(zhí)行環(huán)境中，通過__globals__)，從而延長了生命周期。

當(dāng)在if語句塊中調(diào)用lazy_sum()的時候，解析器會從上下文中(這里是Enclosing層的wrapper函數(shù)的局部作用域中)找到alist列表，計算結(jié)果，返回5050。

當(dāng)你需要動態(tài)的給已定義的函數(shù)增加功能時，比如：參數(shù)檢查，類似的原理就變得很有用：

def add(a, b):

return a+b

這是很簡單的一個函數(shù)：計算a+b的和返回，但我們知道Python是 動態(tài)類型+強類型 的語言，你并不能保證用戶傳入的參數(shù)a和b一定是兩個整型，他有可能傳入了一個整型和一個字符串類型的值：

In [2]: add(1, 2)

Out[2]: 3

In [3]: add(1.2, 3.45)

Out[3]: 4.65

In [4]: add(5, 'hello')

---------------------------------------------------------------------------

TypeError Traceback (most recent call last)

/home/chiyu/ipython-input-4-f2f9e8aa5eae in module()

---- 1 add(5, 'hello')

/home/chiyu/ipython-input-1-02b3d3d6caec in add(a, b)

1 def add(a, b):

---- 2 return a+b

TypeError: unsupported operand type(s) for +: 'int' and 'str'

于是，解析器無情的拋出了一個TypeError異常。

動態(tài)類型：在運行期間確定變量的類型，python確定一個變量的類型是在你第一次給他賦值的時候；

強類型：有強制的類型定義，你有一個整數(shù)，除非顯示的類型轉(zhuǎn)換，否則絕不能將它當(dāng)作一個字符串(例如直接嘗試將一個整型和一個字符串做+運算)；

因此，為了更加優(yōu)雅的使用add函數(shù)，我們需要在執(zhí)行+運算前，對a和b進(jìn)行參數(shù)檢查。這時候裝飾器就顯得非常有用：

import logging

logging.basicConfig(level = logging.INFO)

def add(a, b):

return a + b

def checkParams(fn):

def wrapper(a, b):

if isinstance(a, (int, float)) and isinstance(b, (int, float)): #檢查參數(shù)a和b是否都為整型或浮點型

return fn(a, b) #是則調(diào)用fn(a, b)返回計算結(jié)果

#否則通過logging記錄錯誤信息，并友好退出

logging.warning("variable 'a' and 'b' cannot be added")

return

return wrapper #fn引用add，被封存在閉包的執(zhí)行環(huán)境中返回

if __name__ == "__main__":

#將add函數(shù)對象傳入，fn指向add

#等號左側(cè)的add，指向checkParams的返回值wrapper

add = checkParams(add)

add(3, 'hello') #經(jīng)過類型檢查，不會計算結(jié)果，而是記錄日志并退出

注意checkParams函數(shù)：

首先看參數(shù)fn，當(dāng)我們調(diào)用checkParams(add)的時候，它將成為函數(shù)對象add的一個本地(Local)引用；

在checkParams內(nèi)部，我們定義了一個wrapper函數(shù)，添加了參數(shù)類型檢查的功能，然后調(diào)用了fn(a, b)，根據(jù)LEGB法則，解釋器將搜索幾個作用域，并最終在(Enclosing層)checkParams函數(shù)的本地作用域中找到fn；

注意最后的return wrapper，這將創(chuàng)建一個閉包，fn變量(add函數(shù)對象的一個引用)將會封存在閉包的執(zhí)行環(huán)境中，不會隨著checkParams的返回而被回收；

當(dāng)調(diào)用add = checkParams(add)時，add指向了新的wrapper對象，它添加了參數(shù)檢查和記錄日志的功能，同時又能夠通過封存的fn，繼續(xù)調(diào)用原始的add進(jìn)行+運算。

因此調(diào)用add(3, 'hello')將不會返回計算結(jié)果，而是打印出日志：

chiyu@chiyu-PC:~$ python func.py

WARNING:root:variable 'a' and 'b' cannot be added

有人覺得add = checkParams(add)這樣的寫法未免太過麻煩，于是python提供了一種更優(yōu)雅的寫法，被稱為語法糖：

@checkParams

def add(a, b):

return a + b

這只是一種寫法上的優(yōu)化，解釋器仍然會將它轉(zhuǎn)化為add = checkParams(add)來執(zhí)行。

6. 回歸問題

def addspam(fn):

def new(*args):

print "spam,spam,spam"

return fn(*args)

return new

@addspam

def useful(a,b):

print a**2+b**2

首先看第二段代碼：

@addspam裝飾器，相當(dāng)于執(zhí)行了useful = addspam(useful)。在這里題主有一個理解誤區(qū)：傳遞給addspam的參數(shù)，是useful這個函數(shù)對象本身，而不是它的一個調(diào)用結(jié)果；

再回到addspam函數(shù)體：

return new 返回一個閉包，fn被封存在閉包的執(zhí)行環(huán)境中，不會隨著addspam函數(shù)的返回被回收；

而fn此時是useful的一個引用，當(dāng)執(zhí)行return fn(*args)時，實際相當(dāng)于執(zhí)行了return useful(*args)；

最后附上一張代碼執(zhí)行過程中的引用關(guān)系圖，希望能幫助你理解：

標(biāo)題名稱：python函數(shù)關(guān)系圖 python函數(shù)調(diào)用關(guān)系圖
網(wǎng)頁URL：http://jinyejixie.com/article26/dododcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護、品牌網(wǎng)站設(shè)計、App開發(fā)、網(wǎng)站內(nèi)鏈、品牌網(wǎng)站制作、電子商務(wù)

廣告

聲明：本網(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)