Java | Manejo de TLE mientras se usa la función Arrays.sort()

En programación, es bastante común que un programador de Java se enfrente a un límite de tiempo excedido o TLE si no usa la función Arrays.sort() con cuidado.

A continuación, el código Java muestra el tiempo de ejecución tomado por la función trivial Arrays.sort().

// Java program to show
// time taken by trivial Arrays.sort function
  
import java.util.Arrays;
import java.util.Calendar;
  
public class ArraySort {
  
    // function to fill array with values
    void fill(int a[], int n)
    {
        for (int i = 0; i < n; i++)
            a[i] = i + 1;
    }
  
    // function to check the performance
    // of trivial Arrays.sort() function
    void performanceCheckOfSorting()
    {
        // creating a class object
        ArraySort obj = new ArraySort();
  
        // variables to store start
        // and end of operation
        long startTime = 0l;
        long endTime = 0l;
        int array1[] = new int[100000];
        int n = array1.length;
  
        // calling function to fill array with
        // values
        obj.fill(array1, n);
  
        startTime = Calendar.getInstance()
                        .getTimeInMillis();
        // sorting the obtained array
        Arrays.sort(array1);
        endTime = Calendar.getInstance()
                      .getTimeInMillis();
  
        // printing the total time taken
        // by Arrays.sort in worst case
        System.out.println("Time Taken By The"
                           + " Use of Trivial "
                           + "Arrays.sort() function : "
                           + (endTime - startTime)
                           + "ms");
    }
  
    // Driver function
    public static void main(String args[])
    {
        // creating object of class
        ArraySort obj = new ArraySort();
  
        // calling function to compare performance
        obj.performanceCheckOfSorting();
    }
}

Time Taken By The Use of Trivial Arrays.sort() function : 31ms

Como podemos ver, el tiempo que se tarda en clasificar 1 millón de números es bastante alto; a primera vista, puede parecer que no es tan alto, pero durante el concurso de programación, cada milisegundo produce una diferencia.

Motivo de TLE:
la función Arrays.sort() usa Quick Sort en su implementación. La complejidad del caso más desfavorable de Quick Sort es O( ), donde N es el tamaño de la array. La complejidad en el peor de los casos se presenta en el caso en que la array de entrada ya está ordenada y la mayoría de las veces a los solucionadores de problemas les gusta hacer tales casos de prueba.

Cómo manejar el peor de los casos:

1. Uso de una array de objetos (clases envolventes de primitivas) en lugar de valores:
   en lugar de utilizar una array de valores, la clasificación de la array de objetos lleva menos tiempo. Esto se debe a que la función Arrays.sort() usa Merge Sort para ordenar la array de objetos, que tiene una complejidad en el peor de los casos de O( ) en comparación con O() de clasificación rápida .

   A continuación, el código de Java muestra la comparación del tiempo de ejecución entre el uso de la función Arrays.sort() en la array de valores con la de la array de objetos.

   // Java program to handle worst case // of Arrays.sort method    import java.util.Arrays; import java.util.Calendar;    public class ArraySort {        // function to fill array with values     void fill(int a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = i + 1;     }        // function to fill array with     // objects     void fill2(Integer a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = new Integer(i + 1);     }        // function to compare performance     // of original and optimized method 1     void performanceCheckOfSorting()     {         // creating a class object         ArraySort obj = new ArraySort();            // variables to store start         // and end of operation         long startTime = 0l;         long endTime = 0l;            // Method 1         // Using Arrays.sort()         int array1[] = new int[100000];         int n = array1.length;            // calling function to fill array with         // values         obj.fill(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         // sorting the obtained array         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in worst case         System.out.println("Time Taken By Arrays.sort"                            + " Method On Values : "                            + (endTime - startTime)                            + "ms");            // Method 2         // Taking Array Of Type Object         Integer array2[] = new Integer[n];            // calling function to fill array with         // objects of class Integer         obj.fill2(array2, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         Arrays.sort(array2);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in case of object array         System.out.println("Time Taken By Arrays.sort"                            + " Method On Objects: "                            + (endTime - startTime)                            + "ms");     }        // Driver function     public static void main(String args[])     {         // creating object of class         ArraySort obj = new ArraySort();            // calling function to compare performance         obj.performanceCheckOfSorting();     } }

   Producción:

   Time Taken By Arrays.sort Method On Values : 31ms
   Time Taken By Arrays.sort Method On Objects : 19ms
   

   Aquí podemos ver que el tiempo que tarda la función Arrays.sort() en ordenar la array del objeto es menor que las arrays de valores.

2. Barajar antes de ordenar:
   este método es el más utilizado por los programadores de Java de la competencia. La idea es barajar toda la array de entrada
   antes de ordenar, de esta manera se maneja el peor caso de ordenación rápida que surge en el caso de la array ya ordenada.
   Otro beneficio de este método es que mantiene la naturaleza primitiva de la array.

   En el siguiente programa de Java, he mostrado una comparación entre el uso trivial de la función Arrays.sort() y eso después de barajar toda la array. También proporcioné la implementación del método de reproducción aleatoria definido por el usuario que tiene la complejidad de O( ) de reproducción aleatoria donde N es el tamaño de la array.

   // Java program to handle worst-case // of Arrays.sort method    import java.util.Arrays; import java.util.Calendar;    public class ArraySort {        // function to fill array with values     void fill(int a[], int n)     {         for (int i = 0; i < n; i++)             a[i] = i + 1;     }        // Java implementation of shuffle     // function     void shuffle(int a[], int n)     {         for (int i = 0; i < n; i++) {                // getting the random index             int t = (int)Math.random() * a.length;                // and swapping values a random index             // with the current index             int x = a[t];             a[t] = a[i];             a[i] = x;         }     }        // function to compare performance     // of original and optimized method 2     void performanceCheckOfSorting()     {         // creating a class object         ArraySort obj = new ArraySort();            // variables to store start         // and end of operation         long startTime = 0l;         long endTime = 0l;            // Using Arrays.sort()         // without shuffling before sorting         int array1[] = new int[100000];         int n = array1.length;            // calling function to fill array with         // values         obj.fill(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         // sorting the obtained array         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort in worst case         System.out.println("Time Taken By Arrays.sort"                            + " Method On Trivial Use: "                            + (endTime - startTime)                            + "ms");            // Shuffling before Sorting         // calling function to fill array with         // values         obj.fill(array1, n);            // calling function to shuffle         // obtained array         obj.shuffle(array1, n);            startTime = Calendar.getInstance()                         .getTimeInMillis();         Arrays.sort(array1);         endTime = Calendar.getInstance()                       .getTimeInMillis();            // printing the total time taken         // by Arrays.sort() function in case shuffling         // of shuffling before sorting         System.out.println("Time Taken By Arrays.sort"                            + " Method After Shuffling "                            + "Before Sorting : "                            + (endTime - startTime)                            + "ms");     }        // Driver function     public static void main(String args[])     {         // creating object of class         ArraySort obj = new ArraySort();            // calling function to compare performance         obj.performanceCheckOfSorting();     } }

   Producción:

   Time Taken By Arrays.sort() Function On Trivial Use : 31ms
   Time Taken By Arrays.sort() Function After Shuffling Before Sorting : 10ms
   

   Aquí, en este caso, vemos que el uso de la función Arrays.sort() en una array aleatoria lleva menos tiempo en comparación con la array no aleatoria. Además, el tiempo que se tarda en clasificar la array de objetos es mayor que el tiempo que se tarda en clasificar las arrays después de mezclarlos.