Java Merge Sort -- java campo con mergesort camp codereview Relacionados El problema

Java Merge Sort


3
vote

problema

Español

Implementé un tipo de fusión en Java. ¿Hay alguna manera de mejorarlo? Sospecho que, en particular, la parte fusionada podría mejorarse.

Nota: eliminé deliberadamente todos los comentarios.

  private static void mergeSort(int[] values) {    if (values.length < 2) {       return;    }     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    }     for (int i = middle; i < values.length; i++) {       right[i - middle] = values[i];    }     mergeSort(left);    mergeSort(right);    merge(left, right, values); }  private static void merge(int[] left, int[] right, int[] values) {    int leftPosition = 0;    int rightPosition = 0;    int position = 0;     while (leftPosition < left.length && rightPosition < right.length) {       if (left[leftPosition] <= right[rightPosition]) {          values[position++] = left[leftPosition++];       } else {          values[position++] = right[rightPosition++];       }    }     while (leftPosition < left.length) {       values[position++] = left[leftPosition++];    }    while (rightPosition < right.length) {       values[position++] = right[rightPosition++];    } }   
Original en ingles

I implemented a merge sort in Java. Is there any way to improve it? I suspect that in particular the merging part could be improved.

Note: I deliberately removed all the comments.

private static void mergeSort(int[] values) {    if (values.length < 2) {       return;    }     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    }     for (int i = middle; i < values.length; i++) {       right[i - middle] = values[i];    }     mergeSort(left);    mergeSort(right);    merge(left, right, values); }  private static void merge(int[] left, int[] right, int[] values) {    int leftPosition = 0;    int rightPosition = 0;    int position = 0;     while (leftPosition < left.length && rightPosition < right.length) {       if (left[leftPosition] <= right[rightPosition]) {          values[position++] = left[leftPosition++];       } else {          values[position++] = right[rightPosition++];       }    }     while (leftPosition < left.length) {       values[position++] = left[leftPosition++];    }    while (rightPosition < right.length) {       values[position++] = right[rightPosition++];    } } 
     
 
 

Lista de respuestas

3
 
vote

Arrays.copyOf

     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    }   

Puede reescribir todo menos la declaración como

     int[] left = Arrays.copyOf(values, values.length / 2);   

que declarará una nueva matriz y copiará los valores, por lo que no más atravesar manuales. Además, puede tener un método de copia más optimizado.

Arrays.copyOfRange

     for (int i = middle; i < values.length; i++) {       right[i - middle] = values[i];    }   

Tomando la Declaración de right En el código anterior, podemos escribir

     int[] right = Arrays.copyOfRange(values, left.length, values.length);   

de nuevo, la nueva matriz se crea y copia en combinación.

Combinado, esto nos lleva desde catorce líneas a dos, cortando la longitud general del método por la mitad. Incluso si le devuelve el middle como más comentando, todavía somos considerablemente más cortos.

System.arraycopy

     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    } 0  

Hay un incorporado para esto también.

     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    } 1  

Solo copiará sin crear una nueva matriz. Los dos casos son mutuamente excluyentes, por lo que cambia del int middle = values.length / 2; int leftSize = middle; int rightSize = values.length - middle; int[] left = new int[leftSize]; int[] right = new int[rightSize]; for (int i = 0; i < leftSize; i++) { left[i] = values[i]; } 2 int middle = values.length / 2; int leftSize = middle; int rightSize = values.length - middle; int[] left = new int[leftSize]; int[] right = new int[rightSize]; for (int i = 0; i < leftSize; i++) { left[i] = values[i]; } 3 nos permite agregar un int middle = values.length / 2; int leftSize = middle; int rightSize = values.length - middle; int[] left = new int[leftSize]; int[] right = new int[rightSize]; for (int i = 0; i < leftSize; i++) { left[i] = values[i]; } 4 .

Una posible optimización

Si está realmente desesperado por mejorar el rendimiento y necesita usar esto en lugar de 99887766555443315 , puede intentar cambiar

     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    } 6  

a algo como

     int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    } 7  

Esto es ciertamente menos legible, pero podría ser más rápido. Tendrías que lo comparar para ver. El argumento a favor de que sea más rápido es que el original tiene que hacer tres comparaciones antes de copiar un elemento. Esto solo hace uno en la primera iteración y dos a partir de entonces hasta que se agoten los bucles internos y se inicia.

Es posible que pueda hacerlo aún mejor al no copiar de inmediato y, en su lugar, esperar hasta que sepa cuánto copiar. Luego podría usar int middle = values.length / 2; int leftSize = middle; int rightSize = values.length - middle; int[] left = new int[leftSize]; int[] right = new int[rightSize]; for (int i = 0; i < leftSize; i++) { left[i] = values[i]; } 8 .

Uso de int middle = values.length / 2; int leftSize = middle; int rightSize = values.length - middle; int[] left = new int[leftSize]; int[] right = new int[rightSize]; for (int i = 0; i < leftSize; i++) { left[i] = values[i]; } 9 Con el bucle exterior etiquetado es menos legible en sí mismo, pero es probable que sea la forma más rápida de obtener esta funcionalidad.

Si lo rompimos en dos bucles, podríamos mover el primer 99887766655443320 fuera del bucle.

  right1  

Más código optimizado pero más duplicado. Punto de referencia para asegurarse de que esto no omite a una mejor optimización del compilador.

Guardar memoria

Esto es $ mathcal {o} (n log n) $ en la memoria. Sigues teniendo que asignar nuevas matrices temporales. Podemos lograr la memoria lineal con solo crear una matriz de rasguños primero. Podemos minimizar las copias cambiando entre la matriz de scratch y la matriz original. Consulte una solución de ejemplo aquí si quieres más información.

No solo esto ahorra memoria, sino que reduce el número de asignaciones de memoria también reducirá el tiempo. Las asignaciones de memoria son lentas. Esto también reduce el número de operaciones de copia que deben realizarse.

Mergesort no es eficiente en pequeñas entradas

Esto usa Mergesort hasta dos matrices de elementos. Eso no es necesario. Considere en su lugar usar un método más simple para pequeñas entradas. Por ejemplo, la clasificación de inserción tiene sobrecarga baja y se puede hacer en el lugar. Nuevamente, punto de referencia para encontrar el punto de conmutación óptimo.

 

Arrays.copyOf

   int middle = values.length / 2;    int leftSize = middle;    int rightSize = values.length - middle;     int[] left = new int[leftSize];    int[] right = new int[rightSize];     for (int i = 0; i < leftSize; i++) {       left[i] = values[i];    } 

You can rewrite everything but the right declaration as

   int[] left = Arrays.copyOf(values, values.length / 2); 

That will declare a new array and copy the values, so no more manual traversing. Also, it may have a more optimized copy method.

Arrays.copyOfRange

   for (int i = middle; i < values.length; i++) {       right[i - middle] = values[i];    } 

Taking the declaration of right from the previous code, we can write

   int[] right = Arrays.copyOfRange(values, left.length, values.length); 

Again, the new array is created and copied in combination.

Combined, this gets us from fourteen lines to two, cutting the overall method length in half. Even if you put back middle as more self commenting, we're still considerably shorter.

System.arraycopy

   while (leftPosition < left.length) {       values[position++] = left[leftPosition++];    }    while (rightPosition < right.length) {       values[position++] = right[rightPosition++];    } 

There's a built-in for this as well.

   int remaining = left.length - leftPosition;    if (remaining > 0) {       System.arraycopy(left, leftPosition, values, position, remaining);    } else {       remaining = right.length - rightPosition;       if (remaining > 0) {          System.arraycopy(right, rightPosition, values, position, remaining);       }    } 

It will just copy without creating a new array. The two cases are mutually exclusive, so switching from the while to if lets us add an else.

A possible optimization

If you're really desperate to improve performance and need to use this rather than Arrays.sort, you can try changing

   while (leftPosition < left.length && rightPosition < right.length) {       if (left[leftPosition] <= right[rightPosition]) {          values[position++] = left[leftPosition++];       } else {          values[position++] = right[rightPosition++];       }    } 

to something like

   merging:    while (true) {       if (left[leftPosition] <= right[rightPosition]) {          do {             values[position++] = left[leftPosition++];             if (leftPosition >= left.length) {                break merging;             }          } while (left[leftPosition] <= right[rightPosition]);       }        do {          values[position++] = right[rightPosition++];          if (rightPosition >= right.length) {             break merging;          }       } while (left[leftPosition] > right[rightPosition]);    } 

This is certainly less readable, but it might be faster. You'd have to benchmark it to see. The argument in favor of it being faster is that the original has to do three comparisons before copying an element. This only does one on the first iteration and two thereafter until the inner loops run out and it starts over.

You might be able to do even better by not copying immediately and instead waiting until you know how much to copy. Then you could use System.arraycopy.

Using break with the labelled outer loop is less readable in and of itself, but it is probably the fastest way to get this functionality.

If we broke it up into two loops, we could move the first if out of the loop.

   if (left[leftPosition] <= right[rightPosition]) {       merging1:       while (true) {          do {             values[position++] = left[leftPosition++];             if (leftPosition >= left.length) {                break merging1;             }          } while (left[leftPosition] <= right[rightPosition]);           do {             values[position++] = right[rightPosition++];             if (rightPosition >= right.length) {                break merging1;             }          } while (left[leftPosition] > right[rightPosition]);       }    } else {       merging2:       while (true) {          do {             values[position++] = right[rightPosition++];             if (rightPosition >= right.length) {                break merging2;             }          } while (left[leftPosition] > right[rightPosition]);           do {             values[position++] = left[leftPosition++];             if (leftPosition >= left.length) {                break merging2;             }          } while (left[leftPosition] <= right[rightPosition]);       }    } 

More optimized but more duplicate code. Benchmark to make sure that this doesn't bypass a better compiler optimization.

Saving memory

This is \$\mathcal{O}(n \log n)\$ in memory. You keep having to allocate new temporary arrays. We can achieve linear memory just by creating one scratch array first. We can minimize the copies by switching between the scratch array and the original array. See an example solution here if you want more information.

Not only does this save memory, but reducing the number of memory allocations will reduce the time as well. Memory allocations are slow. This also reduces the number of copy operations that need to be done.

Mergesort is not efficient on small inputs

This uses mergesort all the way down to two element arrays. That's not necessary. Consider instead using a simpler method for small inputs. For example, insertion sort has low overhead and can be done in-place. Again, benchmark to find the optimal switching point.

 
 

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...

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...

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 ...

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  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  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 ...

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  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...

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  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...




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