具有写时复制功能的纯功能数据结构？

我想拥有功能数据结构的优势(可以共享结构的多个数据版本),但能够以命令式方式修改它.

我正在考虑的(以及可能的用途):一个RPG游戏,其中存储了整个游戏历史(例如,允许回到过去).使用copy-on-write,我可以简单地克隆保持游戏状态的结构并通过引入新的转弯来修改它 - 但是可以访问较早的转弯(不一定是所有这些转弯,可能只是游戏状态的选定快照),而不是每次必须复制一切的惩罚.

让我们说foo是一张地图.

bar = foo.clone()

没有任何foo结构(例如,树)被复制.但是,从现在开始,bar它被视为副本,并且不允许任何更改传播回`foo'.

baz = bar[someKey]
baz.modifyInSomeWay()

现在

创建一个新对象,这是一个修改过的副本baz.

bar用新地图替换,保留新的baz(可能保留一些foo结构).

foo 不受影响.

但如果我们那么做......

baz.modifyAgain()

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

所有这些都需要持有的一些版本信息foo和bar关于增加它foo.clone(),并把它传递给baz某种方式(通过使代理对象？).

此外,已克隆的结构的任何部分都成为"历史的一部分",不能再被更改,这可以在运行时强制执行.

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

这已经完成了,到了什么程度？

这是一个好主意吗？如果没有,有没有办法保存它？

怎么可以实施？我正在考虑在Python之类的高级GC语言之上构建它.

Jonathan Gra.. 8

功能("持久")数据结构通常是由不可变节点递归构建的(例如,单独链接列表,其中共享后缀是共享的,搜索树或堆,其中只有树结构的部分位于从根到达的路径上更新的项目需要复制).

每次修改都必须复制整个集合的任何内容都是不好的.在这些情况下,您倾向于使用递归到先前版本来覆盖检查(花费额外时间)的小"差异".每隔一段时间,当差异变得太大时,你可以进行深度复制/重建(因此摊销成本并不那么糟糕).

持久性数据结构可能会产生很大的开销,但是如果你有非常有效的小对象分配(JVM GC合格),它们就非常实用 - 在最好的情况下,同样和可变等价物一样快,只能以牺牲成本为代价来提供持久性.使用的内存 - 每次更新时可能比完整副本少得多.

根据您的语言,您可能会发现您希望在没有操作符重载的情况下难以实现的语法.C++中的Lvalues(可变引用)肯定需要非持久语义.

功能("持久")数据结构通常是由不可变节点递归构建的(例如,单独链接列表,其中共享后缀是共享的,搜索树或堆,其中只有树结构的部分位于从根到达的路径上更新的项目需要复制).

每次修改都必须复制整个集合的任何内容都是不好的.在这些情况下,您倾向于使用递归到先前版本来覆盖检查(花费额外时间)的小"差异".每隔一段时间,当差异变得太大时,你可以进行深度复制/重建(因此摊销成本并不那么糟糕).

持久性数据结构可能会产生很大的开销,但是如果你有非常有效的小对象分配(JVM GC合格),它们就非常实用 - 在最好的情况下,同样和可变等价物一样快,只能以牺牲成本为代价来提供持久性.使用的内存 - 每次更新时可能比完整副本少得多.

根据您的语言,您可能会发现您希望在没有操作符重载的情况下难以实现的语法.C++中的Lvalues(可变引用)肯定需要非持久语义.