7

我想拥有功能数据结构（可以共享结构的多个数据版本）的优势，但能够以命令式的方式对其进行修改。

我在想什么（以及可能的用途）：一个 RPG 游戏，其中存储了整个游戏历史（例如，允许时光倒流）。使用写时复制，我可以简单地克隆保存游戏状态的结构并通过引入新回合来修改它 - 但可以访问早期的回合（不一定是所有回合，可能只是选择的游戏状态快照），没有每次都必须复制所有内容的惩罚。

假设foo是一张地图。

bar = foo.clone()

没有任何foo结构（例如，树）被复制。但是，从现在开始bar被视为副本，不允许任何更改传播回 `foo'。

baz = bar[someKey]
baz.modifyInSomeWay()

现在

  • 创建了一个新对象，即baz.
  • bar被替换为新地图，持有新地图baz（可能保留一些foo's 结构）。
  • foo不受影响。

但如果我们这样做...

baz.modifyAgain()

...baz可以只修改，因为我们有它的最新版本。bar 不需要改变。

foo所有这些都需要保存一些关于and的版本信息bar，在 上增加它foo.clone()，并以某种方式传递它baz（通过使其成为代理对象？）。

此外，已克隆的结构的任何部分都将成为“历史的一部分”并且不能再更改，这可以在运行时强制执行。

这有点类似于 JavaScript 的原型，但我更像是因为它允许更改向上传播。我认为它类似于版本控制系统。

  • 有没有做到这一点，做到什么程度？
  • 这是一个好主意吗？如果没有，有没有办法挽救它？
  • 如何实施？我正在考虑在一些高级 GC 语言（如 Python）之上构建它。
4

3 回答 3

8

功能（“持久”）数据结构通常由不可变节点递归构建（例如，共享公共后缀的单链表，搜索树或堆，其中只有从根到树的路径上的树结构部分）更新的项目需要复制）。

每次修改都必须复制整个集合的任何东西都是不好的。在这些情况下，您往往会通过递归到以前的版本来覆盖检查（花费额外时间）的小“差异”。每隔一段时间，当差异变得太大时，您可以进行深度复制/重建（因此摊销成本并没有那么糟糕）。

持久化数据结构可能有很大的开销，但如果您对小对象进行非常有效的分配（JVM GC 合格），它们可能非常实用 - 在最好的情况下，与可变等价物一样快，仅以使用的内存 - 这可能比每次更新时的完整副本少得多。

根据您的语言，您可能会发现在没有运算符重载进行赋值的情况下难以实现您想要的语法。C++ 中的左值（可变引用）肯定需要非持久语义。

于 2009-09-04T21:36:12.077 回答
0

与仅仅拥有一个完全不可变的数据结构然后使用一个包含对它的引用并公开一个通过更新包装版本来工作的命令式接口的包装器相比，这听起来非常复杂且容易出错。

例如在 Scala 中

class ImmutableData{
   def doStuff(blah : Blah) : ImmutableData = implementation
}

class MutableData(var wrapped : ImmutableData){
  def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); } 
}

当然，这意味着您必须制作两个版本的界面，但语义要理智得多。

于 2009-09-05T10:06:15.613 回答
0

1. 有没有做到，做到什么程度？

是的，例如参见 qt5隐式共享。

2. 这是个好主意吗？如果没有，有没有办法挽救它？

是的，这是个好主意。建议的替代方案之一是使用完全不可变的数据结构（包装在命令式接口中），但问题是即使对象是唯一指向数据的对象，修改操作也会创建数据的副本（没有就地更新），这是低效的。使用写时复制方法，仅在第一次修改时进行复制，随后的修改会更改复制的数据（如果没有创建对相同数据的另一个引用，当然）。

3、如何实施？我正在考虑在一些高级 GC-ed 语言（如 Python）之上构建它。

一种方法是使用引用计数，例如在 qt 中（参见此处的描述）。要实现它，将需要赋值运算符重载或显式方法调用（例如bar = foo.clone()，但它可能很脆弱，如果有人忘记调用clone而只是这样做会发生什么bar = foo？），因此可以保留计数。

如您所说，创建代理对象的其他可能性。参见例如pycow（python 实现）。

于 2016-05-10T16:08:28.393 回答