Является ли получение длины последовательности операцией с постоянным временем?

Question

У меня есть последовательность, которую я хочу получить длиной:

val x = (1 to 1000000)
x.length

Это операция 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)
}

Итак, вы можете видеть, что в данном простом случае 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 ), поэтому некоторые последовательности могут иметь постоянное время (например, массивы), некоторые могут быть линейными ( связанные списки).