Taller 4: Rendimiento y comparación práctica de algunos algoritmos

Con el fin de poder comparar el tiempo de ejecución de diversos algoritmos de ordenamiento sujeto al tamaño de la entrada, la Asociación Internacional de Algoritmos Altamente Ineficientes (AIAAI), ha propuesto establecer una carrera internacional de algoritmos. La idea en general, consiste en la inscripción de diversos Equipos; Cada equipo debe contar con la implementación de un algoritmo de ordenamiento, este algoritmo sería sujeto a prueba en diversas rondas de ordenamiento, durante las cuales, se provee una lista de elementos Comparables de una longitud específica.

El equipo ganador se establece de acuerdo a la posición promedio durante cada ronda, esta posición se encuentra asignada de acuerdo al tiempo de ejecución del algoritmo en la ronda, los algoritmos que tengan el menor tiempo de ejecución obtendrán posiciones superiores.

1. Ejecución del programa y configuración del entorno.

Ingresar a la carpeta taller_4 que se encuentra en el repositorio talleres-templates. En caso de no contar con una copia del repositorio, puede realizar una copia directamente a su máquina local, usando el comando git clone https://[email protected]/talleres/talleres-templates.git.
Inicie DrJava y seleccione en el menú principal Project->Open, luego seleccione el archivo project.xml que se encuentra en la carpeta taller_4. Esto abrirá el proyecto en DrJava.
Compile y ejecute el proyecto.
Figura 1: Menú principal de la aplicación.

Tras ejecutar la aplicación, el terminal debería tener como contenido, un menú de selección similar al presentado en la Figura 1. Por favor, proceda a interactuar con el menú de forma completa, con el fin de detallar y conocer las opciones ofrecidas en el Torneo. Es posible ejecutar una instancia del torneo con los equipos del sistema bajo la opción número 1, seguida de la opción 2.

2. Definición y descripción de un equipo

Por definición, un equipo se encuentra directamente relacionado con la implementación específica de un algoritmo de Ordenamiento, no obstante, todo equipo que participa en el torneo debe contar con parámetros comunes, tal como un nombre, un tiempo de ejecución de la rutina de ordenamiento y un porcentaje de efectividad dispuesto tras cada ejecución de la rutina de ordenamiento. Para este fin, se define una clase abstracta AlgorithmTeam, la cual, además de declarar los atributos previamente enumerados, define el método abstracto public abstract Comparable[] sort(Comparable[] list, TipoOrdenamiento orden);, método que debe ser implementado por la clase (Equipo) que extienda directamente la clase AlgorithmTeam. Es importante notar que el arreglo a ordenar, contiene instancias de la clase Comparable, es decir, cada elemento debe disponer de un método compareTo, el cuál permitiría comparar dos elementos.

Adicionalmente, el parámetro orden puede adquirir dos valores enumerados (Como es posible apreciar en AlgorithmTournament.java), los cuales establecen el criterio de orden de los elementos. Este valor puede ser TipoOrdenamiento.ASCENDENTE o TipoOrdenamiento.DESCENDENTE, si se desea ordenar de forma Ascendente o Descendente, respectivamente.

En la carpeta src/algorithm/race/teams se encuentran alojados todos los archivos de descripción de los equipos que participan en el torneo. A continuación, es posible observar la implementación de algunos algoritmos de complejidad \(\mathcal{O}(n^2)\) reconocidos. Finalmente, es posible apreciar la descripción del equipo TimSort, el cual representa la implementación de referencia de Timsort por parte de la librearía estándar de Java.

3. Implementación de Quicksort y Merge Sort

En la carpeta que contiene las clases que describen los equipos inscritos, es posible observar dos archivos: QuickSortTeam y MergeSortTeam. A continuación, debe abrir estos archivos en el editor y proceder a seguir las instrucciones dispuestas para la implementación de Quicksort y Merge Sort respectivamente. Modifique el nombre de cada equipo si desea e implemente alguna de las opciones sugeridas. Una vez haya finalizado, proceda a ejecutar una instancia del torneo. (Opción 1 en el menú principal, seguida de la opción 2.)

4. Metodología y funcionamiento del torneo.

El torneo comprende una base de datos que contiene 4.000.000 números enteros que se encuentran en desorden, compilados en un conjunto de 80 archivos que contienen 50.000 elementos cada uno, con el fin de establecer una medida de referencia que permita describir la eficiencia temporal del archivo, se procede a definir un conjunto de Rondas, durante cada ronda, se escoge un archivo de forma aleatoria, y de acuerdo al número máximo \(j\) de elementos a ordenar por ronda, se escoge de forma aleatoria \(j\) elementos del archivo. Posteriormente se evalúa y se captura el tiempo de ejecución del algoritmo de ordenamiento dispuesto por cada equipo. A continuación, se disponen los resultados en pantalla, ordenados de acuerdo al tiempo total de ejecución, finalmente, se procede a repetir el proceso hasta que el número de rondas sea equivalente al límite dispuesto por el usuario.

Retos

Ordenamiento Externo

Se desea establecer una división «avanzada» del torneo de algoritmos, para este fin, es necesario que cada equipo ordene la totalidad de los archivos dispuestos por la base de datos, y obteniendo como resultado, un único archivo. Debido a las limitaciones ofrecidas por la memoria, no es posible cargar 4.000.000 de elementos en memoria principal, y por lo tanto, es necesario realizar un proceso de Ordenamiento Externo en la medida que se desea obtener un archivo único que contenga la totalidad de los elementos. Como es posible apreciar, la opción número 3 del menú Iniciar pruebas y competencias se encuentra sin implementar, comprenda y modifique las clases AlgorithmCLI.java, AlgorithmTournament.java y AlgorithmTeam.java con el fin que cada equipo pueda implementar una rutina de ordenamiento externo.

No es necesario implementar todas las rutinas de ordenamiento externo para todos los equipos del sistema, sin embargo, es fundamental implementar una rutina de merge sort, que realice el siguiente procedimiento:

Por cada archivo, cargar su contenido en memoria principal y realizar el ordenamiento de los elementos cargados usando Quicksort o el algoritmo de su preferencia (Excepto la implementación de Timsort dispuesta en Arrays.sort).
Guardar cada archivo con los elementos ordenados.
A continuación, establecer flujos de lectura (BufferedReader) a cada archivo, además de un buffer dispuesto para la escritura del archivo final (BufferedWriter). Implementar un procedimiento similar al presentado en MergeSortTeam.java, merge, el cual debe recibir como entrada, un arreglo que contiene flujos de lectura a cada uno de los archivos. Se debe realizar el proceso de mezcla de cada flujo al comparar la primera entrada de cada flujo, con la primera entrada de los flujos restantes.

Es necesario notar la importancia de guardar las líneas cargadas desde los flujos, en la medida que no es posible retroceder y leer una línea nuevamente una vez ha sido solicitada. Con el fin de resolver este inconveniente, se recomienda establecer un arreglo que contenga los elementos que se encuentran en la misma línea de cada uno de los archivos, i.e., el primer paso consiste en leer una línea de cada flujo y agregarla en el arreglo en el mismo índice del flujo en el arreglo de flujos. A continuación, se procede a ordenar el arreglo de elementos usando el algoritmo de preferencia. Posteriormente, es necesario escribir los elementos del arreglo ordenado en el flujo de escritura al archivo. Finalmente, es necesario repetir este proceso hasta que todos los flujos hayan sido explorados por completo.

Leer Archivos:


   try(BufferedReader br = new BufferedReader(new FileReader("Ubicación del archivo")))
   {
          String inputLine;
          while((inputLine = br.readLine()) != null)
          {
              //Gestión de la entrada
          }
   }
   catch(Exception e)
   {
   }

Escribir Archivos:

    try (Writer writer = new BufferedWriter(new OutputStreamWriter(
         new FileOutputStream("filename.txt"), "utf-8")))
    {
       writer.write("something");
    }

Algoritmos Híbridos

Diseñar un algoritmo híbrido (Un algoritmo que usa dos o más rutinas de ordenamiento) y agregarlo a la lista de equipos inscritos. Finalmente, iniciar una sesión de competencia y comparar.

Preguntas

Compare el desempeño de ejecución de Merge Sort y Quicksort con aquel de Bubble sort sobre un arreglo de números enteros que se encuentra en orden, asímismo, realizar una prueba similar, en esta ocasión, con un arreglo que contiene un único número en cada posición. ¿Cuál algoritmo de ordenamiento tiene un mejor rendimiento en ambas pruebas? En caso de que el algoritmo que presenta mejor rendimiento, cuente con una complejidad temporal de \(\mathcal{O}(n^2)\), ¿Por qué requiere de un menor tiempo para resolver el problema de ordenamiento? Finalmente, ¿Qué cambios deberían efectuarse en las rutinas de ordenamiento que presentan una complejidad de \(\mathcal{n \log{n}}\) con el fin de obtener un rendimiento equivalente a aquel del algoritmo \(\mathcal{O}(n^2)\)?
Quicksort fue propuesto por Tony Hoare en el año 1959, bajo la premisa de ser un algoritmo sencillo, eficiente y conveniente para realizar el ordenamiento de un conjunto de elementos. Si bien, este algoritmo resulta ser popular entre la mayoría de programadores en la industria, este puede presentar fallas significativas de acuerdo al procedimiento de elección de pivote implementado bajo la rutina de partición. Explicar cómo el proceidimiento de elección de pivote puede alterar y modificar el tiempo de ejecución de Quicksort.

Entrega para bonificación

Fecha límite de entrega: Ver

Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
Conteste las preguntas en el archivo README.txt.
Realice pruebas unitarias para la implementación de sus equipos de ordenamiento, estas pruebas deben verificar que los algoritmos:
- Realicen de forma correcta el proceso de ordenamiento.
- Adicionalmente, verificar que los elementos presentes en la lista ordenada, corresponden a los mismos elementos existentes en la lista que no presenta orden.
Cargue el taller a su repositorio en Bitbucket. ** No olvide crear el archivo calificacion.txt

ISIS1206 - Estructuras de Datos