Análisis comparativo de consumo de recursos en vectores, listas y árboles

ESCUELA SUPERIOR POLITÉCNICA DE CHIMBORAZO

[pic 1]

SEMESTRE SEPTIEMBRE 2019 - FEBRERO 2020

TAREA No. 3

IDENTIFICACION

1.TEMA: Análisis comparativo de consumo de recursos en vectores, listas y árboles.

2. OBJETIVOS

2.1. OBJETIVO GENERAL

• Efectuar pruebas de tiempo y consumo de memoria en programas orientados a estructura de datos, específicamente vectores, listas y árboles, los cuales buscan un dato específico y ordenan todos sus datos, con el objeto de estar al tanto de que estructura de datos es la que cumple con su función en menos tiempo y consume menos recursos del computador y en consecuencia generar programas más eficientes.    

2.2. OBJETIVOS ESPECÍFICOS

• Escribir programas que almacenen automáticamente datos en un vector, lista o árbol, además de que busquen un dato en específico y se puedan ordenar.
• Medir el tiempo total de ejecución del programa de inicio a fin de manera automática.
• Registrar el consumo de memoria RAM del programa al momento de ejecutarse en función del tiempo.

3. MARCO TEÓRICO

Cuando se necesita trabajar con una variable, a esta se le puede asignar un valor, sin embargo, estas pueden llegar a ser limitadas, para ello es recomendable utilizar una estructura de datos, la cual puede ser un array que está entre los más simples o avanzadas tales como pilas, listas o árboles.

3.1. Vectores.

También conocidos como arreglos unidimensionales, un vector está formado por un conjunto de elementos de un mismo tipo de datos que se almacenan bajo un mismo nombre y se diferencian por la posición que tiene cada elemento dentro del arreglo de datos.

[pic 2]

3.2. Listas.

Las listas no son arreglos, aunque ambos representan secuencias de elementos de un tipo, los arreglos tienen longitud fija; las listas, no; es decir, las listas son flexibles y permiten cambio de implementación.

En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista suelen recibir también el nombre de Nodos de la lista. Existen diferentes tipos de listas, tales como las simplemente enlazadas, doblemente enlazadas, circulares.

[pic 3]

3.3. Árboles.

Un árbol se define como una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz. Además, se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro. Formalmente se define un árbol de tipo T como una estructura homogénea resultado de la concatenación de un elemento de tipo T con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol es el árbol vacío. Los árboles son estructuras recursivas, ya que cada subárbol es a su vez un árbol.

[pic 4]

4. APLICACIÓN PRÁCTICA

Para el desarrollo de las pruebas se utilizó una computadora de escritorio genérica con una tarjeta madre marca Intel, modelo dh67bl, un procesador Intel corei5 3330 y 12GB de memoria RAM ddr3 800mhz. Además, se codificó usando el lenguaje de programación c++ en el IDE Visual Studio 2019, el mismo que permitió realizar las pruebas correspondientes. Para tener unos resultados que emulen como se manejan los datos en el campo laboral, se puso a prueba con un manejo de 50000 datos de tipo entero.

4.1. Ordenar un vector.

4.1.1 Código.

[pic 5]

4.1.2. Ejecución en consola.

[pic 6]

4.1.3. Consumo de memoria durante la ejecución.

[pic 7]

4.1.4. Conclusión.

El tiempo total de ejecución tomó 2.003 segundos, llegando a tener un consumo máximo de 1,2 MB de memoria RAM.

4.2. Buscar un dato en un vector.

4.2.1. Código.

[pic 8]

 4.2.2. Ejecución en consola.

[pic 9]

4.2.3. Consumo de memoria durante la ejecución.

[pic 10]

4.2.4. Conclusión.

Con una duración de 0.004 segundos, se tuvo un consumo máximo de 1,1MB de memoria RAM.

4.3. Buscar un dato en una lista.

4.3.1. Código.

[pic 11]

[pic 12]

4.3.2. Ejecución en consola.

[pic 13]

4.3.3. Consumo de memoria durante la ejecución.

[pic 14]

4.3.4. Conclusión.

Con un consumo inicial de 524 KB de memoria RAM a los 563.52 MS, llegó a tener un consumo máximo y total de 3.9 MB, con tiempo total de ejecución de 12 segundos, lo cual supera a en tiempo y memoria a los vectores.

4.4. Ordenar Lista.  

4.4.1 Código.

[pic 15]

[pic 16]

[pic 17]

4.4.2. Ejecución en consola.

[pic 18]

4.4.3. Consumo de memoria durante la ejecución.

...