Clojure: secuencia de vuelta al vector

Question

¿Cómo puedo convertir una secuencia de nuevo en vector después de una operación de producción de secuencia (como ordenar)? ¿Usar (vec ..) en una secuencia que era un vector es costoso?

Uno (mal?) Posibilidad es la creación de un nuevo vector fuera de secuencia:

(vec (sort [1 2 3 4 5 6])) 

Estoy pidiendo porque necesito de acceso aleatorio (enésima ..) a enormes vectores ordenados - que ahora son enormes secuencias después el tipo, con horrible O (n) tiempo de acceso aleatorio

Answer 1

Según mis propias pruebas (nada científicas) puede que sea mejor trabajando directamente en arreglos en los casos en los que se hace mucha ordenación. Pero si ordena poco y tiene un montón de acceso aleatorio, ir con un vector puede ser una mejor opción ya que el tiempo de acceso aleatorio es más del 40% más rápido en promedio, pero el rendimiento de clasificación es horrible debido a la conversión del vector a una matriz y luego de vuelta a un vector. Aquí están mis resultados:

(def foo (int-array (range 1000))) 

(time 
    (dotimes [_ 10000] 
    (java.util.Arrays/sort foo))) 

; Elapsed time: 652.185436 msecs 

(time 
    (dotimes [_ 10000] 
    (nth foo (rand-int 1000)))) 

; Elapsed time: 7.900073 msecs 

(def bar (vec (range 1000))) 

(time 
    (dotimes [_ 10000] 
    (vec (sort bar)))) 

; Elapsed time: 2810.877103 msecs 

(time 
    (dotimes [_ 10000] 
    (nth bar (rand-int 1000)))) 

; Elapsed time: 5.500802 msecs 

P.S .: Tenga en cuenta que la versión del vector en realidad no almacenar el vector ordenados en cualquier lugar, pero eso no debería cambiar el resultado considerablemente como lo haría con fijaciones simples en un bucle de velocidad.

Answer 2

Si necesita acceso aleatorio en el resultado de ordenar con vectores enormes, entonces el tiempo de la llamada a vec debe ser superado por el ahorro de tiempo de hacerlo .

Si hace un perfil y encuentra que es demasiado lento, probablemente tenga que usar matrices Java.

Answer 3

Meikel Brandmeyer acaba de publicar una solución para esto en el grupo Clojure.

(defn sorted-vec 
    [coll] 
    (let [arr (into-array coll)] 
    (java.util.Arrays/sort arr) 
    (vec arr))) 

de Clojure sort devuelve una seq a través de una matriz ordenada; este enfoque hace más o menos lo mismo, pero devuelve un vector, no un seq.

Si lo desea, incluso se puede omitir la conversión de nuevo en una persistente estructura Clojure datos:

(defn sorted-arr 
    "Returns a *mutable* array!" 
    [coll] 
    (doto (into-array coll)] 
    (java.util.Arrays/sort)) 

pero la matriz de Java resultante (que se puede tratar como una colección Clojure en la mayoría de los casos) será mutable . Eso está bien si no lo está entregando a otro código, pero tenga cuidado.

Answer 4

Como un nuevo desarrollador de Clojure, es fácil confundir colecciones y secuencias.

Esta función vector Ordenada:

(tipo [1 2 3 4 5 6]) => (1 2 3 4 5 6); devuelve una secuencia

Pero necesito un vector para la siguiente operación, porque esto no funciona ...

(take-tiempo (parcial> 3) (1 2 3 4 5 6))

=> ClassCastException java.lang.Long no se puede convertir a clojure.lang.IFn usuario/eval2251 (NO_SOURCE_FILE: 2136)

Tratemos de convertir la secuencia a un vector:

(vec (1 2 3 4 5 6))

=> ClassCastException java.lang. Long no se puede convertir en clojure.lang.IFn user/eval2253 (NO_SOURCE_FILE: 2139)

¡No! Pero si lo pones todo junto, funciona bien.

(take-tiempo (parcial> 3) (tipo [1 2 3 4 5 6]))

=> (1 2)

La lección: No se puede trabajar con secuencias directamente! Son un paso intermedio en el proceso. Cuando el REPL trata de evaluar (1 2 3 4 5 6), se ve aa función y produce una excepción:

(1 2 3 4 5 6) => ClassCastException java.lang.Long no puede ser fundido a clojure.lang.IFn user/eval2263 (NO_SOURCE_FILE: 2146)