En Clojure, ¿cuándo debo usar un vector sobre una lista y viceversa?

Respuestas:

112

Una vez más, parece que he respondido mi propia pregunta poniéndome impaciente y preguntándola en #clojure en Freenode. Se recomienda responder a sus propias preguntas en Stackoverflow.com: D

Tuve una discusión rápida con Rich Hickey, y aquí está lo esencial.

[12:21] <Raynes>    Vectors aren't seqs, right?
[12:21] <rhickey>   Raynes: no, but they are sequential
[12:21] <rhickey>   ,(sequential? [1 2 3])
[12:21] <clojurebot>    true
[12:22] <Raynes>    When would you want to use a list over a vector?
[12:22] <rhickey>   when generating code, when generating back-to-front
[12:23] <rhickey>   not too often in Clojure
Rayne
fuente
Mientras estás en freenode, ¡ven al lado oscuro y únete a #stackoverflow! :-P
Chris Jester-Young
De hecho, solía estar inactivo allí. Cambié los clientes de IRC y nunca pensé en agregar #stackoverflow a mi lista de autounión.
Rayne
Soy un novato de Lisp, pero me preguntaba si los vectores, los mapas y los conjuntos rompen de alguna manera la idea de que todo el código es intercambiable con los datos. ¿O es solo una de esas cosas que hacen de Clojure un Lisp práctico? (O, ¿puedes evaluar un vector?)
Rob Grant
23
Este es un fragmento de chat completamente inútil. "Generar código" "generar de atrás hacia adelante" -> significa exactamente ?? Realmente estoy teniendo dificultades con esta pregunta porque en mi libro pereza + estilo declarativo = rendimiento mucho mejor, y sin embargo, se sugieren vectores en todas partes en Clojure, lo que me deja totalmente confundido.
Jimmy Hoffa
22
@JimmyHoffa La forma en que lo entiendo: "Generando Código" = "Dentro de una Macro" (porque la mayoría del código son llamadas a funciones, por lo tanto, listas); "generate back to front" = "construyendo una secuencia anteponiendo".
omiel
87

Si ha hecho mucha programación en Java y está familiarizado con el marco de recopilación de Java, piense en listas como LinkedListy vectores similares ArrayList. Así que puedes elegir contenedores de la misma manera.

Para una mayor aclaración: si tiene la intención de agregar elementos individualmente al principio o al final de la secuencia, una lista vinculada es mucho mejor que un vector, ya que los elementos no necesitan ser barajados cada vez. Sin embargo, si desea llegar a elementos específicos (no cerca del frente o al final de la lista) con frecuencia (es decir, acceso aleatorio), querrá usar el vector.

Por cierto, los vectores se pueden convertir fácilmente en seqs.

user=> (def v (vector 1 2 3))
#'user/v
user=> v
[1 2 3]
user=> (seq v)
(1 2 3)
user=> (rseq v)
(3 2 1)
Chris Jester-Young
fuente
Los vectores no son seqs, pero son secuenciales. (fuente: Rich mismo en #clojure en freenode). Además, realmente no conozco Java en absoluto, pero Rich solo respondió mi pregunta.
Rayne
1
Editaré mi publicación para decir que los vectores se pueden convertir en seqs, a través de la función seq. :-)
Chris Jester-Young
2
Elegí tu respuesta porque efectivamente respondió la pregunta, y realmente no me gusta elegir mis propias respuestas como correctas. No parece correcto Gracias. :)
Rayne
Una deque es mejor que una lista vinculada en el caso de agregar primero y último. Los LL son bastante terribles: P
caja el
1
@boxed No puede implementar una deque encima de un vector o ArrayListsin, efectivamente, reimplementándose ArrayDeque.
Chris Jester-Young
43

Los vectores tienen O (1) tiempos de acceso aleatorio, pero deben ser preasignados. Las listas se pueden extender dinámicamente, pero acceder a un elemento aleatorio es O (n).

Svante
fuente
3
Técnicamente, las listas vinculadas tienen tiempos de acceso O (1) ... si solo está accediendo al elemento frontal o posterior. :-P Sin embargo, los vectores tienen O (1) acceso aleatorio. :-)
Chris Jester-Young
44
("Lista vinculada" como se describió anteriormente se refiere a listas doblemente vinculadas. Las listas individualmente vinculadas tienen O (1) acceso solo al elemento frontal. :-P)
Chris Jester-Young
1
Como alguien que simplemente se sumerge en Clojure, esta es una respuesta MUCHO mejor que las otras dos con más votos. Los otros dos no me dicen nada de utilidad.
keithjgrant
@ ChrisJester-Young La lista de enlaces únicos puede admitir el acceso O (1) a la parte posterior si almacena una referencia al elemento posterior, de esa manera .
Gill Bates
30

Cuando usar un vector:

  • Rendimiento de acceso indexado: obtiene ~ O (1) costo por acceso indexado frente a O (n) para listas
  • Anexar - con conj es ~ O (1)
  • Notación conveniente: me resulta más fácil escribir y leer [1 2 3] que '(1 2 3) para obtener una lista literal en circunstancias en las que cualquiera de los dos funcionaría.

Cuándo usar una lista:

  • Cuando desee acceder a él como una secuencia (ya que las listas admiten directamente seq sin tener que asignar nuevos objetos)
  • Previo - agregando al inicio de una lista con contras o preferiblemente conj es O (1)
mikera
fuente
3
Incluso al agregar / eliminar en ambos extremos, una lista es una elección bastante terrible. Una deque es mucho mejor (en la CPU y especialmente en la memoria). Pruebe github.com/pjstadig/deque-clojure
caja el
2
Re: the ~O(1), para aquellos a quienes esta explicación de costos podría ser útil - stackoverflow.com/questions/200384/constant-amortized-time
Merlyn Morgan-Graham
13

solo una nota al margen rápida:

"Leí que los vectores no son seqs, pero las listas sí". 

Las secuencias son más genéricas que las listas o los vectores (o los mapas o conjuntos).
Es desafortunado que REPL imprima listas y secuencias de la misma manera porque realmente hace que parezca que las listas son secuencias a pesar de que son diferentes. la función (seq) creará una secuencia de muchas cosas diferentes, incluidas listas, y luego puede alimentar esa seq a cualquiera de la gran cantidad de funciones que hacen cosas ingeniosas con seqs.

user> (class (list 1 2 3))
clojure.lang.PersistentList

user> (class (seq (list 1 2 3)))
clojure.lang.PersistentList

user> (class (seq [1 2 3]))
clojure.lang.PersistentVector$ChunkedSeq

Sec tiene un acceso directo que devuelve su argumento si ya es un seq:

user> (let [alist (list 1 2 3)] (identical? alist (seq alist)))
true
user> (identical? (list 1 2 3) (seq (list 1 2 3)))
false

static public ISeq seq(Object coll){
        if(coll instanceof ASeq)
                return (ASeq) coll;
        else if(coll instanceof LazySeq)
                return ((LazySeq) coll).seq();
        else
                return seqFrom(coll);
}

las listas son secuencias, aunque otras cosas también lo son, y no todas las secuencias son listas.

Arthur Ulfeldt
fuente
No me refiero a elegir un punto pequeño, es solo una oportunidad para señalar algo útil. muchos ya sabrán esto :)
Arthur Ulfeldt
2
¿No quieres decir en classlugar de class??
qerub
No estoy seguro de si su ejemplo ha cambiado después de las actualizaciones de clojure (creo que estoy en 1.5), pero ambos ejemplos clojure.lang.PersistentListme son devueltos . Supongo que querías escribir classno class?.
Adrian Mouat
¡En efecto lo hice! Lo arreglaré
Arthur Ulfeldt
Todavía un poco confundido; dado que classdevuelve la misma lista persistente para ambas expresiones que mencionó, ¿esto implica que las secuencias y las listas son exactamente lo mismo?
johnbakers