我有一个序列,想要得到以下长度:
val x = (1 to 1000000)
x.length
这是O(1)运算吗? (看起来像这样,通过在副本中尝试几行而得来。)为什么?什么是序列存储,如果它是一个O(1)运算,它将使它成为O(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
。
关于scala - 获取序列的长度是恒定时间操作吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8889258/