爲什麼Scala列表中沒有大小字段？

來自Java背景，我想知道爲什麼List斯卡拉沒有size字段，就像它的Java相當於LinkedList。畢竟，在size字段中，您可以在常量時間內確定列表的大小，爲什麼size字段會下降？爲什麼Scala列表中沒有大小字段？

（本問題涉及到新的集合類斯卡拉2.8和更高版本。另外，我指的是不可變的List，而不是可變的。）

來源

2011-11-19 python dude

它是Java中的'size（）'函數。 – Kapep

但是該函數由一個字段支持，這使得它成爲O（1）。 Scala List沒有這個字段，理由很充分，但是這使得訪問長度爲O（n）。 –

「* python * dude」來自* Java *背景？ * python *不是指語言，是嗎？ – huynhjl

不能說的大小字段是下降，因爲這樣的名單不存在了，因爲LISP50年他們在哪裏無處不在，他們是很常見的ML和Haskell過大小，在斯卡拉都是有重要影響。

其基本原因是列表是一個遞歸結構。非空的List是Cons(head: A, tail: List[A]) - 除了Cons實際上被稱爲::以允許方便的中綴符號。你可以訪問尾部（沒有頭元素的列表），這也是一個列表。這幾乎是所有的時間。因此，在列表中添加計數並不意味着只添加一個整數，而是與元素一樣多的整數。這是可行的，但肯定不是免費的。

如果與java的LinkedList進行比較，LinkedList有一個遞歸實現（基於Node，或多或少像Cons，但在兩個方向都有鏈接）。但LinkedList不是一個Node，它擁有它們（並保持它們的計數）。所以雖然它有遞歸實現，但不能遞歸處理它。它想要LinkedList的尾部作爲LinkedList，您必須刪除頭部並更改列表，或者將所有尾部元素複製到新的LinkedList。所以scala的List和java的LinkedList是非常不同的結構。

來源

2011-11-19 22:21:43

列表在scala中是嚴格的。所以每次應用Cons時它都知道尾部的大小，因此可以增加1並將其寫入特定的字段。像'Cons（head：A，tail：List [A]）{override val size：Int = tail.size + 1}'。這是可能的，但可能被認爲太空間飢餓。 – ayvango

你檢查length場？

來源

2011-11-19 22:02:12

'length'是一種遍歷整個列表的方法，因此具有'O（n）'複雜性。 OP詢問爲什麼不存在具有恆定時間訪問權限的「長度」字段*。 –

@Udo Held：您的鏈接來自Scala 2.7.7，我沒有經驗。我的問題是基於Scala 2.9+，特別是在第二版的「Programming in Scala」一書中，第16章陳述了確定List的長度與元素數量成線性關係。 –

http://www.scala-lang.org/api/current/scala/collection/mutable/LinkedList.html的長度也是2.9。你會發現這裏的大小以及相當於長度。 –

列表定義尺寸：

> List(1, 2, 3).size 
res4: Int = 3

具有線性O（N）執行時間。如果你真的需要一個恆定的時間，你應該考慮可變的ListBuffer，它提供了一個恆定的時間尺寸實現。

來源

2011-11-19 22:07:49 David

哪個版本的Scala是這樣的？ 2.8之前還是之後？至少從2.8和更高版本開始至少爲 –

。請參閱：http://www.scala-lang.org/api/2.8.0/scala/collection/immutable/List.html – David

雖然這是恆定時間？它說「相當於長度」 – 2011-11-19 22:19:39

因爲維持這個領域將

添加內存開銷的所有列表;
爲每個列表創建添加一點時間開銷。

在Java中，通常會創建一個LinkedList，然後在不通過添加/刪除元素的情況下創建新列表的情況下進行操作;在Scala中創建了許多List。

因此決定開銷不值得。

來源

2011-11-19 22:21:22

實際上，考慮到對象是以8個字節的倍數分配的，添加一個'size'字段會將*cons_的大小從8增加到16個字節。 –

我錯過了什麼？尺寸有：

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_29). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.collection.immutable.List 
import scala.collection.immutable.List 

scala> val a = List(1,2,3) 
a: List[Int] = List(1, 2, 3) 

scala> a size 
res0: Int = 3

來源

2011-11-20 00:08:04 Fred

確切但它是一個o（n）大小的實現。主題是LinkedList java實現有一個大小字段，可以在不變的時間內重新調整大小。 – David

的的O（n）的複雜性「缺點」是不是像你想象的那麼大。 Martin Odersky在一次演講中提到，如果我沒有記錯的話，任何計算機語言的所有程序中創建的所有列表中的90％的大小爲4或更小。（這是在不變性和效率的背景下）

因此，size的O（n）訪問時間對於創建的大多數列表來說並不是一個很大的開銷，並且，正如其他人在此提到的那樣，內存節省大於補償這個。

來源

2011-11-20 00:28:26 Adrian

爲什麼Scala列表中沒有大小字段？

回答

相關問題