Carlos Jouanne, 17642701

• Ejecución
• Código
• Tests
• Análisis

La base de python se ejecuta con python3 ./python/main.py tests/test.txt out.txt, mientras que el programa en c se compila con make y se ejecuta con ./kevin-21 tests/test.txt out.txt. Compila sin errores, y Valgrind indica que no hay errores ni pérdida de memoria.

• src/kevin-21
  • main.c
  • person.c
  • person.h
  • world.c
  • world.h
• Makefile

Este archivo no fue mayormente modificado. Se instanción el mundo en la linea 56:2, y se pobló de paises y regiones en la linea 64:4. En cada condicional se llama a la función para encontrar a la persona utilizando la ruta si es que corresponde, y después se ejecuta la función asociada al comando.

En estos se declaran y definen la struct person, y las siguinetes funciones:

• Person* init_tree(): instancia una persona que es la raiz de un arbol, sin padre, ni elementos en su lista ligada.
• void append_contact(Person* person, int id, int state): añade un hijo a person, con el id y state indicado.
• void person_destroy(Person* person): elimina a la persona, y a todos sus hijos, y además libera la memoria pedida al momento de crearlos.
• Person* search_contact(Person* person, int id): Busca el nodo hijo con el id dado.
• void recursive_inform(Person *person, int depth, FILE* output_file): retorna una representación del árbol que se guarda en el archivo output_file.
• positive_exam(Person* person): Este evento registra que una cierta Persona que era sospechosa en espera recibe un Test positivo, por lo que su estado cambia a contagiado. En caso de tener contactos estrechos, cambia el estado de cada uno a sospechoso en espera.
• correct(Person* person1, Person* person2): intercambia los nodos hijos entre person1 y person2.
• positive_exam(Person* person): Este evento registra que una cierta Persona que era sospechosa en espera recibe un Test positivo, por lo que su estado cambia a contagiado. En caso de tener contactos estrechos, cambia el estado de cada uno a sospechoso en espera.
• int count_state(Person* person, int state): cuenta la cantidad de personas que se encuentran en un estado determinado.
• void recursive_statistics(Person* person, FILE* output_file): guarda un reporte mostrando cuantas personas se encuentran en un arbol.

En estos se declaran y definen la struct world, y las siguinetes funciones:

• World* god_create_world(int n_countries): genera una instancia del mundo con n_countries paises.
• void create_region(World *world, int country_index, int n_regions): crea n_regions en un país determinado, en un mundo establecido, y en cada región inicializa el arbol con un caso base.
• void add_contact(World *world, int country, int region, Person *person, int close_contacts): añade close_contacts hijos a person.
• void thanos(World *world): destruye el mundo, y libera su memoria.

A continuación, se muestra la complejidad teórica de cada acción considerando el peor caso:

• La complejidad de búsqueda de un paciente 0 es O(1), muentras que en el peor de los casos es de O(n) donde n es el número de nodos del árbol.

  • ADD_CONTACTS: encontrar la persona a la cual se le añade un contacto tiene complejidad hasta O(n). Añadir un elemento al final de una lista ligada tiene complejidad O(1), al iterar sobre estacción, tenemos una complejidad de O(n), por lo tanto, la complejidad total es O(n).
  • RECOVERD: en el peor de los casos es O(n), ya que la busqueda es O(n) y el cambio de estado es O(1).
  • POSITIVE: en el pero de los casos, la búsqueda es O(n), el cambio de estado es O(1), y el cambio de estado de los hijos es tambien hasta O(n), por lo tanto tiene cmplejidad hasta O(n).
  • NEGATIVE: en el pero de los casos, la búsqueda es O(n), y borrar este nodo y sus hijos correspondientes tiene una complejidad de O(n), por lo tanto tiene cmplejidad hasta O(n).
  • CORRECT: cada búsqueda tiene una complejidad de O(n), el cambio de padre de cada nodo tiene complejidad O(1), por lo que la operación total, tiene complejidad hasta O(n).

• INFORM: tiene siempre una complejidad de O(n) pues siempre debe recorrer el arbol entero.

• STATISTICS: tiene siempre una complejidad de O(n) pues siempre debe recorrer el arbol entero.

• Si se cambiase la estructura del arbol de personas, según se propone en el enunciado, pasando de utilizar una lista ligada a utilizar un arreglo, donde además del id, se conoce el índice en el cual se encuentra un nodo, se simplificaría la búsqueda ya que la búsqueda en un arreglo ordenado es O(1) (O(log n) si no supieramos el índice), mientras que en una lista ligada es O(n). Almismo tiempo, las operaciones de Insertar y Eliminar elementos en la mitad se vuelven mas "costosas" ya que hay que volver a indexar todos los elementos posteriores a la posición en la que se inserta/elimina el elemento, dejando una complejidad de O(n), mientras que en una lista ligada, estas operaciones tienen una complejidad de O(1).

Al testear el programa con los tests de los niveles Easy, Medium y Hard se obtuvieron resultados correctos de manera eficiente. Además, Valgrind indicó que el programa no tiene errores de memoria, y que no hay memory leaks. El programa fue desarrollado y ejecutado con un procesador Intel® Core i5 2da generación, 4GB de RAM, GPU NVIDIA® GEFORCE 2GB, utilizando el sistema operativo Kali Linux.

Al ejecutar los tests obtenidos de la carpeta ./Compare, utilizando el comando time de bash, se obtiene para cada test los siguientes resultados:

Como se puede ver en la tabla, el tiepo de ejecución del programa user esen promedio un 79.04% menor en C, en relación a ejecutar el mismo test en Python3. Además, utiliza un 21.2% menos de CPU, y el valor total entregado por time es también un 70.8% menor en C. Con esto podemos decir, que evidentemente C es más rápido que Python3, ya que ejecuta la misma tarea en aproximadamente 1/5 del tiempo. A pesar de esto, en la columna system, se puede ver los tiempos para C son 59.8% mayores que para Python3. Esto quiere decir la cantidad de tiempo que la CPU (s) pasó realizando llamadas del sistema para el kernel en nombre del programa es mayor para C que para Python3 (Al menos en la configuración en la cual los tests fueron ejecutados).