为什么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列表中没有大小字段？

回答

相关问题