¿Por qué la Lista de Scala no tiene un campo de tamaño?

Procedente de un fondo Java, me pregunto por qué List en Scala no tiene un campo size como su equivalente en Java LinkedList. Después de todo, con un campo de tamaño, podrá determinar el tamaño de la lista en tiempo constante, entonces, ¿por qué se eliminó el campo de tamaño?¿Por qué la Lista de Scala no tiene un campo de tamaño?

(Esta pregunta se refiere a las nuevas clases de colección en Scala 2.8 y posteriores. Además, me refiero a lo inmutable List, no el mutable.)

Fuente

2011-11-19 python dude

Es 'size()' en Java, una función. – Kapep

Pero la función está respaldada por un campo, lo que lo convierte en O (1). Scala List no tiene dicho campo, por una buena razón, pero eso hace que acceda a la longitud O (n). –

"* python * dude" viene de un * fondo * Java *? * python * no se refiere al idioma, ¿o sí? – huynhjl

No se puede decir el campo de tamaño se redujo , como tal lista sin el tamaño han existido durante 50 años desde LISP donde están omnipresentes y son muy comunes en ML y Haskell también, tanto influyente en la Scala.

La razón básica es que la lista es una estructura recursiva. Un List no vacío es Cons(head: A, tail: List[A]) - excepto que Cons se llama de hecho :: para permitir una notación de infijo conveniente. Puedes acceder a la cola (la lista sin su elemento principal) y esa es una lista también. Y esto se hace casi todo el tiempo. Por lo tanto, tener el recuento en la lista no significa agregar solo un entero, sino tantos enteros como elementos. Esto es factible, pero ciertamente no es gratis.

Si compara con el LinkedList de java, LinkedList tiene una implementación recursiva (basada en Node, que es más o menos como Cons, pero con enlaces en ambas direcciones). Pero LinkedList no es un Node, los posee (y mantiene su cuenta). Por lo tanto, si bien tiene una implementación recursiva, no puede tratarlo recursivamente. Si deseaba la cola de una LinkedList como LinkedList, tendría que eliminar la cabecera y cambiar su lista o copiar todos los elementos de la cola en una nueva LinkedList. Por lo tanto, el List de scala y el LinkedList de java son estructuras muy diferentes.

Fuente

2011-11-19 22:21:43

Las listas son estrictas en scala. Por lo tanto, cada vez que se aplica Cons, conoce el tamaño de la cola y, por lo tanto, puede aumentar en 1 y escribirlo en un campo específico. Como 'Contras (cabeza: A, cola: Lista [A]) {invalidar el tamaño del val: Int = cola.tamaño + 1}'. Es posible, pero se puede considerar que tiene mucho espacio. – ayvango

¿Ha revisado el campo length?

Fuente

2011-11-19 22:02:12

'length' es un método que atraviesa toda la lista, y por lo tanto tiene una complejidad' O (n) '. El OP pregunta por qué no hay un campo 'length' * con acceso de tiempo constante. –

@Udo retenido: su enlace es de Scala 2.7.7, con el que no tengo experiencia. Mi pregunta se basa en Scala 2.9+, y específicamente en el libro "Programming in Scala", 2nd Ed., Donde se afirma en el capítulo 16 que la determinación de la longitud de una lista es lineal en la cantidad de elementos. –

http://www.scala-lang.org/api/current/scala/collection/mutable/LinkedList.html tiene la longitud también y es 2.9. También encontrarás el tamaño que es equivalente a la longitud. –

Lista define tamaño:

> List(1, 2, 3).size 
res4: Int = 3

que tiene o lineal (n) el tiempo de ejecución. Si realmente necesita un tiempo constante, debe considerar el ListBuffer mutable que proporciona una implementación de tamaño de tiempo constante.

Fuente

2011-11-19 22:07:49 David

¿Qué versión de Scala es esta? Antes o después de 2.8? –

al menos desde 2.8 y posteriores. Ver: http://www.scala-lang.org/api/2.8.0/scala/collection/immutable/List.html – David

¿Es esto constante? dice "equivalente de longitud" –

Debido a que el mantenimiento de este campo sería

Añadir sobrecarga de la memoria de todas las listas;
Agregue una ligera sobrecarga de tiempo en cada creación de lista.

En Java normalmente se crea un LinkedList y, a continuación, manipulado sin crear nuevas listas de añadir/eliminar elementos; en Scala hay muchos List s creados.

Así que se decidió que la sobrecarga no vale la pena.

Fuente

2011-11-19 22:21:22

De hecho, agregar un campo 'size' sería * double * el tamaño de _cons_ de 8 a 16 bytes, dado que los objetos se asignan en múltiplos de 8 bytes. –

¿me falta algo? El tamaño está ahí:

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_29). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.collection.immutable.List 
import scala.collection.immutable.List 

scala> val a = List(1,2,3) 
a: List[Int] = List(1, 2, 3) 

scala> a size 
res0: Int = 3

Fuente

2011-11-20 00:08:04 Fred

exacto pero es una implementación de tamaño o (n). El tema fue que la implementación de LinkedList java tiene un campo de tamaño que retuts el tamaño en tiempo constante. – David

La "desventaja" de la complejidad de O (n) no es tan grande como se podría pensar. Martin Odersky mencionó en una charla que (si no recuerdo mal) el 90% de todas las listas creadas en todos los programas en cualquier lenguaje de computadora tienen un tamaño de 4 o menos.(Esto fue en el contexto de inmutabilidad y eficiencia)

Por lo tanto, el tiempo de acceso O (n) para size no es tan grande para la mayoría de las listas creadas, y, como otros lo han mencionado aquí, el ahorro de memoria compensa con creces esta.

Fuente

2011-11-20 00:28:26 Adrian

¿Por qué la Lista de Scala no tiene un campo de tamaño?

Respuesta

Cuestiones relacionadas