为什么Scala列表没有大小字段？

Question

来自Java背景,我想知道为什么List在Scala中没有size类似Java等效的字段LinkedList.毕竟,使用大小字段,您将能够在常量时间内确定列表的大小,那么为什么大小字段会被删除？

(这个问题涉及Scala 2.8及更高版本中的新集合类.另外,我指的是不可变的List,而不是可变的.)

Answer 1

人们不能说大小字段被丢弃了,因为没有大小的列表已经存在了50年,因为LISP无处不在,它们在ML和Haskell中也很常见,在scala中都很有影响力.

基本原因是list是递归结构.非空List是Cons(head: A, tail: List[A])- 除了Cons实际上被称为::允许方便的中缀表示法.您可以访问尾部(没有头元素的列表),这也是一个列表.这种情况几乎一直在进行.因此,列表中的计数并不意味着只添加一个整数,而是添加与元素一样多的整数.这是可行的,但肯定不是免费的.

如果你与java的比较LinkedList,LinkedList有一个递归实现(基于Node,它或多或少像Cons,但在两个方向都有链接).但是LinkedList不是Node,它拥有它们(并且保留它们的数量).因此,虽然它具有递归实现,但您不能递归地处理它.您希望LinkedList的尾部作为LinkedList,您必须删除头部并更改列表,否则将所有尾部元素复制到新的LinkedList.所以scala List和java LinkedList是非常不同的结构.

Answer 2

因为保持这个领域会

1. 为所有列表添加内存开销;
2. 在每个列表创建上添加少量时间开销.

在Java中,通常LinkedList创建a,然后通过添加/删除元素来操作而不创建新列表; 在Scala中有很多Lists创建.

所以决定开销不值得.

Answer 3

列表定义大小:

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

它具有线性o(n)执行时间.如果你真的需要一个恒定的时间,你应该考虑ListBuffer提供恒定时间大小实现的mutable .

Answer 4

O(n)复杂性的"劣势"并不像你想象的那么大.Martin Odersky在一次演讲中提到(如果我没记错的话)在所有程序中用任何计算机语言创建的所有列表中有90%的大小为4或更小.(这是在不变性和效率的背景下)

因此,size对于大多数创建的列表而言,O(n)访问时间并不是一个很大的开销,并且正如其他人在此提到的那样,内存节省不仅可以弥补这一点.