¿Persisten todas las estructuras de datos inmutables en Scala? Si no, ¿cuáles de ellos son y cuáles no? ¿Cuáles son las características de comportamiento de aquellos que son persistentes? Además, ¿cómo se comparan con las estructuras de datos persistentes en Clojure?Estructuras de datos persistentes en Scala
Las estructuras de datos inmutables de Scala son todas persistentes, en el sentido de que el valor anterior se mantiene mediante una operación `update '. De hecho, no sé de la diferencia entre inmutable y persistente; para mí, los dos términos son alias.
Dos de las 2.8 estructuras de datos inmutables de Scala son vectores y hash tries, representados como árboles de 32 arios. Estos fueron diseñados originalmente por Phil Bagwell, quien estaba trabajando con mi equipo en EPFL, luego adoptado por Clojure, y ahora finalmente adoptado por Scala 2.8. La implementación de Scala comparte una raíz común con la implementación Clojure, pero ciertamente no es un puerto de la misma.
Para la última parte de su pregunta, recuerdo que Rich Hickey mencionó en una presentación que las estructuras de datos de Clojure han sido transferidas a Scala. Además, Michael Fogus menciona planes para que Scala 2.8 adopte algunas de las estructuras de datos de Clojure en this interview.
Lo siento, esto es tan corto en detalles ... No estoy seguro de cuál es el estado en los planes antes mencionados de Scala 2.8, pero recordé que Rich y Michael mencionaron esto y pensaron que podría ser una cosa interesante para ti google para si estás interesado.
Por favor, echar un vistazo a estos excelentes artículos de Daniel Spiewak:
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala
http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis
También se está refiriendo a la aplicación Clojure.
List, Vector, HashMap y HashSet son todos persistentes en Scala 2.8. Existen otras estructuras de datos persistentes, pero que cubren todos los usos principales, no estoy seguro de que tenga sentido enumerarlos todos.
¿Esto significa que el método + de HashMap es O (1)? –
@MartinKonicek "Efectivo" O (1), lo que significa que algunas suposiciones deben mantenerse para que sea O (1). Consulte las colecciones [características de rendimiento] (http://docs.scala-lang.org/overviews/collections/performance-characteristics.html) documentos. –
¡Gracias @Daniel C. Sobral! –
Bueno, entiendo que "persistente" se refiere a una implementación en la que la actualización de un valor inmutable devuelve un valor que comparte una subestructura con el original en lugar de hacer un clon completo. Esto puede proporcionar colecciones inmutables con un rendimiento cercano a sus contrapartes mutables: no es necesario copiar 10k de elementos antiguos para agregar uno nuevo. –
No creo que el intercambio de datos (a diferencia de la copia) sea un requisito previo para la persistencia ya que el término se usa normalmente. (http://en.wikipedia.org/wiki/Persistent_data_structure) –
Encontré este párrafo en http://akka.io/docs/akka/1.2/scala/stm.html: "Scala proporciona las llamadas estructuras de datos persistentes lo que hace que trabajar con colecciones inmutables sea rápido. Son inmutables pero con acceso y modificación de tiempo constante. Usan el intercambio estructural y una inserción o actualización no arruina la estructura anterior, por lo tanto "persistente". Hace que trabajar con tipos compuestos inmutables sea rápido. las estructuras de datos actualmente consisten en un mapa y un vector ". - Me parece un poco desconcertante a la luz de esta respuesta. Probablemente simplemente entendí mal algo. –