tail 和 init 在 List 上的运行时

Question

如果我有以下 ls scala.collection.immutable.List 实例：

将 ls.init 复制 ls 的前 n-1 个元素，然后返回此副本从而产生 n-1 的 theta 运行时间（由于复制运行时间）？

ls.tail 是否需要 O(1) （我想这会将 ls 解构为 head :: tail 然后返回 tail 这将需要 O(1)它是一个单链表）？

我实际上需要一个可以给我 O(1) 初始化操作的集合，有没有一个集合可以为初始化提供这样的运行时间？

Answer 1

关于tail：

@SerialVersionUID(509929039250432923L) // value computed by serialver for 2.11.2, annotation added in 2.11.4
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
}

所以是的，它是 O(1)。 Init 定义在 TraversableLike:

def init: Repr = {
    if (isEmpty) throw new UnsupportedOperationException("empty.init")
    var lst = head
    var follow = false
    val b = newBuilder
    b.sizeHint(this, -1)
    for (x <- this) {
      if (follow) b += lst
      else follow = true
      lst = x
    }
    b.result
}

所以它是线性的。

如果您需要具有常量 init 的不可变结构，可以使用 @Dima 提到的 Vector。 Init 在那里实现为 dropRight(1) 。但它是 "effectively constant"，因为 Vector 更像是一个深度数组数组（32 的 Trie），所以 dropRight 实际上是在创建一个具有另一个大小的新视图（通过在某个高级别上快速复制），但仍然必须处理右边缘以聪明的方式，所以这个“1”实际上可能是 32，甚至 64（我想）。

tail 和 init 在 List 上的运行时

Runtime of tail and init on List

scala

scala-collections