Universidad de Costa Rica
Escuela de Ciencias de la Computación e Informática
CI-1201 Programación II - I-2013
Profesor Jeisson Hidalgo-Céspedes
Grupo 03. Entrega límite: 24-abr-2013 11:55 p.m.
Modifique su comando estad (o en inglés stats) para que incluya entre los resultados estadísticos el cálculo de la mediana y la moda cuando se soliciten explícitamente con la opción -a. Además de otras mejoras que se explican en lo siguiente y se resumen al imprimir la ayuda del programa con la opción --help:
$ stats --help Usage: stats [-afhiV] [FILES] Get statistics such as average and standard deviation from numeric data stored in FILES. Options: -a print all statistics including median and mode -f force to get statistics from no valid files -h [N] print a histogram with N breaks -i print statistics for each individual file -V print version of this program Warning: -a and -h options may require high memory consumption $
La mediana es el valor que se encuentra en la posición central de un conjunto de datos ordenados. En el lenguaje de programación C, si los datos se almacenan en un arreglo ordenado arr de tamaño n, el valor de la mediana será el elemento arr[n/2] si n es impar. Si n es par, la mediana se calcula como el promedio de los dos valores centrales, es decir (arr[n/2 - 1] + arr[n/2])/2.0.
Para poder calcular la mediana, su programa necesita tener los datos ordenados y no existe ninguna garantía de que el usuario los provea en orden. Por esto, su solución deberá encargarse de ordenar los datos. Hay varias alternativas para lograr esto. Históricamente los programadores cargan los datos del origen a alguna forma de estructura de datos en la memoria principal, por ejemplo, un arreglo o un árbol que son eficientemente ordenables. Luego de ordenar los datos en la memoria, se calcula el dato resultado, se imprime y se descarta la estructura en memoria.
El cargado de una copia de los datos a la memoria principal tiene como ventajas que es eficiente el ordenamiento, ya que la RAM trabaja a una velocidad mucho mayor que la memoria secundaria. Sin embargo, sufre del inconveniente que la cantidad de memoria principal puede ser mucho menor que el tamaño de los datos. Por ejemplo, si el usuario quiere ordenar un archivo de 1TB en una máquina con 8GB de RAM. Soluciones se pueden implementar en estos escenarios, como crear un archivo de acceso aleatorio temporal donde se realiza el ordenamiento, o incluso, utilizar computación de alto rendimiento (HPC, High Performance Computing) que permite dividir el problema en partes que son resueltas entre varios equipos, lo que reduce el tiempo de ejecución notablemente.
Para efectos de esta tarea, basta con que los datos numéricos se carguen a un arreglo en la memoria principal, se ordene y con él se calcule la mediana. Un reto más debe considerarse. El programa obtiene los datos numéricos en secuencia, uno a uno de la fuente de datos; y no se sabe de antemano cuántos de ellos serán. Dado que la fuente de datos puede ser la entrada estándar, no hay posibilidad de recorrer dos veces los datos. Se sugiere entonces que el programador haga crecer el arreglo en memoria dinámica conforme más datos se vayan cargando. Debe emplearse la función realloc() para este fin. En el código que se encuentra más adelante en este enunciado, ya esta funcionalidad fue implementada, incluso el cálculo de la mediana.
El valor modal es aquel que más se repite en el conjunto de datos. Por ejemplo, si los datos son {2, 3, 3, 4, 6}, la moda es 3 y se repite 2 veces. Si se tienen los datos ordenados en un arreglo, es fácil contar cuántas veces se repite un valor mirando si es el mismo al valor anterior en el arreglo. Esto implica que basta un contador (una variable entera) para calcular la moda, y no otro arreglo en memoria para almacenar frecuencias.
Puede ocurrir que el conjunto de datos tenga dos o más valores modales. Esto es, cuando hay dos o más valores que se repiten con la mayor frecuencia y hay al menos otro valor que se repite con menos frecuencia. En caso de haber varios valores modales, su programa debe imprimir cada uno de ellos. Sugerencia: puede hacer dos recorridos por el conjunto de datos. Si todos los valores en el conjunto de datos se repiten con la misma frecuencia, no existe una moda y su programa debe informarlo. Ejemplos de datos y sus modas:
Los comandos de Unix pueden recibir dos tipos de opciones en los parámetros de invocación. Las opciones largas son palabras que se anteceden de dos guiones, como --help, --version y --hist-breaks=N. Las opciones cortas constan de una única letra y se anteceden por un guión (y no dos). Las opciones largas son las opciones primarias de los comandos y las opciones cortas son "atajos" a algunas formas largas y son provistos por conveniencia al usuario. Las opciones largas son más fáciles de memorizar o leer que las opciones cortas. Por convención de Unix, las opciones cortas se pueden unir tras un mismo guión. Por ejemplo, las siguientes invocaciones de su programa deberían producir exactamente el mismo resultado
$ ./stats -a -f gr08.txt -i $ ./stats -af gr08.txt -i $ ./stats -afi gr08.txt $ ./stats -fia gr08.txt $ ./stats gr08.txt -ifa $ ./stats gr08.txt -a -fi $ ./stats gr08.txt -aa -fia -i
Si una opción (larga o corta) aparece dos o más veces en los parámetros de invocación, se toma como sólo fuese escrita una única vez. Algunas opciones largas o cortas pueden tomar valores adicionales. Por ejemplo, usted debe programar la opción -h capaz de aceptar un parámetro numérico optativo, el cual indica la cantidad de clases (breaks) que el usuario quiere en el histograma, como se solicita en el siguiente punto.
El manejo de opciones cortas unidas, ya fue implementado en el código de ejemplo de clase provisto más adelante en este enunciado.
En esta versión su comando debe ser capaz de dibujar un histograma aún cuando los datos provengan de la entrada estándar. Cuando la opción -h es provista, su programa debe copiar los números de la fuente de datos al arreglo en memoria de la misma forma que cuando se solicita la mediana o la moda (opción -a).
También en esta versión su programa debe ser inteligente a la hora de seleccionar la cantidad de clases (breaks o bins) en que se divide el histograma. Usted debe proponer una ecuación para construir un histograma incluso con conjuntos de datos "raros". Puede leer una lista de propuestas en entrada de la Wikipedia sobre histogramas. Por ejemplo, si el usuario provee n=1,000,000 de números todos iguales, la opción raíz cuadrada \(k = \sqrt{n}\) crearía un histograma con 1000 divisiones, pero sólo 1 de ellas tendría todos los valores. Sugerencia: para su solución plantee una fórmula que pueda escoger en tiempo ejecución la mejor entre dos o más propuestas. Su objetivo es que el histograma sea informativo para el usuario.
Puede ocurrir que el usuario no encuentre
Es habitual que los programas impriman información de versión, fechas, autores, licencias, sitio web del proyecto, y otros detalles cuando se les invoca con la opción --version o abreviada como -V. Implemente estos dos parámetros para dar información sobre el programa a sus potenciales usuarios, por ejemplo:
$ ./stats --version stats v2.0 [2013-04-12] Jeisson Hidalgo-Cespedes <jeissonh@gmail.com> stats comes with absolutely no warranty. This is free software, and you are welcome to redistribute it under Creative Commons Attribution 3.0 Unported (CC BY 3.0) license: http://creativecommons.org/licenses/by/3.0/ $
Su solución deberá implementarse bajo el paradigma de programación procedimental. El siguiente código fuente realizado en clase muestra cómo calcular la mediana. Para compilarlo con GCC puede emitir el comando cc -Wall -std=c99 -o estad estad.c.
]]>
Para presentar su solución, comprima únicamente los archivos fuente (.c, .cpp, .h) que haya creado y suba el comprimido a la Plataforma Educativa en la asignación con nombre Tarea03.