¿Está obteniendo la duración de una secuencia una operación de tiempo constante?

Question

que tienen una secuencia que quiero para obtener la longitud de:

val x = (1 to 1000000) 
x.length 

¿Es esta una (1) Operación O? (Parece que es así, al probar un par de líneas en el repl.) ¿Por qué? ¿Qué es un almacenamiento de Secuencia que hace de esto una operación O (1), si es una? (¿Simplemente almacena la longitud de la secuencia como metadatos?)

Answer 1

(1 to 1000000) crea un objeto Range (no el más general Seq). Range define length llamando 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) 
} 

Por lo tanto, se puede ver que en el caso sencillo dado, un Range con un tamaño de paso de 1, length es O (1), ya que sólo resta end-start y añade uno. La opción NumericRange.count es más compleja, pero aún utiliza operaciones matemáticas para encontrar el valor en tiempo constante.

En cuanto a otros Seq tipos:

List es una lista enlazada y hace la información de longitud no almacene directamente, por lo que requiere atravesar toda la estructura y hacer el seguimiento de cuántos elementos se ve:

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

por otro lado, algo así como la información del índice Vector tiendas, por lo que puede devolver la longitud en tiempo constante:

def length = endIndex - startIndex 

Otros tipos de Seq pueden implementar length de otras maneras.

Answer 2

Depende de la implementación de Seq. La longitud se define como abstracta (http://www.scala-lang.org/api/current/scala/collection/Seq.html), por lo que algunas secuencias pueden ser de tiempo constante (como matrices), algunas pueden ser lineales (listas enlazadas).