我針對The Hunt For the Missing Data Type 收到了許多迴響。下面收錄了其中幾個最有趣的回應。

回應文章

• 「失落的」圖資料型別早已存在。它在 70 年代就被發明了，一篇關於 datalog 的文章。

電子郵件與留言

以下引號內的內容皆為原文照錄。

GraphBLAS

我叫 Michel Pelletier，是 GraphBLAS API 標準與 Python 綁定的貢獻者之一。

恭喜你的部落格文章登上了 Hacker News 首頁。我在那裡回覆了一些我認為對你的問題可能有幫助的資訊，不過被淹沒在大量的討論中。我注意到你有邀請大家寫信給你，所以決定直接把資訊寄給你。

你所欠缺的圖（graph）資料型別，其實就是你已經提過的矩陣（matrix）。你在部落格文章中提到了鄰接矩陣（adjacency matrices），但在文章的脈絡裡，它們只被當成一種儲存格式，而非圖本身。但圖與矩陣在概念與代數上是同構的。所有的圖，因此所有的複合資料結構，在數學上都是矩陣，而所有的矩陣也都是圖。超圖（Hypergraphs）與多重圖（Multigraphs）則是以「關聯矩陣（Incidence Matrices）」來表示，也就是透過兩個矩形矩陣來呈現節點到邊、再從邊到節點的鄰接關係。

由超級運算中心與 MIT 林肯實驗室主任 Jeremy Kepner 博士領軍的一大群研究人員所撰寫的一篇非常出色的入門論文是：

https://arxiv.org/pdf/1606.05790.pdf

用電腦把圖當成矩陣來思考的問題在於，大多數的圖是稀疏的，而大多數的矩陣函式庫（如 numpy）是稠密的。這使得使用鄰接矩陣的成本非常高，因為稠密矩陣中的絕大部分「空間」最終都是零。這極度沒有效率，也無法發揮馮·紐曼架構中典型的快取階層優勢。這兩個世界至今仍未真正匯合。

不過，圍繞高效稀疏矩陣運算、進而稀疏圖分析的研究與開發其實很多。雖然這兩者看似不同，實際上卻是同一回事：矩陣乘法就是在圖上的一次廣度優先遍歷步驟。這正是兩者同構特性的一部分。許多機器學習與人工智慧研究同時涉及稀疏矩陣與圖，而這些研究在提升兩種典範的效能方面是高度統一的。

我常被問到的一個大問題是「為什麼」。為什麼要用線性代數公式，而不是寫一個遍歷節點與邊的函式？其中一個最重要的答案，就是在超大型圖上的平行化。當圖變得非常、非常大，擁有數十億甚至數兆條邊時，你需要有效率地分割演算法的工作量。要怎麼做？為每條邊都建立一個分支（fork）？使用執行緒池（thread pool）？要如何有效率地排程工作、分割圖？現在還要在 CUDA 上做這件事……即便是最聰明的程式設計師，也幾乎不可能處理這樣的問題。

有了 GraphBLAS，圖運算就是一個線性代數公式，會被分解成一系列的矩陣乘法，你只需要寫出像是 Ax = b 這樣的式子，底層的函式庫就會想辦法在特定的目標架構上以最有效率的方式完成工作。不管是在 Chromebook 還是超級電腦上執行，程式碼都不需要改變，改變的只是機器能處理更大圖的能力。你可以把 GraphBLAS 想成一種語言，它能根據底層架構，以及你餵給它的問題的形狀與類型來進行「JIT」編譯。由於線性代數（LA）是數學、科學與工程的共通語言，這項技術自然能應用到許多現有的工作中。

所以只是想把這些資訊分享給你，祝你在這個主題上的後續探索一切順利。如果你想進一步了解，隨時歡迎找我聊聊，身為 C API 委員會的成員，推廣這個主題本來就是我工作的一部分，我也很樂於介紹它。

謝謝！

Gremlin

在這篇文章的早期草稿中，我有提到 TinkerPop，也就是 Apache 的圖運算框架，以及它的查詢語言 Gremlin。我在定稿時把它刪掉了，有好幾個人注意到了這個缺漏。以下是其中一則回應。

你提到了 Cypher，卻沒有談到 Gremlin，它是一個用於 Neo4j／TinkerPop、表達能力很強的圖查詢語言：

https://tinkerpop.apache.org/

它曾被用來驅動後來被 ShiftLeft 收購的 Joern SAST 工具，我想在金融領域也用得很多。

我上次用它來建立了一個包含 Maven 上所有軟體套件及其相互依賴關係的圖。

它與程式語言的綁定做得很好——我用的是 Python 的 Gremlin，這樣就能用熟悉的腳本語言來操作它，因為預設的 REPL／腳本語言是 Groovy，我比較不熟。

你可以在用 Gremlin 查詢圖和用 Python 進行「一般」的指令式腳本編寫之間自由切換，然後再根據結果進一步查詢。感覺相當自然。

我不太清楚它在整圖演算法方面的現況——我當時感興趣的一直是基於遍歷的查詢，而不是像中心性（centrality）這類整圖統計數據。

魔術方塊

我是透過 CodeProject 電子報的連結看到你那篇關於圖的軟體函式庫有所缺漏的文章。文章寫得非常棒。我雖然不像你寫作時諮詢的那些人那麼厲害，但還是想再提供一個例子，說明要為圖打造通用軟體函式庫有多困難。具體來說，我是一個非常鬆散的團體的一員，這個團體多年來一直用電腦來研究魔術方塊背後的數學。

魔術方塊背後的數學叫做群論（group theory），而你能對群做的一件事，就是用一種叫做凱萊圖（Cayley graphs）的圖把它描繪出來。那個自以為無所不知的 Google 是這樣描述的：「凱萊圖經常被用來透過以圖的形式呈現群的結構，讓群的抽象結構變得容易看見。當群 G 被呈現為凱萊圖時，群 G 的性質，例如它的大小或生成元數量，就變得容易檢視得多。」具體來說，魔術方塊的每一種可能狀態都可以表示為凱萊圖中的一個節點，而相鄰的節點就是那些恰好只需一步就能到達的狀態。你在文章中提到了 15 拼圖。事實上，其中一位研究魔術方塊的人就寫過一個完整且非常快速的 15 拼圖求解器。而事實也證明，15 拼圖的規模跟魔術方塊的凱萊圖比起來，根本是小巫見大巫。

無論如何，我從 1985 年就開始寫程式來研究魔術方塊。這不只是為了「解」魔術方塊，那其實相當容易。而是要針對將近 10^20 種狀態中的每一種，找出解開該狀態所需的最少步數。這個問題至今仍未解決，單純就是因為規模太過龐大。目前已經確定，任何一種狀態都可以在 20 步或 26 步內解開，取決於你如何計算「一步」。但這跟為每一種可能狀態都找出「最少步數」的解法，並不是同一回事。

無論如何，根據豐富的經驗我知道，為了以任何實際可行的方式處理這個問題，我必須開發一套相當專屬於魔術方塊的資料結構。關鍵問題在於（這裡引用你文章中的話）效能太重要了。我找不到任何符合我需求的函式庫，所以就自己動手做了。

謝謝你寫了這麼棒的一篇文章，

Jerry

我請他進一步說明「20 步或 26 步」是什麼意思，以及是否能多分享一些他使用的資料結構。他的回覆如下：

如你所猜的，是否將一次半轉算作一步或兩步，就是「怎麼算一步」最主要的例子。如果只把四分之一轉算作一步，那就叫做四分之一轉度量（quarter turn metric）。在這種度量下，任何狀態都可以在 26 步內解開。如果把四分之一轉和半轉都算作一步，那就叫做面轉度量（face turn metric）。在這種度量下，任何狀態都可以在 20 步內解開。但還有其他方式來決定什麼算作一步。魔術方塊在任何方向上都有三層。通常你只計算外層的轉動，例如頂層和底層，而不計算頂層與底層之間的中間層，或是右層與左層之間的中間層。但有時候把這些中間層的轉動也算作一步也很有趣。另一種變化是「卡軸問題」，也就是假設其中一個軸卡住了。例如，你不轉動頂面，只轉動方塊另外五個面上的層。在這種變化下，你仍然可以到達所有可能的狀態，但凱萊圖不再具有軸都沒卡住時的那種對稱性。而且，解開一個卡軸的方塊所需的步數，可能遠多於標準的 20 步或 26 步。

我認為魔術方塊並沒有什麼標準的資料結構。每個研究方塊的人都有自己的資料結構，只不過很明顯地，任何能忠實呈現方塊的資料結構，在某種程度上都必然與其他能忠實呈現方塊的資料結構同構。一個很大的區別在於，資料結構是只包含狀態，還是同時包含狀態與步法。舉例來說，連續兩次順時針轉動前面的四分之一，會得到與連續兩次逆時針轉動前面相同的狀態。在凱萊圖中，如果繼續下去，這些移動序列就會形成一個迴圈。這個迴圈是一個四步循環（4-cycle）。所以，你是要同時儲存步法與狀態，還是只儲存狀態？

我真的不知道其他人的資料結構是如何處理這些問題的。就我自己而言，我並不會明確地儲存整個凱萊圖。相反地，我儲存狀態，並為每個狀態針對每一種可能的移動儲存一個位元（bit），用來表示該步是讓你離已解狀態更遠，還是更近。在四分之一轉度量下，每個狀態有 12 個這樣的位元，在面轉度量下則有 18 個。這些位元隱含地定義了一個凱萊圖，但我並不會明確地儲存這個圖。其他研究這個問題的人會談到使用正規的移動序列，例如你可以連續兩次順時針轉動前面，但不能連續兩次逆時針轉動前面。我用我的位元做了類似但不完全相同的事情。

另一個問題是我需要一個樹狀結構，而樹可以被視為圖的一種特例。也就是說，樹就是一種圖，其中有一個節點被宣告為根節點，且圖中沒有迴圈。我必須自己打造樹狀結構。我所需要的樹狀結構是這樣產生的。一個標準的魔術方塊上有 54 個色塊。在標準的數學模型中，每個面的中心色塊是不會移動的，因此剩下 48 個會移動的色塊。在這 48 個色塊中，24 個位於 3x3 方格的角塊上，24 個位於邊塊上。角塊的色塊與邊塊的色塊是互不相交的，所以我透過為每個角塊色塊標上 A 到 X 的字母，並為每個邊塊色塊也標上 A 到 X 的字母，來表示一個方塊狀態。每個狀態因此就是一對有序的「字」，其中每個字由 24 個字母組成，且每個字母在每個字中恰好出現一次。

那我為什麼需要一棵樹呢？嗯，我需要能夠非常快速地找到這些字。這就像在拼字檢查字典中快速查找單字一樣。名義上，樹中的每個節點都需要 24 個指向樹中其他節點的指標。但與拼字檢查字典中真實的單字不同，每個字母在每個字中只能出現一次。因此，當我越接近樹的葉節點時，每個節點就會大部分都是空指標（null pointers），這對非常珍貴的記憶體來說是巨大的浪費。所以我必須打造一個樹狀結構來因應這些狀態的儲存，以實現快速檢索。沒有任何標準函式庫的常式同時夠快又夠節省記憶體。

所以基本上我有兩種疊在一起的資料結構。其中一種使用位元開關來定義方塊的凱萊圖，另一種則使用類似拼字檢查字典的樹來非常快速地定位特定狀態。而樹就只是圖的特例。

不知道這樣是否有回答到你的問題，希望對你有幫助。

Jerry

圖與知識資料庫

Hillel — 謝謝你分享對圖表示法的探索，並清楚地解釋了為什麼沒有明確的優勝者。我在想，你所提到的那些問題，是否大到足以排除其他可行的替代方案。

我首先是以 Smalltalk 程式設計師的身分，然後是以 Wiki 創造者的身分來思考這個問題。這兩者都具有一種由零碎片段組合而成、並在持續使用中保持的類圖結構。圍繞我最新 wiki 實作的小社群，非常希望能在頁面中加入圖，就像段落、圖片、大綱和表格一樣。我們已經透過使用 Dot 作為標記語言的 Graphviz 部分地實現了這一點。但這並無法像 yaml 或 csv 檔案那樣帶來運算與共享的效益。

我們最近開始採用一種做法（例如在 JavaScript 中），將圖表示為一個包含節點與關聯陣列的物件。空的圖會是這樣：

{nodes:[], rels:[]}

節點與關聯本身也是物件，各有一個表示類型的字串，以及一個用於屬性的額外物件，還有一些用來將它們串連起來的受控索引。這樣就能很方便地序列化為（無迴圈的）JSON，這是一種廣泛使用、對於以 KB 為單位的圖來說已經足夠的格式。

這些圖可以很容易地轉換為 Neo4j 物件，而我們在這方面有相當豐富的經驗。更常見的情況是，我們避免在 wiki 本身之外再維護一個資料庫。雖然我們也打造了一個簡易的 Cypher 直譯器，但發現它並沒有那麼有用。我們有一個令人驚訝的發現：我們更傾向於將許多小圖合併成一個能解決手邊問題的圖，而不是建立一個大型的 Neo4j 圖再從中查詢出解決同樣問題所需的圖。

最近，我們開始根據問題空間中的跨領域關注點，將問題拆分為「面向（aspects）」。我們可能會有數十個甚至數百個這樣的圖。我們瀏覽這些圖的方式，就像瀏覽 wiki 一樣，其中的 wiki 連結等價物，來自於辨識出同一個節點出現在尚未納入的圖中。這是一個「推薦」流程，查詢被「選擇與取消選擇推薦項目」所取代，而進行中的成果會透過在瀏覽器中執行的 Graphviz 即時呈現。

我原本在這封信的開頭寫了更完整的圖抽象描述，但後來又刪掉了，因為不確定你是否會對我們的經驗感興趣。我也可以描述一些這套方法證明有用的應用，通常都涉及社群內的某種協作問題。

如果你覺得我們的興趣有重疊之處，我很樂意繼續通信交流。

感謝並致上最誠摯的問候 — Ward

他的相關程式碼連同文件與範例可在這裡取得。後續的來信：

Hillel — 我們正在尋找代表更大問題中各個面向的小圖。這裡有一個案例，當我被請去閱讀一篇要投稿到歐洲模式（European Patterns）研討會的論文時，我選擇非常仔細地閱讀它，並將其中模式裡的每一句「關係性」語句都對映出來。這裡有一張圖，其中以黃色標示了面向之間意想不到的重疊。

這個特定的圖檢視器經歷了一段曲折的歷程：一開始是 wiki 頁面上的腳本；後來被抽取出來，成為基於 Croquet、用於線上協作的獨立網頁應用程式；然後在這裡又成為一個朝著回歸 wiki 方向的單人「solo」應用程式。它目前還不是一看就懂的工具。不過，你可以透過 wiki 頁面最後一段中的「open」連結將它叫出來，該頁面是我與一位同樣對這類探索感興趣的共同審稿人協調合作的地方。http://ward.dojo.fed.wiki/aspects-of-pattern-relations.html

另外兩個展示不同「面向」可能性的類似專案是：將一年的近期變更切碎，以及用節點-關聯註解來標註搜尋引擎的原始碼，並透過 GitHub Actions 將它們萃取為圖檔案。