scala - 获取序列的长度是恒定时间操作吗？

Question

我有一个序列，想要得到以下长度:

val x = (1 to 1000000)
x.length

这是O(1)运算吗？ (看起来像这样，通过在副本中尝试几行而得来。)为什么？什么是序列存储，如果它是一个O(1)运算，它将使它成为O(1)运算？ (它只是将序列的长度存储为元数据吗？)

Answer 1

(1 to 1000000)创建一个Range对象(不是更通用的Seq)。 Range通过调用length来定义count:

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)
}

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

至于其他 NumericRange.count类型:
Seq是一个链表，不直接存储长度信息，因此它需要遍历整个结构并跟踪看到的元素数:

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

另一方面，像 List这样的东西存储索引信息，因此它可以在恒定时间内返回长度:

def length = endIndex - startIndex

其他 Vector类型可以其他方式实现 Seq。