online - clojurescript
Quicksort en Clojure (4)
Al examinar los puntos principales de la respuesta de mikera, puede ver que se centran principalmente en eliminar la sobrecarga introducida mediante el uso de Clojure idiomático (en lugar de modificado), que probablemente no existiría en una implementación idiomática de Java:
- Aritmética primitiva : un poco más fácil y más idiomático en Java, es más probable que use
ints queIntegers - ints para los índices de matriz - el mismo
- Use macros en lugar de funciones para dividir el código (evita la sobrecarga funcional de llamadas y el boxeo) : corrige un problema introducido al usar el idioma. Clojure fomenta el estilo funcional, por lo tanto, una función llamada sobrecarga (y boxeo).
- Use loop / recurre para obtener la máxima velocidad en el bucle interno : en Java usaría idiomáticamente un bucle ordinario (que es lo que el bucle / recurrir compila de todos modos, hasta donde sé)
Dicho esto, en realidad hay otra solución trivial. Escriba (o encuentre) una implementación eficiente de Java de Ordenación rápida, diga algo con una firma como esta:
Sort.quickSort(long[] elems)
Y luego llámalo desde Clojure:
(Sort/quickSort elems)
Lista de verificación:
tan eficiente como en Java - si
idiomático en Clojure - podría decirse que sí , yo diría que la interoperabilidad de Java es una de las características principales de Clojure.
reutilizable: sí , hay una buena posibilidad de que pueda encontrar fácilmente una implementación Java muy eficiente ya escrita.
No estoy tratando de hacer un troll, entiendo lo que estás tratando de descubrir con estos experimentos. Solo estoy agregando esta respuesta para completar. ¡No olvidemos lo obvio! :)
Estoy tratando de demostrar que el rendimiento de Clojure puede estar en pie de igualdad con Java. Un caso de uso importante que he encontrado es el Quicksort. He escrito una implementación de la siguiente manera:
(set! *unchecked-math* true)
(defn qsort [^longs a]
(let [qs (fn qs [^long low, ^long high]
(when (< low high)
(let [pivot (aget a low)
[i j]
(loop [i low, j high]
(let [i (loop [i i] (if (< (aget a i) pivot)
(recur (inc i)) i))
j (loop [j j] (if (> (aget a j) pivot)
(recur (dec j)) j))
[i j] (if (<= i j)
(let [tmp (aget a i)]
(aset a i (aget a j)) (aset a j tmp)
[(inc i) (dec j)])
[i j])]
(if (< i j) (recur i j) [i j])))]
(when (< low j) (qs low j))
(when (< i high) (qs i high)))))]
(qs 0 (dec (alength a))))
a)
Además, esto ayuda a llamar al Java quicksort:
(defn jqsort [^longs a] (java.util.Arrays/sort a) a))
Ahora, para el punto de referencia.
user> (def xs (let [rnd (java.util.Random.)]
(long-array (repeatedly 100000 #(.nextLong rnd)))))
#''user/xs
user> (def ys (long-array xs))
#''user/ys
user> (time (qsort ys))
"Elapsed time: 163.33 msecs"
#<long[] [J@3ae34094>
user> (def ys (long-array xs))
user> (time (jqsort ys))
"Elapsed time: 13.895 msecs"
#<long[] [J@1b2b2f7f>
El rendimiento es mundos separados (un orden de magnitud, y luego algunos).
¿Hay algo que me esté perdiendo, alguna característica de Clojure que pueda haber usado? Creo que la principal fuente de degradación del rendimiento es cuando necesito devolver varios valores de un bucle y debo asignar un vector para eso. ¿Se puede evitar esto?
BTW corriendo Clojure 1.4. También tenga en cuenta que he ejecutado el punto de referencia varias veces para calentar el HotSpot. Estos son los tiempos en que se asientan.
Actualizar
La debilidad más terrible de mi código no es solo la asignación de vectores, sino el hecho de que fuerzan el boxeo y rompen la cadena primitiva. Otra debilidad es usar los resultados del loop porque también rompen la cadena. Sí, el rendimiento en Clojure sigue siendo un campo minado.
Esta versión se basa en @mikera''s, es igual de rápida y no requiere el uso de macros feas. En mi máquina esto toma ~ 12ms vs ~ 9ms para java.util.Arrays / sort:
(set! *unchecked-math* true)
(set! *warn-on-reflection* true)
(defn swap [^longs a ^long i ^long j]
(let [t (aget a i)]
(aset a i (aget a j))
(aset a j t)))
(defn ^long apartition [^longs a ^long pivot ^long i ^long j]
(loop [i i j j]
(if (<= i j)
(let [v (aget a i)]
(if (< v pivot)
(recur (inc i) j)
(do
(when (< i j)
(aset a i (aget a j))
(aset a j v))
(recur i (dec j)))))
i)))
(defn qsort
([^longs a]
(qsort a 0 (long (alength a))))
([^longs a ^long lo ^long hi]
(when
(< (inc lo) hi)
(let [pivot (aget a lo)
split (dec (apartition a pivot (inc lo) (dec hi)))]
(when (> split lo)
(swap a lo split))
(qsort a lo split)
(qsort a (inc split) hi)))
a))
(defn ^longs rand-long-array []
(let [rnd (java.util.Random.)]
(long-array (repeatedly 100000 #(.nextLong rnd)))))
(comment
(dotimes [_ 10]
(let [as (rand-long-array)]
(time
(dotimes [_ 1]
(qsort as)))))
)
La necesidad de alineación manual es en su mayoría innecesaria a partir de Clojure 1.3. Con algunos consejos de tipo solo en los argumentos de la función, la JVM realizará la integración por usted. No es necesario convertir los argumentos de índice a int para las operaciones de matriz; Clojure lo hace por usted.
Una cosa a tener en cuenta es que el bucle / repetición anidados presenta problemas para la incorporación de JVM, ya que el bucle / repetición no admite (en este momento) primitivas de retorno. Así que tienes que dividir tu código en fns separados. Esto es lo mejor, ya que los bucles / repeticiones anidados se vuelven muy feos en Clojure de todos modos.
Para ver más detalladamente cómo lograr el rendimiento de Java (cuando realmente lo necesita), examine y entienda test.benchmark .
Esto es un poco horrible debido a las macros, pero con este código creo que puedes igualar la velocidad de Java (obtengo alrededor de 11 ms para el punto de referencia):
(set! *unchecked-math* true)
(defmacro swap [a i j]
`(let [a# ~a
i# ~i
j# ~j
t# (aget a# i#)]
(aset a# i# (aget a# j#))
(aset a# j# t#)))
(defmacro apartition [a pivot i j]
`(let [pivot# ~pivot]
(loop [i# ~i
j# ~j]
(if (<= i# j#)
(let [v# (aget ~a i#)]
(if (< v# pivot#)
(recur (inc i#) j#)
(do
(when (< i# j#)
(aset ~a i# (aget ~a j#))
(aset ~a j# v#))
(recur i# (dec j#)))))
i#))))
(defn qsort
([^longs a]
(qsort a 0 (alength a)))
([^longs a ^long lo ^long hi]
(let [lo (int lo)
hi (int hi)]
(when
(< (inc lo) hi)
(let [pivot (aget a lo)
split (dec (apartition a pivot (inc lo) (dec hi)))]
(when (> split lo) (swap a lo split))
(qsort a lo split)
(qsort a (inc split) hi)))
a)))
Los principales trucos son:
- Hacer todo con aritmética primitiva.
- Use ints para los índices de matriz (esto evita algunos lanzamientos innecesarios, no es un gran problema, pero todo ayuda ...)
- Utilice macros en lugar de funciones para dividir el código (evita la sobrecarga de llamadas a funciones y el cuadro de parámetros)
- Utilice bucle / repetición para obtener la máxima velocidad en el bucle interno (es decir, partición del subconjunto)
- Evite construir nuevos objetos en el montón (evite vectores, secuencias, mapas, etc.)
The Joy of Clojure , Capítulo 6.4 describe un algoritmo de ordenamiento rápido perezoso. La belleza de la clasificación perezosa es que solo hará todo el trabajo necesario para encontrar los primeros valores de x. Entonces si x << n este algoritmo es O (n).
(ns joy.q)
(defn sort-parts
"Lazy, tail-recursive, incremental quicksort. Works against
and creates partitions based on the pivot, defined as ''work''."
[work]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [smaller? #(< % pivot)]
(recur (list*
(filter smaller? xs)
pivot
(remove smaller? xs)
parts)))
(when-let [[x & parts] parts]
(cons x (sort-parts parts)))))))
(defn qsort [xs]
(sort-parts (list xs)))