获得序列的长度是一个恒定时间操作？

Question

我有一个序列,我想得到的长度:

val x = (1 to 1000000)
x.length

这是O(1)操作吗？(看起来像这样,在repl中尝试了几行.)为什么？什么是序列存储,使其成为O(1)操作,如果它是一个？(它只是将序列的长度存储为元数据吗？)

Answer 1

(1 to 1000000)创建一个Range对象(不是更一般Seq). 通过调用Range定义:lengthcount

def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int = {
  // faster path for the common counting range
  if (start >= 0 && end > start && end < scala.Int.MaxValue && step == 1)
    (end - start) + ( if (isInclusive) 1 else 0 )
  else
    NumericRange.count[Long](start, end, step, isInclusive)
}

因此,您可以看到,在给定的简单情况下,Range步长为1的length是O(1),因为它只是减去end-start并添加一个.该NumericRange.count选项更复杂,但仍使用数学运算在恒定时间内查找值.

至于其他Seq类型:

List 是一个链表并且不直接存储长度信息,因此它需要遍历整个结构并跟踪它看到的元素数量:

def length: Int = {
  var these = self
  var len = 0
  while (!these.isEmpty) {
    len += 1
    these = these.tail
  }
  len
}

另一方面,类似于Vector存储索引信息,因此它可以在恒定时间内返回长度:

def length = endIndex - startIndex

其他Seq类型可以length以其他方式实现.

Answer 2

这取决于Seq的实施.长度定义为抽象(http://www.scala-lang.org/api/current/scala/collection/Seq.html),因此某些序列可能是恒定时间(如数组),有些可能是线性的(链表) ).