clojure - assoc in 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 RunTime 类。它拥有构成语言核心的大部分方法。

2. assoc对于包括向量和映射在内的所有关联数据结构，是 O(1)。array-map从前几个项目开始是线性的，然后将自己提升为 ahash-map所以它也是 O(1) 。如果需要，您当然可以使用不是 O(1) 的东西来实现关联接口。

3. 从技术上讲，通过调用另一个地图创建的地图或矢量中的项目的访问时间assoc是 O(log32 N)。因为这些数据结构的大小上限约为 2^32 个项目，所以最大树深度为 6，这实际上是恒定的时间

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