为什么在Clojure中的瞬态映射中插入1000 000个值会产生一个包含8个项目的映射？

Question

如果我尝试assoc!在瞬态向量上做1000 000 ,我将获得1000 000个元素的向量

(count
  (let [m (transient [])]
    (dotimes [i 1000000]
      (assoc! m i i)) (persistent! m)))
; => 1000000

另一方面,如果我对地图做同样的事情,它只会有8个项目

(count
  (let [m (transient {})]
    (dotimes [i 1000000]
      (assoc! m i i)) (persistent! m)))
; => 8

有没有理由发生这种情况？

Answer 1

瞬态数据类型的操作不保证它们将返回与传入的引用相同的引用.有时,实现可能决定返回一个新的(但仍然是瞬态的)映射assoc!而不是使用您传入的映射.

在上ClojureDocs页assoc!有一个很好的例子,说明这种行为:

;; The key concept to understand here is that transients are 
;; not meant to be `bashed in place`; always use the value 
;; returned by either assoc! or other functions that operate
;; on transients.

(defn merge2
  "An example implementation of `merge` using transients."
  [x y]
  (persistent! (reduce
                (fn [res [k v]] (assoc! res k v))
                (transient x)
                y)))

;; Why always use the return value, and not the original?  Because the return
;; value might be a different object than the original.  The implementation
;; of Clojure transients in some cases changes the internal representation
;; of a transient collection (e.g. when it reaches a certain size).  In such
;; cases, if you continue to try modifying the original object, the results
;; will be incorrect.

;; Think of transients like persistent collections in how you write code to
;; update them, except unlike persistent collections, the original collection
;; you passed in should be treated as having an undefined value.  Only the return
;; value is predictable.

我想重复最后一部分,因为它非常重要:您传入的原始集合应该被视为具有未定义的值.只有返回值是可预测的.

这是您的代码的修改版本,按预期工作:

(count
  (let [m (transient {})]
    (persistent!
      (reduce (fn [acc i] (assoc! acc i i))
              m (range 1000000)))))

作为旁注,你总是得到8的原因是因为Clojure喜欢使用一个clojure.lang.PersistentArrayMap(由数组支持的地图)来处理8个或更少元素的地图.一旦你超过8,它就会切换到clojure.lang.PersistentHashMap.

user=> (type '{1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a})
clojure.lang.PersistentArrayMap
user=> (type '{1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a})
clojure.lang.PersistentHashMap

一旦超过8个条目,瞬态映射就会将后备数据结构从一对(PersistentArrayMap)数组切换到一个哈希表(PersistentHashMap),此时assoc!返回一个新引用而不是仅更新旧引用.

Answer 2

最简单的解释来自Clojure文档本身(强调我的):

瞬态支持一组并行的"更改"操作,后面跟着类似的名称! - assoc !, conj!除了返回值本身是瞬态的,它们与持久对应物做的事情相同.请特别注意,瞬态不是设计为就地瞄准.您必须在下一次调用中捕获并使用返回值.