Clasificación de algoritmos y interfaz de línea de comandos -- performance campo con beginner campo con sorting campo con clojure campo con mergesort camp codereview Relacionados El problema

Sorting algorithms and command-line interface


2
vote

problema

Español

He implementado algunos algoritmos de clasificación (a saber, item1 item2 ), así como una interfaz de línea de comandos, en Clojure por diversión y para probar mis habilidades de Clojure (He manipulado con Clojure por un tiempo ahora, pero sigo siendo bastante principiante).

El código se ve bien, pero creo que el estilo de algunas partes del código podría usar la mejora (principalmente el 99887766655443313 implementación, que se ve muy detalladamente verbosa). Además de eso, podría usar otras mejoras en general, como la velocidad y el rendimiento, especialmente con listas más grandes.

Core.clj:

  item4  

Comando-line.clj:

  item5  
Original en ingles

I have implemented both some sorting algorithms (namely bubble sort and merge sort), as well as a command-line interface, in Clojure for fun and to test my Clojure abilities (I've tampered with Clojure for a while now, but I'm still quite a beginner).

The code looks alright, but I think the styling of some parts of the code could use improvement (mainly the merge sort implementation, which looks awfully verbose). As well as that, I could use some other improvements in general, such as speed and performance, especially with larger lists.

core.clj:

(ns experiments.core   (:gen-class)   (:require [experiments.command-line :as cl]))  (defn bubble-sort [array]   (loop [ind 0          sort-arr array          swaps? 0]     (if (= ind (dec (count array)))       (if (not= swaps? 0)         (bubble-sort sort-arr))       (if (> (nth sort-arr ind) (nth sort-arr (inc ind)))         (let           [temp-arr             (vec               (concat                 (subvec sort-arr 0 ind)                 [(nth sort-arr (inc ind))]                 [(nth sort-arr ind)]                 (subvec sort-arr (+ ind 2))))]           (do             (println temp-arr)             (recur (inc ind) temp-arr (inc swaps?))))         (recur (inc ind) sort-arr swaps?)))))  (defn merge-sort [array]   (defn split-array [arr]     (loop [orig arr final []]       (if (< (count orig) 2)         (if (= (count orig) 1)           (conj final orig)           final)         (recur           (subvec orig 2)           (conj final (subvec orig 0 2))))))   (defn sort-two [[a b]]      (loop [arr-a a             arr-b b             final []]        (if          (or            (empty? arr-a)            (empty? arr-b))          (vec            (concat              final              (if (empty? arr-a) arr-b arr-a)))          (if (> (first arr-a) (first arr-b))            (recur              arr-a              (vec (rest arr-b))              (conj final (first arr-b)))            (recur              (vec (rest arr-a))              arr-b              (conj final (first arr-a)))))))   (loop     [sort-arr       (split-array         (vec           (for [a (range (count array))] [(nth array a)])))]     (if (= (count sort-arr) 1)       (println (sort-two sort-arr))       (recur         (split-array           (loop [ind 0                  temp-arr sort-arr]             (println temp-arr)             (if (= ind (count temp-arr)) temp-arr               (recur                 (inc ind)                 (vec                     (concat                       (subvec temp-arr 0 ind)                       [(if (= (count (nth temp-arr ind)) 1)                          (nth (nth temp-arr ind) 0)                          (sort-two (nth temp-arr ind)))]                       (subvec temp-arr (inc ind))))))))))))  (defn gen-random-array [length]   (loop [arr []]     (if (= (count arr) length) arr       (let [rand-val (rand-int length)]         (if (some #{rand-val} arr)           (recur arr)           (recur (conj arr rand-val)))))))  (defn init-args []   (cl/add-arg "-b" "bubble"     ["Print the procedure of bubble-sorting,"      "given an arbitrary amount of arguments."]     (fn       ([]        (bubble-sort          (gen-random-array 10)))       ([args]        (bubble-sort          (vec            (for [a (range (count args))]              (read-string (nth args a))))))))   (cl/add-arg "-m" "merge"     ["Print the procedure of merge-sorting,"      "given an arbitrary amount of arguments."]     (fn       ([]        (merge-sort          (gen-random-array 10)))       ([args]        (merge-sort          (vec            (for [a (range (count args))]              (read-string (nth args a))))))))   (cl/add-arg "-r" "random"     ["Generate a random array."]     (fn       ([args]        (println          (gen-random-array            (read-string (nth args 0))))))))  (defn -main [& args]   (init-args)   (cl/parse-arg (vec args))) 

command-line.clj:

(ns experiments.command-line   (:gen-class)   (:require [clojure.string :as string]))  (def names (atom [["-h" "help"]])) (def docs (atom [[""]])) (def funcs (atom [(fn [] ())]))  (defn add-arg [s-name l-name arg-doc func]   (swap! names conj [s-name l-name])   (swap! docs conj arg-doc)   (swap! funcs conj func))  (defn disp-help []   (println "\nCommands: ")   (loop [a 1]     (if (= a (count @names))       (print "")       (do         (println "  "           (nth (nth @names a) 0) "\b,"           (nth (nth @names a) 1) "\b:\n   "           (string/join "\n    "             (nth @docs a)))         (println "")         (recur (+ a 1))))))  (defn parse-arg [args]   (let [main-arg (nth args 0)         other-args (subvec args 1)]     (loop [a 0]       (if (= a (count @names))         (println "No match!")         (if           (or             (= main-arg (nth (nth @names a) 0))             (= main-arg (nth (nth @names a) 1)))           (if (= a 0)             (disp-help)             ((nth @funcs a) other-args))           (recur (+ a 1))))))) 
              
 
 

Lista de respuestas

1
 
vote

Vamos a tratar con bubble-sort .


El formulario if

    (if (not= swaps? 0)     (bubble-sort sort-arr))   

... no tiene expresión para lo que sucede si la condición falla, por lo tanto, devuelve nil . Lo anterior necesita ser ...

    (if (not= swaps? 0)     (bubble-sort sort-arr)     sort-arr)   

Esto funciona.


A continuación, cada vez que realice un intercambio, reconstruye un vector completo usando concat . Es más rápido y más leído usar assoc para cambiar los dos elementos vecinos:

  s = ScoreDetail(**item) 0  

También he usado s = ScoreDetail(**item) 1 Para ordenar el s = ScoreDetail(**item) 2 Miramos antes.


Otro par de mejoras:

La función s = ScoreDetail(**item) 3 realiza una llamada recursiva para cada pase a través del vector. Esto le limita a secuencias alrededor de 10k de largo, dependiendo de cómo se configura el JVM. De lo contrario, obtienes el desbordamiento de la pila.

La solución es reemplazar la llamada recursiva s = ScoreDetail(**item) 4 CON EL EQUIVALENTE s = ScoreDetail(**item) 5 . También debemos reemplazar la referencia a s = ScoreDetail(**item) 6 con uno a s = ScoreDetail(**item) 7 , dado que 99887776655443318 ya no se renueva en cada pase. Así que reemplazamos

  s = ScoreDetail(**item) 9  

con ...

  json0  

Esto funciona. Prueba ...

  json1  

antes y después.


Un desajuste fundamental es que la clasificación de burbujas funciona por la actualización en el lugar, mientras que las estructuras de datos principales de Clojure son persistentes, no puede cambiarlos. Lo que vuelve de json2 y similares es una versión modificada del original que comparte la mayor parte de su estructura. Esto lleva un costo sustancial en el rendimiento.

Dado que no está utilizando la persistencia del vector, puede usar transitors . Esto reduce considerablemente el costo de las actualizaciones - YMMV. Para hacerlo,

  • Uso json3 Para crear la versión transitoria.
  • Reemplazar json4 Con json5
  • Uso json6 para recuperar una versión persistente.

Tenemos ...

  json7  

Esto parece correr un poco más rápido, aunque sigue siendo horriblemente lento en comparación con el núcleo json8 .

 

Let's deal with bubble-sort.


The if form

  (if (not= swaps? 0)     (bubble-sort sort-arr)) 

... has no expression for what happens if the condition fails, hence then returns nil. The above needs to be ...

  (if (not= swaps? 0)     (bubble-sort sort-arr)     sort-arr) 

This works.


Next, every time you do a swap, you reconstruct an entire vector using concat. It is faster and neater to use assoc to exchange the two neighbouring elements:

(defn bubble-sort [array]   (loop [ind 0          sort-arr array          swaps? 0]     (if (= ind (dec (count array)))       (if (zero? swaps?)         array         (bubble-sort sort-arr))       (if (> (nth sort-arr ind) (nth sort-arr (inc ind)))         (let [temp-arr (assoc sort-arr                          ind (sort-arr (inc ind))                          (inc ind) (sort-arr ind))]           (recur (inc ind) temp-arr (inc swaps?)))         (recur (inc ind) sort-arr swaps?))))) 

I've also used zero? to tidy up the if we looked at before.


Another couple of improvements:

The bubble-sort function performs a recursive call for each pass through the vector. This limits it to sequences about 10K long, depending on how the JVM is configured. Otherwise you get stack overflow.

The solution is to replace the recursive call (bubble-sort sort-arr) with the equivalent (recur 0 sort-arr 0). We also need to replace the reference to array with one to sort-arr, since array is no longer renewed on every pass. So we replace

(if (zero? swaps?)   array   (bubble-sort sort-arr)) 

with ...

(if (zero? swaps?)   sort-arr   (recur 0 sort-arr 0)) 

This works. Try ...

(-> (range 10000 0 -1) vec bubble-sort) 

before and after.


A fundamental mismatch is that bubble sort works by update-in-place, whereas clojure's core data structures are persistent - you can't change them. What you get back from assoc and the like is a modified version of the original which shares most of its structure. This carries a substantial cost in performance.

Since you are not using the persistence of the vector, you can use transients. This reduces the cost of updates considerably - YMMV. To do so,

  • Use transient to create the transient version.
  • Replace assoc with assoc!
  • Use persistent! to recover a persistent version.

We get ...

(defn bubble-sort [array]   (loop [ind 0          sort-arr (transient array)          swaps? 0]     (if (= ind (dec (count array)))       (if (zero? swaps?)         (persistent! sort-arr)         (recur 0 sort-arr 0))       (if (> (nth sort-arr ind) (nth sort-arr (inc ind)))         (let [temp-arr (assoc! sort-arr                          ind (sort-arr (inc ind))                          (inc ind) (sort-arr ind))]           (recur (inc ind) temp-arr (inc swaps?)))         (recur (inc ind) sort-arr swaps?))))) 

This seems to run a bit quicker, though it's still horribly slow compared to the core sort.

 
 
       
       

Relacionados problema

2  Fusionar la implementación de Sort Java  ( Merge sort java implementation ) 
¿Puede alguien revisar mi implementación de tipo de fusión en Java? ¿Es bueno / malo y puede mejorarse más? public class MyMergeSort { private int [] d...

1  Merge Sort in PHP - Mi primera exposición algorítmica a PHP 5  ( Merge sort in php my first algorithmic exposure to php 5 ) 
Tengo este pequeño programa en PHP implementando una especie de combinación. Utilicé una optimización de tiempo de ejecución bastante simple mediante el uso d...

6  Fusionar la implementación de ordenación en Java  ( Merge sort implementation in java ) 
¿Puedes revisar mi implementación de tipo de fusión? De todas mis pruebas, parece que funciona, pero solo quería asegurarme de que lo estoy haciendo lo mejor ...

6  Algoritmo para encontrar inversiones en tipo MERGE  ( Algorithm for finding inversions in merge sort ) 
Ayuda en las revisiones de código para la legibilidad, optimizándola, funcionalidad, etc. import java.io.BufferedReader; import java.io.FileNotFoundExcepti...

2  Merge rápido en JavaScript  ( Fast merge sort in javascript ) 
Al desarrollar una interfaz de usuario que permite la clasificación por varios campos diferentes, noté que Array.prototype.sort() es extremadamente lento pa...

7  Merge Sort en JavaScript  ( Merge sort in javascript ) 
Implementé este tipo de fusión en JS y noté que para los números de enteros aleatorios es mucho más rápido que la construcción en funciones de tipo de todos l...

2  Algoritmo de Mergesort en C  ( Mergesort algorithm in c ) 
Tengo esta implementación de Mergesort que tiene exactamente la misma API que qsort : : Mergesort.h : #ifndef MERGESORT_H #define MERGESORT_H #inclu...

12  Fusionar una especie de una matriz entera  ( Merge sort an integer array ) 
He implementado fusionar una matriz entera. ¿Está bien usar I, J, k como nombre de variable para bucle? ¿Debo cambiarlos a nombres más significativos? En gene...

2  Fusión natural Sort En C  ( Natural merge sort in c ) 
Tengo esta implementación C del tipo de combinación natural: #include "stable_sort.h" #include <stdbool.h> #include <stdlib.h> #include <stdio.h> #include ...

5  Memoria / Performance of Merge Sort Code  ( Memory performance of merge sort code ) 
Escribí un código de tipo de combinación para un poco de bocadillo nocturno. Lo he puesto trabajando, pero solo estaba mirando a aprender si me faltaba algo e...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos