Tarea #8 [solución]

Mediciones de eficiencia para HerenciaOrdenada

      Use como base el programa HerenciaOrdenada.java que recibió en clase y modifíquelo para agregarle los siguientes métodos de ordenamiento: QuickSort() y HeapSort(). Además, modifique la implementación de sus algoritmos para contar la cantidad de comparaciones y de copias que realicen, con el fin de mostrar en un gráfico comparativo el rendimiento de cada algoritmo.

      La clase Algoritmo_Ordenador no tiene ningún campo, pero usted puede añadirle los campos m_comparaciones y m_copias para contar la cantidad de comparaciones y copias que hace su algoritmo cuando ordena un vector (agregue también los métodos adecuados para que ¡No se le meta al Rep!). Luego guarde en un archivo CSV el tamaño del vector junto con los contadores que calculó. Use esos valores para hacer varios gráficos que muestren el comportamiento del algoritmo conforme aumenta la cantidad de valores hay que ordenar.

      Si lo desea, puede usar una biblioteca Java como JChart2D para hacer uno o varios gráficos qe muestren la cantidad de operaciones de comparación y copia que utiliza cada método. Sin embargo, puede que le resulte más sencillo usar el componente calc de LibreOffice.

      Correr cada algoritmo con un único vector no permite obtener gráficos que reflejen la cantidad real de operaciones que puede necesitar. Por eso, usted creará 2 escenarios de ejecución diferentes, para obtener la cantidad de operaciones de cada algoritmo ordenador. Para el primer conjunto de valores de ejecución, ejecute cada uno de los algoritmos con todas las permutaciones posibles de los números {1,2,...,10}. Para obtener el segundo grupo de datos, construya 100 mil vectores de longitud {11,12,...,100} usando el algoritmo Random32 de Park& Miller. Finalmente, a partir de los valores recolectados, haga gráficos en que use el valor mínimo, promedio y máximo de todas las ejecuciones de cada algoritmo. Luego, analice los resultados que ha obtenido a la luz del rendimiento teórico de cada algoritmo [ O(n×log n) vs O(n²) ].

Park, Stephen K. && Miller, Keith W.:

“Random Number Generators Good Ones Are Hard To Find”, Computing Practices, Communications of the ACM, Volume 31 Number 10, pp 1192-1201, October 1988.
→  http://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf

Consulta:

Profe: ¿Puedo usar mi propia lista?

Respuesta:

Si. Pero tu programa duraría mucho más si hacés las pruebas con la lista en lugar de usar un vector.

Consulta:

Profe: ¿Hay que hacer un archivo “.csv.txt” por cada tipo de ordenamiento?. Es que cuando ejecute la primera parte del programa creo muchas líneas y cuando abrí el archivo con openOffice me dijo que la cantidad de filas habían sido superadas entonces omitía el resto.

Respuesta:

No hace falta que grabés un renglón para cada ejecución de cada uno de los algoritmos. Basta que guardés la cantidad mínima y máxima de ejecuciones para cada tamaño “n” del vector, en donde el valor de “n” varías desde 1 hasta 100. Para calcular la cantidad promedio, basta que acumulés la cantidad de operaciones m_comparaciones y m_copias y luego tomás el promedio. De esta manera evitás grabar trillones de renglones.

Consulta:

Profe: ¿En las instrucciones dice “creará 2 escenarios de ejecución diferentes”. ¿Se refiere a 2 programas diferentes o todo lo ponemos en el mismo “CARNET.java”?

Respuesta:

Me parece que meterlo todo en un solo archivo es un poco incómodo, pero si esto te da tranquilad, no hay problema en que lo hagás de esa forma.

Consulta:

Profe: a la hora de hacer la gráfica del primer entorno en la tarea de algoritmos, como se supone que vamos a hacer la gráfica si por ejemplo el quickSort() se dice en Google que tiene una complejidad de [ n×log(n) ] que donde “n” es el tamaño del vector, entonces me parece que puedo hacerlo usando los valores de “m_ciclo” y de “m_comparaciones” de manera que aumente conforme vayan pasando las permutaciones. Si es así, el gráfico sería lineal, no generaría ningún tipo de curva.

Respuesta:

No sería lineal, pues la cantidad de copias y comparaciones es diferente para cada permutación y para cada valor de “n”. Por cierto, no es “m_ciclo” sino más bien “m_copias”.

Consulta:

Profe: La forma de hacer el gráfico es usar un ciclo para aumentar tamaño “n” del vector y generar todas las permutaciones con cada tamaño. Pero esto contradice el enunciado de la tarea, que dice que nada más se generen las permutaciones. Aclaro, estamos en el entorno uno, de 1 a 10.

Respuesta:

El enunciado no dice que solo hay que generar permutaciones. Lo que dices es que, para tamaños en el rango [1..10] ustedes debe ejecutar cada algoritmo con todas las permutaciones de esos números. Sin embargo, como la cantidad de permutaciones crece tan rápidamente, para valores de “n” en el rango [11..100] ustedes deben generar muchos vectores diferentes, de manera que puedan obtener las cantidaddes m_comparaciones y m_copias para hacer los 2 gráficos. Los 2 escenarios de ejecución son muy similares, pero varía la forma en que ustedes deben generar los valores de los vectores (es saludable que usen la misma semilla para generar los valores de todos los vectores con Random32).

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2013
Derechos de autor reservados © 2013