Scala中的持久數據結構

Scala中的所有不可變數據結構是否持久？如果不是，它們是哪一個，哪一個不是？那些持久的行爲特徵是什麼？另外，它們如何與Clojure中的持久數據結構進行比較？Scala中的持久數據結構

2010-06-24 Abhinav Sarkar

Scala的不可變數據結構都是持久的，因爲舊值由`update'操作維護。事實上，我不知道永恆和永恆之間的區別。對我來說這兩個詞是別名。

斯卡拉2.8不可變數據結構中的兩個是向量和散列嘗試，表示爲32元樹。這些最初是由Phil Bagwell設計的，他與我在EPFL的團隊一起工作，然後被Clojure採用，現在最終被Scala 2.8採用。 Scala實現與Clojure實現共享一個共同的根，但肯定不是它的一個端口。

來源

2010-06-24 08:43:18

+20

那麼，我的理解是，「持久性」指的是更新不可變值的實現返回一個與原始值共享子結構的值，而不是完成一個完整的克隆。這可以爲不可變集合提供接近可變對象的性能 - 您不需要複製10k箇舊元素以添加一個新元素。 – 2010-06-24 10:33:56

我不認爲數據共享（而不是複製）是通常使用的術語的持久性的先決條件。（http://en.wikipedia.org/wiki/Persistent_data_structure） – 2010-06-24 19:52:54

我在http://akka.io/docs/akka/1.2/scala/stm.html發現了這一段：「Scala提供了所謂的持久數據結構它使得不可變集合的工作變得快速，它們是不可變的，但是可以隨時訪問和修改，它們使用結構共享，插入或更新不會破壞舊結構，因此「持久化」。數據結構目前由Map和Vector組成。「 - 根據這個答案我覺得有點不解。我可能只是誤解了一些東西。 – 2011-10-31 11:23:46

對於問題的最後部分，我記得Rich Hickey在演示中提到Clojure數據結構已經移植到Scala。另外，Michael Fogus提到Scala 2.8計劃在this interview中採用一些Clojure的數據結構。

對不起，這是如此短的細節......我不確定上述提到的斯卡拉2.8計劃的狀態是什麼，但我記得瑞奇和邁克爾提到這一點，並認爲這可能是一個有趣的事情，讓你谷歌如果你有興趣。

來源

2010-06-24 04:28:15

請看看丹尼爾Spiewak這些優秀的文章：
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala
http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

他還指的是Clojure的實現。

來源

2010-06-24 05:17:25

List，Vector，HashMap和HashSet在Scala 2.8上都是持久的。還有其他的持久數據結構，但是它們涵蓋了所有的主要用途，我不確定列舉所有主要用途是否有意義。

來源

2010-06-24 15:15:52

這是否意味着HashMap的+方法是O（1）？ – 2012-12-02 14:03:19

@MartinKonicek「Effective」O（1），這意味着一些假設必須保持爲O（1）。查看集合[性能特徵]（http://docs.scala-lang.org/overviews/collections/performance-characteristics.html）文檔。 – 2012-12-03 01:34:06

謝謝@Daniel C. Sobral！ – 2012-12-03 15:04:27

Scala中的持久數據結構

回答

相關問題