Clojure中的结构共享 [英] Structural Sharing in Clojure

问题描述

我不清楚Clojure中的结构共享。下面是从Clojure（Great book BTW）中获取的函数xconj。

  ;;构建一个简单的二叉搜索树递归
（defn xconj [tv] 
（cond 
（nil？t）{：val v：L nil：R nil} 
 ）{：val（：val t）：L（xconj（：L t）v）：R（：R t）} 
：如果定义了两个树t1和t2（xconj（：Rt）v）}））
  

$ b如下所示。

 （def t1（xconj（xconj（xconj nil 5）3）2））
 def t2（xconj t1 7））
  

很明显，Left子树由t1& t2

 用户> （same？（：L t1）（：L t2））
 true 
  

一个是通过在t1的左子树中插入一个新值1来创建一个新树t3，如下所示：

 （def t3（xconj t1 1））
  

这会导致一个全新的树复制和没有结构共享，还是会有一些结构仍然共享？如果左分支更大说2-> 3-> 4-> 5-> 6-> 7（*根）和1被插入到左子树，然后一些共享的结构持久？

解决方案

要插入新值的位置的路径上的节点将被替换，但至少有两件事情应该

节点在 xconj 操作过程中保留其子树及其值之一;只有一个子树被交换出来。 （如果您沿着左，左，左路径替换节点，则位置左，左，右的节点将被共享）。因此，即使沿着

被替换的节点是地图。如果它们大于只有三个键，那么使用 assoc / assoc-in / update-in ，而不是构建新地图：

  ... 
 （< v（：val t））（update-in t [：L] xconj v）
 ... 
  

比新节点映射能够与旧节点映射共享结构。 （再次，这里没有意义，因为节点是多么小;但在不同的上下文中，这可以产生巨大的差异。）

I'm unclear about structural sharing in Clojure. Below is a function xconj taken from the Joy of Clojure (Great book BTW).

;;Building a naive binary search tree using recursion
(defn xconj [t v]
      (cond 
          (nil? t) {:val v :L nil :R nil}
          (< v (:val t)) {:val (:val t) :L (xconj (:L t) v) :R (:R t)}
          :else {:val (:val t) :L (:L t) :R (xconj (:R t) v)}))

If one defines two trees t1 and t2 as shown below.

(def t1 (xconj (xconj (xconj nil 5) 3) 2))
(def t2 (xconj t1 7))

It is clear that the Left subtree is shared by t1 & t2

user> (identical? (:L t1) (:L t2))
true

But if one were to create a new tree t3, by inserting a new value '1' in the left subtree of t1, like this:

(def t3 (xconj t1 1))

Will this result in a completely new tree with all values copied and no structural sharing, or will some structure still be shared? What if the left branch was bigger say 2->3->4->5->6->7(*root) and 1 was inserted in the left subtree, will then some sharing of structure persist?

解决方案

The nodes on the path to the place where the new value is to be inserted will be replaced, but there are at least two things one ought to notice to get the whole story:

1. Replacing a non-nil node in the course of an xconj operation preserves one of its subtrees and its value; only one subtree is swapped out. (If you replace nodes along the path "left, left, left", then the node at position "left, left, right" is going to be shared.) Thus a lot of structure can potentially be shared even if all nodes along the path to one of the leaves are replaced.

2. The nodes being replaced are maps. If they were larger than just three keys, it would make sense to use assoc / assoc-in / update-in instead of building new maps:

   ...
   (< v (:val t)) (update-in t [:L] xconj v)
   ...
   

   Than the new node map would be able to share structure with the old node map. (Once again, here it doesn't make sense because of how small the nodes are; but in different contexts this can make a huge difference.)

这篇关于Clojure中的结构共享的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！