Clojure，替换 let 绑定中的 vars 会导致性能问题吗？

Question

假设有一个函数，它接收到一个 json 字符串，其中包含大约 100KB 的数据。该字符串被转换为一个映射，然后它不断将新键与该映射相关联并替换 let 绑定中的 var，如下所示：

(defn myfn
  [str]
  (let [j (json/read-str str)
        j (assoc-in j [:key1 :subkey1] somedata1)
        j (assoc-in j [:key2 :subkey2] somedata2)
        ....
        j (assoc-in j [:key100 :subkey100] somedata100)]
    ... do something ...))

我知道，在所有这些 let 绑定之后，j 将添加所有这些新键。这只是一个例子。我想知道在同一个 var 的大量绑定中发生了什么。

我的意思是记忆中发生的事情。那会在内存中复制 100KB 100 次吗？它会占用 100KB * 100 = 10,000KB 直到它退出该函数？或者，Clojure 足够聪明，它实际上一直在同一内存中添加新键 space？

如果你也能推荐我应该在 Clojure 参考中寻找什么来找到这个问题的答案，那就太好了。

Answer 1

Clojure 使用一种称为 trie 的数据结构，它类似于树，但只有叶节点处有数据。大多数 clojure 的持久化结构都是作为一个 trie 来实现的。

This excellent article确实解释的很详细，而且用的是向量，这里就不赘述了。我知道 S.O。最好给出内容而不是 link，但这不是一个可以在此处的答案中完全涵盖的主题，而且这篇文章做得最好，所以我只 link。

简而言之，当以某种方式修改数据结构时，会为新的 "version" 创建一个新的 trie，而不是通过一次更改将所有数据从旧的复制到新的，新结构中的节点指向现有数据。这是上述文章中显示数据共享的可视化：

所以，使用这种结构，我们共享了数据，但由于它只是一个二叉树，它可以很快变得很深，所以查找可能需要很长时间（对于一个包含 10 亿个元素的向量，到达叶节点的深度是 log₂1e9，即 30）。为了解决这个问题，clojure 使用 32 向分支因子而不是 2 向分支因子，生成的树非常浅。因此，在 clojure 中包含 10 亿个元素的相同向量只需要 log₃₂1e9，或 6 个间接级别，即可到达叶子。

我鼓励您阅读这篇文章，并查看 PersistentHashMap, and you will see references to shift + 5 in several places. This is a clever way to use bit-shifting to index into the trie (log₂32 = 5). See the second part of the article 以获取有关此的更深入的信息。

总而言之，clojure 使用高效的数据结构来实现持久化，任何以不变性为核心特征的语言都必须这样做，如果它希望获得可用的性能。

Clojure，替换 let 绑定中的 vars 会导致性能问题吗？

Clojure, replacing vars in let bindings causes performance issue?

binding

replace

var

clojure

let