2

这是frequenciesin的实现clojure：

(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!认为是突变？

assoc!里面的复杂度是frequencies多少？

此外，似乎counts每次迭代都会访问两次：它会导致性能损失吗？

4

3 回答 3

4

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

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

这是一个不使用任何多重状态的功能版本：

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

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

于 2012-10-18T07:13:42.190 回答
2

您可以使用树来存储从元素到具有 log(n) 复杂度的频率的映射（它可以是二叉搜索树、AVL、红黑树等）。选择这棵树的功能实现，即你不能改变它，而是assoc counts x freq返回一个新的数据结构，在内存中与counts. 这是一种“写时复制”。那么计算所有频率的性能将是 O(n log(n))。

于 2012-10-18T06:45:29.420 回答
1

assoc!对瞬态数据进行变异，它的性能比assoc. 这并没有真正违反不可变 Clojure 的模型（请参阅http://clojure.org/transients）。

  1. persistent!并且transient是 O(1)
  2. assoc!是 O(log32 n)，它实际上是 O(1)，因为hash-map具有 ~2^32 项大小的上限，因此最大树深度为 6

因此， 的复杂度与frequencies的大小成线性关系coll。

备注：正如@mikera 所注意到的，复杂度也frequencies将是线性的，assoc但具有更高的常数因子。

于 2012-10-23T03:52:45.047 回答