如何操作不可变对象的树？

immutability java class-design

2022-09-04 20:47:22

我正在从不可变对象构建整个应用程序，以便多线程和撤消变得更容易实现。我正在使用Google Collections Library，它提供了Map，List和Set的不可变版本。

我的应用程序模型看起来像一棵树：

对象图可能如下所示：

Scene
 |
 +-- Node
      |
      +-- Node 
           |
           +- Port
      +-- Node
           |
           +- Port
           +- Port

如果所有这些对象都是不可变的，则由顶级 SceneController 对象控制：

更一般地说：

答案 1

这里有两个有趣的概念。首先，持久数据结构。如果树的所有元素都是不可变的，那么可以通过替换某些部分（但引用旧部分）从原始树中派生出新树，从而节省时间和内存。

例如，如果要向已具有两个端口的节点添加第三个端口，则必须创建一个新场景、一个新场景的节点的后代以及要更改的节点。不需要重新创建其他节点和所有端口 - 您只需在新的场景/节点中引用它们即可。

另一个概念是拉链。拉链是一种在持久性数据结构中“导航”以优化本地更改的方法。例如，如果您添加了四个新端口而不是一个，但每次添加一个端口，则必须创建四个新场景和八个新节点。使用拉链，您可以推迟此类创作，直到完成，从而节省这些中间对象。

我读过的关于拉链的最好的解释是在这里。

现在，使用拉链来导航数据结构消除了对反向链接的需求。通过巧妙地使用递归构造函数，可以在不可变结构中具有反向链接。但是，这样的数据结构不会是持久的。非持久性不可变数据结构的修改性能较差，因为每次都需要复制整个数据。

至于学术文献，我推荐冈崎的《纯粹函数数据结构》（论文PDF，完全成熟的书）。

答案 2

如果你的树是不可变的，那么如果你想改变它，你必须产生一个新的树。

这听起来很糟糕，但如果你所有的节点都是不可变的，那就不是这样了！由于您不需要创建不可变对象的副本，因此除了您所做的更改之外，您的新树将主要引用旧树。

您必须以这样一种方式设计您的树，即每个不可变树都引用其他不可变树。这样，您也不需要重现整个不可变树。

但是，如果您走不可变的树路线，那么您就不能有反向链接。否则，您将无法重用子树。