Malas estructuras de datos

Lester Pastrana [lester@uh.cu]

Introducción:

El objetivo de este material no es enseñar cómo programar una estructura de dato ya que existen muchas bibliotecas que nos brindan interfaces de estas, probablemente mucho más eficientes y con menos errores de las que lograríamos nosotros. Lo que persigue este material es ayudar a entenderlas y decidir cuales usar en cada momento.

Problema:

Uno de los estados más importantes en la solución de un problema consiste en determinar dónde se van a guardar los datos. Es común que en los inicios se tomen decisiones incorrectas. Un problema clásico y sencillo orientado por los profesores, es realizar un programa para la gestión de libros en una biblioteca. Por lo general, este se restringe a que durante la ejecución del programa los datos se deben almacenar en un Vector o un LinkedList.

Las principales acciones a realizar en el software consisten en agregar un nuevo libro, eliminarlo y buscarlo para prestarlo. Otros requerimientos son implementar la estructura de dato y desarrollar el software en C++.

La experiencia ha demostrado que la gran mayoría decide utilizar LinkedList para la resolución de su problema, pero… ¿Por qué no un simple Vector? Muchos piensan que un LinkedList utiliza menos memoria, además la inserción y la eliminación parecen ser más eficientes. En esto existe un error.

Resolución:

Definamos algunas notaciones para facilitar la explicación.
O (1): Indica que la operación se realiza en un tiempo constante. Es decir el número de datos no influye en el tiempo que consume la operación.
O (n): Indica que la operación se realiza en un tiempo lineal. Es decir el número de datos influye linealmente en el tiempo que consume la operación.
O (log n): Indica que la operación se realiza en un tiempo logarítmico. Es decir el tiempo de la operación es aproximadamente igual al logaritmo del número de datos.

Ordenes del Vector y LinkedList
• Inserción: O (1)
• Eliminación: O (n)
• Búsqueda: O (n)
• Memoria: O (n)

Como se aprecia ambas estructuras se comportan igual según indican los órdenes. Por desgracia esto nos da una descripción bastante pobre del real comportamiento de cada estructura. Veamos cada uno de los puntos en detalles.

Definición:

Vector: Consiste en un array dinámico que crece (por lo general se duplica su tamaño) cuando el número de elementos supera su capacidad.

LinkedList: Lista de nodos unidas por referencias (apuntadores).

La memoria

Sin perder generalidad supongamos que el tamaño de cada elemento almacenado es de 4 bytes, que es el tamaño de un puntero, si el elemento tiene un tamaño inferior se deja al lector que demuestre la superioridad inmediata del Vector sobre el LinkedList en este aspecto.

Denotemos por M (v) como el tamaño de memoria del Vector y M (l) como el tamaño de memoria del LinkedList.

M (v) = 4 * length, donde length indica el número máximo de elementos que se pueden almacenar en el Vector y M (l) = 8 * count, cada casilla esta compuesta por el elemento y una referencia al próximo y count es el número de casillas existentes.

Cuando el Vector se llena entonces length = count y en el instante en que este crece length = 2 * count, luego sustituyendo se tiene que M (v) = 8 * count en este momento el Vector estaría a la mitad de su capacidad y la memoria ocupada por este es idéntica a la utilizada por el LinkedList, a medida que se llena el Vector –a diferencia del LinkedList– la memoria ocupada por este no aumenta.

Este análisis sumado a que el LinkedList requiere constantemente creación dinámica de memoria y con esto llamadas al kernel de Windows, fragmentación de la memoria, espacio extra para la actualización de la estructura del Memory Manager del Sistema Operativo y grandes dolores de cabezas con posibles punteros perdidos, nos hace pensar que no es muy factible.

Por otra parte el Vector al poseer todos los datos de forma consecutiva no presenta los problemas anteriores. Aclaremos que el Vector sólo aumenta su tamaño cuando el número de datos excede el doble de la cantidad que había la última vez que creció. Esto cada vez es menos frecuente, además la copia de los datos al nuevo espacio reservado es extremadamente rápida.

La inserción

Ambas estructuras tienen un comportamiento similar, el Vector lo inserta al final y el LinkedList por lo regular al inicio. A excepción por la llamada de reservación de memoria por el LinkedList no hay mayores problemas. Como se vio anteriormente la duplicación del Vector no es un problema que nos quite el sueño.

La eliminación

En este caso, en ambas estructuras se necesita iterar por todos los elementos hasta encontrar el deseado y luego eliminarlo. En el caso del Vector es necesario cubrir el hueco copiando el último elemento o corriendo todos los elementos a partir de la posición k + 1 para la posición k donde k en el índice del elemento eliminado.

En el LinkedList se elimina el nodo y el apuntador del nodo anterior se iguala al nodo siguiente del eliminado o NULL si este no existe.

En dependencia de la técnica escogida en el vector será uno igual o más eficiente que el otro. Pero no es algo que determine.

Antes de tocar el último punto analicemos el problema en cuestión. Una biblioteca recibe muchos libros los primeros días, pero posteriormente no es un evento frecuente. La eliminación de libros sucede cuando uno está prestado, es robado, se perdió. A excepción de los préstamos los demás eventos tampoco resultan frecuentes. Sin embargo la búsqueda se realiza de forma constante, por lo que esta acción debe ser la más eficiente.

La búsqueda

En el Vector se iteran por todos los elementos hasta hallar el deseado y en el LinkedList nos desplazamos por cada nodo con la misma intensión. Lo gracioso es que debido a las operaciones de bajo nivel que implican estas acciones, el Vector presenta un mejor comportamiento a pesar de tener órdenes iguales.

Se aclarar que aún así estas búsquedas presentan tiempos muy pobres y pudieran ocurrírsenos algunos cambios los cuales definitivamente dejarían a una de estas estructuras completamente rezagadas. Piénselo un momento ante de ver la respuesta.

La magia de la ordenación y el INVENTO:

Ordenar un LinkedList es una tarea ardua y no nos beneficia en nuestro objetivo. Sin embargo ordenar el Vector resulta relativamente fácil y con un orden eficiente O (n log n), valiéndonos de un algoritmo de búsqueda binaria reduciríamos el tiempo de búsqueda que antes era O (n) hasta O (log n). El problema es que los órdenes de la inserción y eliminación manteniendo el Vector ordenado subirían a O (n) y aunque estas acciones no son frecuentes si lo son los préstamos que conllevan a una eliminación tras una inserción. Esto tiene solución, nuevamente los invito a pensarla antes de leer la respuesta.

La solución es no eliminar del Vector un libro al ser prestado sino poner una marca booleana indicando que no está disponible. De esta forma siempre que se busque se encontrará como que la biblioteca tiene este libro, pero no está disponible en estos momentos. En caso de existir varios libros iguales con una mínima modificación a la marca se soluciona el problema y se puede dejar como ejercitación.

Conclusiones

El LinkedList por lo general es una estructura que se utiliza como sustento de otras como grafos, árboles, hash enlazado, estructuras de mapas, etc.
Los Vectores por lo general se utilizan para almacenar elementos que requieren una iteración frecuente, almacenaje temporal, etc.

Cuando se utiliza una estructura de datos no basta con conocer sus órdenes es necesario tener un conocimiento profundo de su comportamiento en cada situación y del problema en cuestión que esta va a resolver.

Existen otras estructuras para resolver este problema que nos brindan tiempos mucho más factibles. Estas pueden ser árboles binarios, B-Tree y Tablas de Hash.

Artículos relacionados