Clojure

暫態資料結構

原理

如果一棵樹在森林中倒下,它會發出聲音嗎?
如果純函數為了產生不可變的回傳值而改變某些區域資料,這樣可以嗎?

這是一個有趣的問題。Clojure 資料結構每次呼叫時都會使用變異,例如 assoc,建立一個或多個陣列並變異它們,然後再回傳它們以供之後不可變地使用。原因在於效能 - 僅使用純函數和不可變資料無法達到這麼快的速度。然而,一旦建構並共用,不可變和持續性對於穩健的程式而言至關重要。Clojure 在內部變異的事物是小型、新配置的陣列,構成其資料結構的內部節點。沒有人會看到這些陣列。

當您想要使用多個步驟初始化或轉換大型持續性資料結構時,您會遇到類似的情況,而且在較高的層級上,除了建構/轉換程式碼之外,其他程式碼都不會看到這些步驟。此處的挑戰在於轉換的來源將是現有的持續性資料結構,而函數的結果會被共用。複製到傳統的可變資料結構再複製回來會涉及 O(n) 複製,而且內部程式碼會是一團命令式混亂,與您其他 Clojure 程式碼完全不同。此外,沒有防範措施可以防止意外共用或別名化可變資料結構,特別是如果您需要呼叫輔助函數來執行工作時。簡而言之,如果您必須離開 Clojure 的模型才能加速這類程式碼,那將是一件令人遺憾的事。暫時性資料結構是此最佳化問題的解決方案,它與 Clojure 模型整合,並提供您對 Clojure 所預期的相同執行緒安全性保證。

它們如何運作

暫時性資料結構總是從現有的持續性 Clojure 資料結構建立。從 Clojure 1.1.0 開始,支援向量、雜湊映射和雜湊集合。請注意,並非所有 Clojure 資料結構都能支援此功能,但大多數都能。清單不行,因為沒有好處可得。

您可以透過呼叫 transient 來取得資料結構的暫時性「複製」。這會建立一個新的暫時性資料結構,它是來源的複製,並具有相同的效能特性。事實上,它大部分就是來源資料結構,並突顯了暫時性的第一個特點 - 建立一個暫時性資料結構是 O(1)。它與其來源共用結構,就像持續性複製共用結構一樣。

暫時性的第二個特點是建立一個暫時性資料結構不會修改來源,而且無法透過使用暫時性資料結構來修改來源。您的來源資料永遠都是不可變且持續的。

暫存支援來源的唯讀介面,也就是說,你可以呼叫暫存向量的nthgetcount和函數呼叫,就像持久向量一樣。

暫存支援來源資料結構的持久介面。assocconj等都會擲回例外,因為暫存並非持久。因此,你無法意外地將暫存洩漏到需要持久性的內容中。

暫存支援一組平行的「變更」操作,其名稱類似,後面加上 - assoc!conj!等。這些操作與其持久對應項執行相同的工作,但回傳值本身是暫存的。特別注意,暫存並非設計成在原處進行猛擊。你必須擷取並在下次呼叫中使用回傳值。如此一來,它們支援與其取代的功能性持久程式碼相同的程式碼結構。正如範例所示,這將讓你能夠輕鬆地提升程式碼效能,而無需進行結構變更。

當你完成建立結果時,你可以透過對暫存呼叫persistent!來建立持久資料結構。此操作也是 O(1)。呼叫persistent!後,不應使用暫存,且所有操作都會擲回例外。對於你可能建立的任何別名,這也是正確的。

範例

以下是非常典型的範例,一些程式碼會建立一個向量以供回傳,所有「變更」都屬於函數的區域性。請注意,使用暫存的版本具有完全相同的結構,僅

  • 對來源向量呼叫transient

  • 使用conj!而非conj

  • 在回傳時呼叫persistent!

(defn vrange [n]
  (loop [i 0 v []]
    (if (< i n)
      (recur (inc i) (conj v i))
      v)))

(defn vrange2 [n]
  (loop [i 0 v (transient [])]
    (if (< i n)
      (recur (inc i) (conj! v i))
      (persistent! v))))

;; benchmarked (Java 1.8, Clojure 1.7)
(def v (vrange 1000000))    ;; 73.7 ms
(def v2 (vrange2 1000000))  ;; 19.7 ms

喔,對了,暫存很快!

並行使用

這就是使用暫存的全部內容,但它們還有另一個重要的限制:暫存需要執行緒隔離。由於暫存操作的每個結果與前一個結果共用(可變)結構,因此如果有多個執行緒同時處理暫存,則會發生錯誤。應透過在單執行緒範圍內使用暫存,或在強制執行的架構中使用暫存,來控制特定暫存實例的使用。

在 Clojure 1.6 及更早版本中,瞬態會偵測到除了建立它們的執行緒之外的任何(讀取或寫入)使用,並擲回例外。在 1.7 中移除了該檢查,以允許在核心異步執行區塊等框架中更靈活地使用,這些框架透過其他方式強制執行單執行緒約束。

摘要

瞬態提供功能資料結構建立程式碼的高效能最佳化,可與 Clojure 的資料結構搭配使用,並提供重要的安全性保證。

  • 單路徑使用

  • 從持久資料結構中建立 O(1)

  • 與持久來源共用結構

  • 編輯階段結束時建立持久資料結構的 O(1)

  • 與功能版本相同的程式碼結構

    • 擷取回傳值,用於下一次呼叫

    • 不要原地修改

    • 非持久,因此無法保留中間值或別名

  • 回傳持久版本後無法使用

  • 快速

瞬態持久向量、雜湊映射和雜湊集合已新增至 Clojure 1.1。