clojure - 计算集合中元素频率的复杂性是多少？

Question

下面是 clojure 中 frequencies 的实现:

(defn frequencies
  "Returns a map from distinct items in coll to the number of times
  they appear."
  [coll]
  (persistent!
   (reduce (fn [counts x]
         (assoc! counts x (inc (get counts x 0))))
           (transient {}) coll)))

assoc! 是否被认为是突变？

在 frequencies 中 assoc! 的复杂度是多少？

此外，counts 似乎在每次迭代中被访问两次:它会导致性能下降吗？

Answer 1

assoc! 是瞬变的突变，我相信它是 O(log n) 摊销的。因此，frequencies 的整个执行是 O(n log n)。

counts 是一个本地绑定(bind)变量，所以访问它两次是没有问题的。

这是一个不使用任何多态的 freqencies 的函数式版本:

(defn frequencies-2 [coll]
  (reduce (fn [m v] (assoc m v (inc (get m v 0)))) {} coll))

这个函数式版本也是 O(n log n)，尽管由于创建和丢弃更多临时对象，它会有更多的开销(更高的常数因子)。