Trabajo Final de Lenguajes de Scripting

Alumno: Emiliano Martínez Luque

Legajo: 43556

Docente: Ares

Cursada: Viernes a la Noche, Segundo Cuatrimestre 2011

Descripción General

Se trata de una serie de scripts en Python para analizar el comportamiento de un algoritmo bajo diferentes inputs. Se generan una serie de reportes en los que se varian algunos de los parametros del input y se analizan los resultados.

Motivación

Por una cuestión de ejercitación personal, estuve realizando el análisis de complejidad de un algoritmo genérico básico. Al comenzar este análisis resulto relativamente fácil tanto determinar la corrección del algoritmo, como buscar estructuras de datos para mejorarlo, así como determinar matematicamente el mejor y el peor caso. Sin embargo la definición de una función matematica para determinar el comportamiento del caso promedio no resulto tan inmediato. Se busca con este trabajo proveer datos exploratorios para ayudar en este proceso.

Descripción del Algoritmo a Analizar

Es un algoritmo sencillo en el que dado una lista de números ordenados, por ejemplo: [1,3,3,6,4,8,6,4,10], retorna la misma lista manteniendo el orden pero sacando los duplicados, por ejemplo: [1,3,6,4,8,10]. Básicamente se crea otra lista pasados y se va iterando por la lista original y comparando contra pasados. En cada iteración si el valor preexiste en pasados se borra el valor de la lista original, si no preexiste, se lo agrega a pasados y se continua el proceso. Definitivamente el algoritmo puede ser mejorado usando mejores estructuras de datos (por ejemplo: binary search trees). Pero, dado que ese análisis ya lo he hecho, el objetivo de este Trabajo es otro, a saber analizar el comportamiento de la función sobre una distribución de probabilidades aleatorias.

Una implementación en C del algoritmo para testear sobre linea de comandos, puede ser accedida en la carpeta algoritmo bajo el nombre de algoritmo.c.

Una version modificada de esta implementación llamada algo.c es la que usa el script para generar las muestras.

.

Descripción Detallada del Trabajo

Las muestras se generan corriendo un subproceso algo (originalmente codificado en C) desde los scripts de Python, con una lista de enteros separados por coma como argumento de la llamada. Esta lista randomizada es generada dentro del script de Python. El subproceso algo retorna por stdout un entero que es el resultado del calculo del costo de la porción del algoritmo que nos interesa analizar. El script de Python lee este valor. Luego de generar una cantidad determinada de experimentos con diferentes parametros de input y diferentes tamaños de muestras se generan reportes en HTML, que incluyen los resultados de las variables en cada experimento así como gráficos de la distribución. Así mismo se guardan las diferentes muestras en el sistema de archivos.

.

Se usan conceptos generales vistos en las materias Estadisca y Modelos y Simulación.

.

Por que se Utilizo Python?

De los lenguajes vistos durante la cursada, aquellos que podrían haber sido usados para un trabajo de este tipo son: Ruby, Perl y Python, dado que AWK y Bash no tienen la capacidad expresiva, ni la intención de cubrir este tipo de casos de uso y Javascript es mayoritariamente ( a pesar de los avances actuales de Node.JS ) un lenguaje para desarrollo en clientes web. Se prefirió Python por el soporte y sus capacidades para procesamiento matematico, así como por su expresividad.

.

Conceptos de programación en Python usados en el trabajo

Se intento tambíen hacer una interface gráfica moderna y bien presentada.

Advertencia

Por el costo computacional de generar las simulaciones, en la presentación del final los reportes generados en vivo serán pequeños. Se presenta así mismo un reporte completo y amplio (con mayores tamaños de muestra) pregenerado sin limitaciones de tiempo y en una maquina con mayor capacidad de procesamiento y memoria.

.