Ordenar grandes matrices de tipos primitivos en orden descendente

7 minutos de lectura

Avatar de usuario de Benedikt Waldvogel
Benedikt Waldvogel

tengo un largo matriz de tipos primitivos (doble). ¿Cómo clasifico los elementos en orden descendiente?

Desafortunadamente, la API de Java no admite la clasificación de primitivo tipos con un comparador.

El primer enfoque que probablemente le venga a la mente es convertirlo en una lista de objetos (boxing):

double[] array = new double[1048576];    
Arrays.stream(array).boxed().sorted(Collections.reverseOrder())…

Esta solución probablemente sea lo suficientemente buena para muchos (o incluso la mayoría) de los casos de uso, pero boxeo cada primitiva en la matriz es demasiado lento y causa mucha presión en el GC si la matriz es grande!

Otro enfoque sería ordenar y luego revertir:

double[] array = new double[1048576];
...
Arrays.sort(array);
// reverse the array
for (int i = 0; i < array.length / 2; i++) {
     // swap the elements
     double temp = array[i];
     array[i] = array[array.length - (i + 1)];
     array[array.length - (i + 1)] = temp;
}
   

Este enfoque también puede ser demasiado lento. si la matriz ya está ordenada bastante bien.

¿Cuál es una mejor alternativa si los arreglos son grandes y el rendimiento es el principal objetivo de optimización?

avatar de usuario de user29480
usuario29480

Creo que sería mejor no reinventar la rueda y usar Arrays.sort().

Sí, vi la parte “descendente”. La clasificación es la parte difícil y desea beneficiarse de la simplicidad y la velocidad del código de la biblioteca de Java. Una vez hecho esto, simplemente invierte la matriz, que es una operación O(n) relativamente barata. Aquí hay algo de código Encontré hacer esto en tan solo 4 líneas:

for (int left=0, right=b.length-1; left<right; left++, right--) {
    // exchange the first and last
    int temp = b[left]; b[left]  = b[right]; b[right] = temp;
}

  • esta respuesta debe ser aceptada. Es mucho más rápido que las alternativas (boxing + sorting + unboxing, con o sin streams)

    – tucuxi

    18 oct 2021 a las 17:27

  • Ordenar más invertir la matriz es en realidad incluso una solución potencial que encuentra en mi pregunta. Probablemente sea una solución lo suficientemente buena para la mayoría de los casos. Sin embargo, en el caso que estaba preguntando, la velocidad realmente importaba y era probable que la matriz ya estuviera ordenada. En este caso, invertir la matriz es una sobrecarga significativa incluso si es solo una operación O(n). Al final, una optimización como el uso de “Java Primitive” ciertamente solo debería aplicarse si un buen punto de referencia muestra que realmente vale la pena los costos (por ejemplo, la dependencia adicional).

    – Benedikt Waldvogel

    12 de septiembre a las 10:12


Avatar de usuario de Brandon
brandon

Primitivo de Java incluye funcionalidad para clasificar matrices primitivas en función de un comparador personalizado. Al usarlo, y Java 8, su muestra podría escribirse como:

double[] array = new double[1048576];
...
Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false);

Si está utilizando Maven, puede incluirlo con:

<dependency>
    <groupId>net.mintern</groupId>
    <artifactId>primitive</artifactId>
    <version>1.2.1</version>
</dependency>

cuando pasas false como tercer argumento para sortutiliza un tipo inestable, una edición simple de la función integrada de Java clasificación rápida de doble pivote. Esto significa que la velocidad debe ser cercana a la de la clasificación integrada.

Divulgación completa: escribí la biblioteca Java Primitive.

  • Este es un gran proyecto simple en GitHub. ¡Muy buen trabajo! Los lectores también deben tener en cuenta que true como tercer argumento para sort utilizará una edición simple del TimSort incorporado de Java, que es estable.

    – Kevinarpe

    18 de abril de 2016 a las 11:02

Aquí hay una línea, usando flujos en Java 8

int arr = new int[]{1,2,3,4,5};
Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();

  • Boxeo ¡cada primitiva en la matriz es demasiado costosa para matrices grandes!

    – Benedikt Waldvogel

    1 de noviembre de 2019 a las 14:25


  • Excelente, gracias. Es bueno tener una sola línea que funcione con métodos estándar de Java. Si de hecho es demasiado lento para arreglos grandes, siempre es posible refactorizarlo.

    –Eric Duminil

    25 de mayo de 2020 a las 12:28

Guayaba tiene métodos para convertir matrices primitivas en listas de tipos de contenedores. Lo bueno es que estas listas son vistas en vivo, por lo que las operaciones en ellas también funcionan en las matrices subyacentes (similar a Arrays.asList()pero para primitivas).

De todos modos, cada una de estas Listas se puede pasar a Collections.reverse():

int[] intArr = { 1, 2, 3, 4, 5 };
float[] floatArr = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
double[] doubleArr = { 1.0d, 2.0d, 3.0d, 4.0d, 5.0d };
byte[] byteArr = { 1, 2, 3, 4, 5 };
short[] shortArr = { 1, 2, 3, 4, 5 };
Collections.reverse(Ints.asList(intArr));
Collections.reverse(Floats.asList(floatArr));
Collections.reverse(Doubles.asList(doubleArr));
Collections.reverse(Bytes.asList(byteArr));
Collections.reverse(Shorts.asList(shortArr));
System.out.println(Arrays.toString(intArr));
System.out.println(Arrays.toString(floatArr));
System.out.println(Arrays.toString(doubleArr));
System.out.println(Arrays.toString(byteArr));
System.out.println(Arrays.toString(shortArr));

Producción:

[5, 4, 3, 2, 1]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

Avatar de usuario de Jason Cohen
jason cohen

Su implementación (la que está en la pregunta) es más rápida que, por ejemplo, envolver con toList() y usando un método basado en un comparador. El encuadre automático y la ejecución a través de métodos de comparación u objetos de colecciones envueltos es mucho más lento que simplemente invertir.

Por supuesto que podrías escribir tu propio tipo. Esa podría no ser la respuesta que estás buscando, pero tenga en cuenta que si su comentario sobre “si la matriz ya está ordenada bastante bien” sucede con frecuencia, podría hacer bien en elegir un algoritmo de clasificación que maneje bien ese caso (por ejemplo, inserción) en lugar de usar Arrays.sort() (que es mergesort, o inserción si el número de elementos es pequeño).

  • No puede llamar a Arrays.toList en un doble[] y haz que haga lo que quieras; Arrays.toList necesita pasar un Doble[] y no una matriz de tipos primitivos.

    – Eli Cortesano

    18 de octubre de 2008 a las 17:19

  • Arrays.asList(nuevo doble[]{}); compila bien.

    – johnstok

    18 de octubre de 2008 a las 17:27

  • Ese es mi punto; Resumo este problema en mi respuesta recién editada.

    – Eli Cortesano

    18 de octubre de 2008 a las 17:34

Avatar de usuario de Krystian Cybulski
krystian cybulski

No puede usar comparadores para ordenar matrices primitivas.

Su mejor opción es implementar (o tomar prestada una implementación) de un algoritmo de clasificación que sea adecuado para su caso de uso para ordenar la matriz (en orden inverso en su caso).

  • No puede llamar a Arrays.toList en un doble[] y haz que haga lo que quieras; Arrays.toList necesita pasar un Doble[] y no una matriz de tipos primitivos.

    – Eli Cortesano

    18 de octubre de 2008 a las 17:19

  • Arrays.asList(nuevo doble[]{}); compila bien.

    – johnstok

    18 de octubre de 2008 a las 17:27

  • Ese es mi punto; Resumo este problema en mi respuesta recién editada.

    – Eli Cortesano

    18 de octubre de 2008 a las 17:34

avatar de usuario de madfree
loco

Creo que la solución más fácil sigue siendo:

  1. Obtener el orden natural de la matriz
  2. Encontrar el máximo dentro de esa matriz ordenada que luego es el último elemento
  3. Uso de un bucle for con operador decremento

Como dijeron otros antes: usar toList es un esfuerzo adicional, Arrays.sort(array,Collections.reverseOrder()) no funciona con primitivas y usar un marco adicional parece demasiado complicado cuando todo lo que necesita ya está integrado y, por lo tanto, probablemente sea más rápido como bien…

Código de muestra:

import java.util.Arrays;

public class SimpleDescending {

    public static void main(String[] args) {

        // unsorted array
        int[] integerList = {55, 44, 33, 88, 99};

        // Getting the natural (ascending) order of the array
        Arrays.sort(integerList);

        // Getting the last item of the now sorted array (which represents the maximum, in other words: highest number)
        int max = integerList.length-1;

        // reversing the order with a simple for-loop
        System.out.println("Array in descending order:");
        for(int i=max; i>=0; i--) {
            System.out.println(integerList[i]);
        }

        // You could make the code even shorter skipping the variable max and use
        // "int i=integerList.length-1" instead of int "i=max" in the parentheses of the for-loop
    }
}

¿Ha sido útil esta solución?