正在獲取序列的長度恆定時間操作？

Question

我有我想要得到的長度的順序：

val x = (1 to 1000000) 
x.length 

這是一個O（1）操作？ （似乎是這樣，在repl中嘗試了幾行。）爲什麼？什麼是序列存儲，使其成爲O（1）操作，如果它是一個？ （它是否僅將序列的長度存儲爲元數據？）

Answer 1

(1 to 1000000)創建一個Range對象（不是更一般的Seq）。 Range通過調用count定義length：

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:1的步長Range，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），所以一些序列可能是恆定的時間（如數組），有些可能是線性的（鏈表）。