Anteponiendo a una lista es fácil:

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

Anexar a un vector es fácil:

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

¿Cómo puedo (idiomáticamente) anteponer a un vector, mientras que obtener un vector?
Esto no funciona como se devuelve un seq, no un vector:

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

Esta es feo (IMVHO):

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

Nota: yo, básicamente, sólo quiero un discbased que puedo anexar y anteponer. Anexar a las listas de gran tamaño debe tener una gran penalización de rendimiento, por lo que pensé de vectores..

  • Sería negligente de mi parte no señalar que la final de la ‘fea’ ejemplo puede ser simplificado en un poco menos feo forma: (apply vector :foo [:bar :baz]) (acaba de salir el cons). Pero estoy de acuerdo es un poco torpe que, más allá de la (vector ...) solución, hay básicamente sólo concat. Si sólo hubo un azucaradas/bastante sintaxis para splatting argumentos, en lugar de apply (como [email protected] pero no solo para macros)… suspiro
InformationsquelleAutor 0x89 | 2010-11-04

5 Comentarios

  1. 71

    Vectores no están diseñados para anteponiendo. Sólo has de O(n) anteponer:

    user=> (into [:foo] [:bar :baz])
    [:foo :bar :baz]

    Lo que quieres es más probable que un dedo árbol.

    • +1 para los dedos de los árboles – una muy buena estructura de datos!!
    • Buena manera de poner las diapositivas en línea: talk-finger-tree.heroku.com
    • rrb-vectores pueden ser concatenados (y por lo tanto antepone) en O(log n) tiempo. Consulte github.com/clojure/core.rrb-vector
    • Me gustaría recomendar la rrb-vectores, demasiado. He encontrado este post y después de la excavación en el Clojure lista de correo, me encontré con otros dos libs que se suponía que iban a reemplazar los datos.dedo del árbol y agregar ClojureScript de apoyo. rrb-vector es un contrib proyecto mantenido por Michał Marczyk, que es un respetado colaborador dentro de la Clojure de la comunidad. No es que los autores de las otras librerías no, es sólo que yo–ser un Clojure novato–no lo reconocen.
    • No hay ninguna razón real por la que Clojure del Vector no se puede hacer una anteponer con la complejidad mismo tiempo como un anexados. He implementado esta en Ir, aquí: github.com/d11wtq/persistent/tree/feature/prepend. La solución es 1) Recordar un «desplazamiento de inicio» (por defecto = 0) y el uso que en todo el árbol de operaciones. 2) Cuando anteponiendo, si «inicio» offset = 0, asignar un nuevo nodo raíz, la posición de la antigua nodo raíz hasta la mitad dentro de ella y actualizar el «desplazamiento de inicio» para esta posición. 3) En todos los demás casos, añade, a continuación, sólo se convierte en un caso de disminución de la del «offset» y haciendo un normal assoc en el índice 0.
    • Las preocupaciones acerca de la memoria de residuos en el que el diseño se eliminan por la pereza de inicializar los nodos sólo cuando se van a almacenar los datos. Un shift operación (pop a la izquierda) se logra mediante el incremento de la del «offset» y haciendo un assoc null en el elemento cero. Se debe tener cuidado para quitar nodos caminos seguidos por los índices de < «desplazamiento de inicio» que tendría.
    • No he explorado todavía, pero tengo la sospecha de split y concat se podría hacer en O(log32(n)), de manera efectiva, O(1) utilizando la misma estructura de datos de la manipulación.

  2. 17

    Sé que esta pregunta es viejo, pero nadie dijo nada acerca de la diferencia
    listas y ya que dicen que en realidad sólo quieren algo que se puede anexar
    y anteponer con, suena a diferencia de las listas podrían ser de ayuda.
    No parecen muy popular en Usa, pero son MUY fáciles de
    para implementar y mucho menos complejo que el dedo de los árboles, así que he hecho un
    pequeña diferencia de la lista de la biblioteca, justo ahora (y probado incluso). Estos
    concatenar en O(1) tiempo (anteponer o append). La conversión de una diferencia
    lista a una lista de coste O(n), que es un buen trade-off si
    usted está haciendo una gran cantidad de concatenación. Si usted no está haciendo un montón de
    concatenación, a continuación, sólo se adhieren a las listas, ¿verdad? 🙂

    Aquí son las funciones en esta pequeña biblioteca:

    dl: Una diferencia de lista en realidad es una función que concats su propia
    contenido con el argumento y devuelve la lista resultante. Cada vez
    producir una diferencia de lista, usted puede crear una función poco que
    actúa como una estructura de datos.

    dlempty: Ya que una diferencia de lista sólo concats su contenido a la
    argumento, un vacío diferencia de la lista es la misma cosa como la identidad
    función.

    undl: Debido a lo que los diferencia de las listas, usted puede convertir un
    diferencia de la lista a una lista normal solo llamando con nil, por lo que este
    la función no es realmente necesario, es sólo por conveniencia.

    dlcons: conses un elemento al frente de la lista-no totalmente
    es necesario, pero consing es bastante corriente de la operación y es sólo un
    one-liner (como todas las funciones, aquí).

    dlappend: concats la diferencia de dos listas. Creo que su definición es
    la mayoría de la diversión — check it out! 🙂

    Y ahora, aquí está la pequeña biblioteca — 5-funciones de la línea que le dan un O(1)
    anexar/prepend estructura de datos. No está mal, eh? Ah, la belleza de Lambda
    Cálculo…

    (defn dl
      "Return a difference list for a list"
      [l]
      (fn [x] (concat l x)))
    
    ; Return an empty difference list
    (def dlempty identity)
    
    (defn undl
      "Return a list for a difference list (just call the difference list with nil)"
      [aDl]
      (aDl nil))
    
    (defn dlcons
      "Cons an item onto a difference list"
      [item aDl]
      (fn [x] (cons item (aDl x))))
    
    (defn dlappend
      "Append two difference lists"
      [dl1 dl2]
      (fn [x] (dl1 (dl2 x))))

    Se puede ver en acción con este:

    (undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))

    que devuelve:

    (1 2 3 4 5 6)

    Esto también se vuelve la misma cosa:

    ((dl '(1 2 3)) '(4 5 6))

    Divertirse con diferencia listas!

    Actualización

    Aquí son algunas definiciones que pueden ser más difíciles de entender, pero creo que son mejores:

    (defn dl [& elements] (fn [x] (concat elements x)))
    (defn dl-un [l] (l nil))
    (defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

    Esto le permite a usted decir algo como esto:

    (dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

    Que volver

    (1 2 3 4)
  3. 2

    A medida que el usuario optevo dijo en los comentarios bajo el dedo de árboles de respuesta, usted puede utilizar el clojure/core.rrb-vector lib, que implementa la RRB-árboles:

    RRB-Árboles de construir sobre Clojure del PersistentVectors, adición de tiempo logarítmico de concatenación y cortarlo en rodajas. ClojureScript es compatible con la misma API, excepto por la ausencia de la vector-of función.

    Decidí publicar esto por separado como una respuesta, porque creo que esta biblioteca se merece eso. Es compatible con ClojureScript y es mantenido por Michał Marczyk, que es bastante conocido dentro de la Clojure de la comunidad por su trabajo en la implementación de diversas estructuras de datos.

  4. 1

    Me gustaría sugerir el uso de las características de la conveniencia construido en la Biblioteca de Tupelo. Por ejemplo:

    (append [1 2] 3  )   ;=> [1 2 3  ]
    (append [1 2] 3 4)   ;=> [1 2 3 4]
    
    (prepend   3 [2 1])  ;=> [  3 2 1]
    (prepend 4 3 [2 1])  ;=> [4 3 2 1]

    por comparación, con el formato raw, Clojure es fácil cometer un error:

    ; Add to the end
    (concat [1 2] 3)    ;=> IllegalArgumentException
    (cons   [1 2] 3)    ;=> IllegalArgumentException
    (conj   [1 2] 3)    ;=> [1 2 3]
    (conj   [1 2] 3 4)  ;=> [1 2 3 4]
    
    ; Add to the beginning
    (conj     1 [2 3] ) ;=> ClassCastException
    (concat   1 [2 3] ) ;=> IllegalArgumentException
    (cons     1 [2 3] ) ;=> (1 2 3)
    (cons   1 2 [3 4] ) ;=> ArityException
  5. 1

    Si no miedo quasiquoting, esta solución es realmente muy elegante (para algunas de las definiciones de ‘elegante’):

    > `[~:foo [email protected][:bar :baz]]
    
    [:foo :bar :baz]

    Puedo utilizar este en alguna ocasión en el código real, ya que la sintaxis declarativa hace bastante legible en mi humilde opinión.

Dejar respuesta

Please enter your comment!
Please enter your name here