持久vs不可变数据结构 [英] persistent vs immutable data structure

问题描述

持久化和不可变数据结构有差异吗？维基百科指的是在讨论持久性时的不可变数据结构，但我有一种感觉，两者之间可能会有微妙的区别。

解决方案

em> Immutability 是一种实现技术。除此之外，它提供了一个接口的持久化。持久性API是这样的：

• 版本更新（操作o，版本v）在版本 v 上执行操作 o ，返回一个新版本。如果数据结构是不可变的，新版本是一个新的结构（可能会分享旧结构的不可变部分）。如果数据结构不可变，则返回的版本可能只是版本号。版本 v 仍然是有效的版本，因为这个更新，所以不能更改任何观察 - 更新只能在返回的版本中显示，而不在 v 中。


• 数据观察（查询q ，版本v）观察版本 v 的数据结构，而不更改或创建新版本。

有关这些差异的更多信息，请参阅：

• Haim Kaplan在数据结构与应用手册中的持久数据结构一章


• 数据结构持续存在Driscoll等人


• 2012年春季麻省理工学院6.851年第一次演讲：高级数据结构

Is there any difference in a persistent and immutable data structure? Wikipedia refers to immutable data structure when discussing persistence but I have a feeling there might be a subtle difference between the two.

解决方案

Immutability is an implementation technique. Among other things, it provides persistence, which is an interface. The persistence API is something like:

• version update(operation o, version v) performs operation o on version v, returning a new version. If the data structure is immutable, the new version is a new structure (that may share immutable parts of the old structure). If the data structure isn't immutable, the returned version might just be a version number. The version v remains a valid version, and it shouldn't change in any observe-able way because of this update - the update is only visible in the returned version, not in v.
• data observe(query q, version v) observes a data structure at version v without changing it or creating a new version.

For more about these differences, see:

• The chapter "Persistent data structures" by Haim Kaplan in Handbook on Data Structures and Applications
• "Making Data Structures Persistent" by Driscoll et al.
• The first lecture of the Spring 2012 incarnation of MIT's 6.851: Advanced Data Structures

这篇关于持久vs不可变数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！