Scala中的持久数据结构

Question

Scala中的所有不可变数据结构都是持久的吗？如果不是,哪一个是哪个,哪个不是？那些持久的行为特征是什么？另外,它们如何与Clojure中的持久数据结构进行比较？

Answer 1

Scala的不可变数据结构都是持久的,因为旧值是由"更新"操作维护的.事实上,我不知道不可变和持久之间的区别; 对我来说,这两个术语是别名.

Scala的2.8个不可变数据结构中的两个是向量和散列尝试,表示为32个树.这些最初由Phil Bagwell设计,他与我的团队一起在EPFL工作,然后被Clojure采用,现在最终被Scala 2.8采用.Scala实现与Clojure实现共享一个公共根,但肯定不是它的端口.

好吧,我的理解是"持久性"是指一种实现,其中更新不可变值返回一个与原始值共享子结构而不是完全克隆的值.这可以使不可变集合的性能接近其可变对应物 - 您不需要复制10k旧元素以添加单个新元素. (22认同)
我在http://akka.io/docs/akka/1.2/scala/stm.html中找到了这一段:"Scala提供了所谓的持久数据结构,这使得快速处理不可变集合.它们是不可变的,但具有持续的时间访问和它们使用结构共享,插入或更新不会破坏旧结构,因此"持久".快速处理不可变复合类型.持久数据结构目前由Map和Vector组成. - 鉴于这个答案,我觉得有点令人费解.我可能只是误解了一些东西. (5认同)
"持久"意味着当您"修改"其中一个结构(例如,将键/ val插入映射)时,原始数据结构提供的性能保证也适用于派生数据结构.在不是这种情况下构建实现很容易. (3认同)
我不认为数据共享(与复制相对)是持久性的先决条件,因为通常使用该术语.(http://en.wikipedia.org/wiki/Persistent_data_structure) (2认同)

Answer 2

他也指的是Clojure的实现.

Answer 3

List,Vector,HashMap和HashSet在Scala 2.8上都是持久的.还有其他持久性数据结构,但这些结构涵盖了所有主要用途,我不确定列举所有这些结构是否有任何意义.

@MartinKonicek"有效"O(1),这意味着一些假设必须保持为O(1).请参阅集合[性能特征](http://docs.scala-lang.org/overviews/collections/performance-characteristics.html)文档. (2认同)