clojure - Clojure中的assoc:内部构造说明

这是assoc的代码:

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

clojure.lang.RT是什么意思？

在矢量/地图上调用assoc的复杂性是什么？

访问assoc创建的结构的复杂性是什么？

最佳答案

clojure.lang.RT是Clojure RunTime主类。它具有构成语言核心的大多数方法。

assoc对于包括矢量和地图在内的所有关联数据结构均为O(1)。 array-map从头几项开始线性，然后提升为hash-map，因此也是O(1)。当然，如果需要，您可以使用非O(1)的东西来实现关联接口。

从技术上讲，通过在另一张地图上调用assoc创建的地图或矢量中项目的访问时间为O(log32 N)。由于这些数据结构在〜2 ^ 32项的大小上具有上限，因此保留了最大树深度为6的有效树长

Clojure的关联数据结构在空间中都是O(nLog n)(因为它们是树)。