Does the duration of the sequence get a continuous operation?

Question

I have a sequence that I want to get the length:

val x = (1 to 1000000) x.length 

Is this an O (1) operation? (It sounds like having tried a couple of lines in a replica.) Why? What is the sequence preservation that this O (1) operation does, if it is one? (Does it just save the length of the sequence as metadata?)

Answer 1

(1 to 1000000) creates a Range object (no more common Seq ). Range defines length by calling 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) } 

So you can see that in the simple case above, a Range with a step size of 1, length is O (1), because it just subtracts the end-start and adds it. The NumericRange.count option NumericRange.count more complex, but still uses math to find the value in constant time.

As for other types of Seq :

List is a linked list and does not store length information directly, so moving the entire structure and tracking the number of elements that it sees is required:

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

On the other hand, something like Vector stores information about the index, so it can return a length in constant time:

 def length = endIndex - startIndex 

Other types of Seq may implement length other ways.

Answer 2

It depends on the implementation of Seq. Length is defined as abstract ( http://www.scala-lang.org/api/current/scala/collection/Seq.html ), so some sequences can be constant (like arrays), some can be linear (linked lists) .