为什么在Scala List前面添加一个常量时间操作,但是附加一个线性时间操作？

Question

我现在正在从Odersky的"Scala编程"中学习Scala,我刚读完这篇文章

...附加到列表所花费的时间随着列表的大小线性增长,而前缀为::需要恒定时间...

为什么在线性时间附加到附加到列表但是只有不变的时间来预先添加到列表中.我目前的猜测是它以某种方式在内部实现为链接列表,这将解释两个操作之间的差异.在这种情况下,如何实现具有恒定时间附加的ListBuffers？

Answer 1

这里有两个问题:一个是关于列表的非常基本的问题,另一个是特定于scala的问题.首先,我会画一幅画."列表"抽象数据类型是计算机科学中最古老的数据类型之一; 它可以追溯到1956年,也是LISP语言的第一次实施.

列表ADT确实使用单向链表实现.传统上,每个元素称为cons单元格(Nil表示列表的结尾):

+------+------+      +------+------+    +--------+
|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +-------------+    +--------+
^
|
val list1 

这对应于scala中链接的"cons"(列表构造)调用:

scala> val list1 = 1 :: 3 :: Nil
list1: List[Int] = List(3, 1)

List是一个不可变的数据结构.我们不能通过重写任何现有的指针/引用来破坏性地更新它.那么如果我们想要在它前面呢？

scala> val list2 = 0 :: list1
list2: List[Int] = List(0, 1, 3)

创建list2非常快速和简单,我们只需创建一个新的cons单元并将其添加到现有列表中:

+------+------+      +------+------+      +------+------+    +--------+
|   0  |   *--+----->|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +------+------+      +-------------+    +--------+
 ^                   ^
 |                   |
 val list2           val list1 

这样做的好处在于它保留了所有现有的参考文献,保留了不变性.但是,如果我们想要/追加/到列表,我们必须将对Nil的引用覆盖为新元素,从而改变list1.因此,唯一的方法是复制整个现有列表并重写它:

scala> val list3 = list1 ++ (5 :: Nil)
list3: List[Int] = List(1, 3, 5)


+------+------+      +------+------+      +------+------+    +--------+
|   0  |   *--+----->|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +------+------+      +-------------+    +--------+
^                    ^                                           ^
|                    |                                           |
val list2            val list1                                   |
                                                                 |
                                                                 |
(copy)                                                           |
+------+------+      +------+------+    +--------+-------+       |
|   1  |   * -+----> |  3   +   * -+--->|   5    |    *--+-------+
+------+------+      +-------------+    +--------+-------+    
^
|
val list3 

这是一个线性时间操作,因为要附加到长度为N的列表,我们必须复制所有N个cons单元格(Nil除外).

至于Scala的ListBuffer,其附加的工作原理是直接突变背衬列表中,在重写最终cons单元,其具有性能稍微别扭的寻找类型:: [A]的尾部参考.

在List.scala中:

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
   override def tail : List[B] = tl
   override def isEmpty: Boolean = false
}

[..]在ArrayList.scala中:

/** Appends a single element to this buffer. This operation takes constant time.
*
*  @param x  the element to append.
*  @return   this $coll.
*/
def += (x: A): this.type = {
  if (exported) copy()
  if (isEmpty) {
    last0 = new :: (x, Nil)
    start = last0
  } else {
    val last1 = last0
    last0 = new :: (x, Nil)
    last1.tl = last0
  }
  len += 1
  this
} 

last1.tl = last0是允许的,因为::.tl具有可见性私有[scala],允许不安全的"幕后"操作来改变集合,例如ListBuffer.

Answer 2

它们都与链接列表类似地实现.不同之处在于ListBuffer还包含指向列表尾部的指针.Scala的源代码是开放的,如果你对它的细节感到好奇,你可以在github上探索它(例如,这里是ListBuffer的附加代码)