assoc命令Clojure中：的內部

Question

下面的解釋是assoc代碼：

(def assoc 
(fn assoc 
    ([map key val] (. clojure.lang.RT (assoc map key val))))) 

1. 什麼是clojure.lang.RT意思？

2. 向量/地圖上調用assoc的複雜性是什麼？

3. 訪問由assoc創建的結構的複雜性是什麼？

Answer 1

1. clojure.lang.RT是主要的Clojure運行時類。它擁有構成語言核心的大部分方法。

2. assoc對於包括向量和映射的所有關聯數據結構都是O（1）。 array-map開始爲前幾項線性，然後提升自己爲hash-map所以它也是O（1）。如果需要的話，你當然可以用不是O（1）的東西來實現關聯接口。

3. 從技術上講，通過在另一個地圖上調用assoc創建的地圖或矢量中的項目的訪問時間爲O（log32 N）。因爲這些數據結構有一個上限的〜2^32個項目的大小這留下6其中有效恆定時間的最大樹深度

Clojure的締數據結構都是O（n日誌n）的在空間（因爲它們是樹）。