clojure - 在 clojure : explanation of the internals 中关联

Question

这是assoc的代码:

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

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

2. 在矢量/ map 上调用assoc 的复杂度是多少？

3. 访问由 assoc 创建的结构的复杂性如何？

Answer 1

1. clojure.lang.RT 是主要的 Clojure RunTime 类。它具有构成该语言核心的大部分方法。

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

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

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