Guia 5
Guia 5
Guia 5
Una estructura auto referenciada contiene un miembro de apuntador que apunta a una
estructura del mismo tipo de estructura. Por ejemplo, la definición:
struct node
{
int data;
struct node*nextPtr;
}
define un tipo, struct node. Una estructura del tipo struct node tiene dos miembros —el
miembro entero data y el miembro de apuntador nextPtr. El miembro nextPtr apunta a
una estructura de tipo struct node —una estructura del mismo tipo que la que se está
declarando aquí, de ahí el "término estructura auto referenciada". El miembro nextPtr se
conoce como un enlace o vínculo —es decir, nextPtr puede ser utilizada para "vincular"
una estructura del tipo struct node con otra estructura del mismo tipo. Las estructuras
auto referenciadas pueden ser enlazadas juntas para formar útiles estructuras de datos
como son las listas, las colas de espera, las pilas y los árboles. Estas estructuras de
datos almacenan un conjunto de objetos del mismo tipo, relacionados entre sí mediante
punteros contenidos en ellos mismos, de forma que, basta conocer la raíz de un árbol o
el principio de una lista (normalmente terminadas en un puntero NULL, usado como
centinela), para poder acceder a todo el conjunto
La creación y mantenimiento de estructuras dinámicas de datos, requiere de la
asignación dinámica de memoria —la capacidad por parte de un programa de obtener,
en tiempo de ejecución, más espacio de memoria para contener nuevos nodos, y de
poder liberar espacio ya no requerido. El límite de la asignación dinámica de memoria
pude ser tan grande como la totalidad de memoria física disponible en la computadora,
o la cantidad de memoria virtual disponible, en un sistema de memoria virtual.
La clase SortedList es una colección de pares (clave, valor) que se ordenan según las
claves. Se puede acceder a esos pares por clave y también por índice (indexación
basada en cero). Esto viene bajo el espacio de nombres System.Collections.
Características de la clase SortedList:
Se puede acceder a un elemento SortedList por su clave o por su índice.
Un objeto SortedList mantiene internamente dos arrays para almacenar los
elementos de la lista, es decir, una matriz para las claves y otra matriz para los valores
asociados.
Una clave no puede ser nula, pero un valor puede serlo.
La capacidad de un objeto SortedList es el número de elementos que puede contener
SortedList.
Un SortedList no permite claves duplicadas.
Las operaciones en un objeto SortedList tienden a ser más lentas que las
operaciones en un objeto Hashtable debido a la clasificación.
Se puede acceder a los elementos de esta colección mediante un índice de números
enteros. Los índices de esta colección son de base cero.
-SortedList(): Inicializa una nueva instancia de la clase SortedList que está vacía, tiene
la capacidad inicial predeterminada y se ordena según la interfaz IComparable
implementada por cada clave agregada al objeto SortedList.
-SortedList(IComparer): Inicializa una nueva instancia de la clase SortedList que está
vacía, tiene la capacidad inicial predeterminada y se ordena según la interfaz IComparer
especificada.
-SortedList(IComparer, Int32): Inicializa una nueva instancia de la clase SortedList que
está vacía, tiene la capacidad inicial especificada y se ordena según la interfaz
IComparer especificada.
-SortedList(IDictionary): Inicializa una nueva instancia de la clase SortedList que
contiene elementos copiados del diccionario especificado, tiene la misma capacidad
inicial que el número de elementos copiados y se ordena según la interfaz IComparable
implementada por cada clave.
-SortedList(IDictionary, IComparer): Inicializa una nueva instancia de la clase
SortedList que contiene elementos copiados del diccionario especificado, tiene la misma
capacidad inicial que el número de elementos copiados y se ordena según la interfaz
IComparer especificada.
-SortedList(Int32): Inicializa una nueva instancia de la clase SortedList que está vacía,
tiene la capacidad inicial especificada y se ordena según la interfaz IComparable
implementada por cada clave agregada al objeto SortedList.
3. Una estructura definida como genérico provee ventajas en cuanto a la
verificación de tipos. ¿Cuáles puede indicar?
Hay un ligero defecto en este esquema cuando ocurren conflictos (es decir, dos claves
distintas se asignan a la misma celda, o elemento, en el arreglo). Como no podemos
ordenar dos registros de datos distintos en el mismo espacio, necesitamos encontrar un
lugar alternativo para todos los registros más allá del primero que se asignen a un
subíndice particular en el arreglo. Un esquema para hacer esto es reasignar la
transformación de hashing a la clave, para proporcionar una siguiente celda candidata
en el arreglo. El proceso de hashing está diseñado para ser aleatorio, por lo que se
supone que con sólo unos cuantos valores de hash se encontrará una celda disponible.
Otro de los esquemas utiliza un valor de hash para localizar la primera celda candidata.
Si la celda está ocupada, se realiza una búsqueda lineal en las celdas subsiguientes
hasta encontrar una celda disponible. Para obtener datos se realiza el mismo
procedimiento: se obtiene un valor de hash para la clave, y la celda resultante se
comprueba para determinar si contiene los datos deseados. Si es así, la búsqueda
termina. Si no, se realiza una búsqueda lineal en las celdas subsiguientes hasta que se
encuentran los datos deseados. La solución más popular para los conflictos de tablas
hash es hacer que cada celda de la tabla sea un “recipiente” hash; por lo general, una
lista enlazada de todos los pares clave-valor que se asocian a esa celda. Ésta es la
solución que implementa la clase Hashtable del .NET Framework. El factor de carga
afecta al rendimiento de los esquemas de hash. El factor de carga es la proporción del
número de objetos almacenados en la tabla hash en relación con el número total de
celdas de la tabla hash. A medida que esta proporción aumenta, la probabilidad de
conflictos tiende a incrementarse.
Las dos clases tienen modelos de objetos similares, pero difieren en el uso de la
memoria y la velocidad de inserción y eliminación:
SortedList usa menos memoria que SortedDictionary.
SortedDictionary tiene operaciones de inserción y eliminación más rápidas para datos
no ordenados.
Si la lista se completa de una vez con datos ordenados, SortedList es más rápido que
SortedDictionary.
Casos de uso:
SortedDictionary se debe usar cuando:
Se requieren más operaciones de inserción y eliminación.
El acceso a la clave es suficiente y no se requiere el acceso al índice.
La memoria no es un cuello de botella.
Los datos están desordenados.
HashTable
Ventajas:
Acceso a los datos almacenados muy rápido.
Desventajas:
Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados
crece. Se trata de una operación costosa.
Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar
la totalidad de los elementos.
NO podemos recorrer la tabla secuencialmente.
Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles
elementos, se consume más memoria de la necesaria.
Restricciones:
No se puede ordenar dos registros de datos distintos en el mismo espacio
Dictionary
Ventajas:
Recuperar un valor mediante su clave es muy rápido.
Rápido acceso.
El sistema de gestión de archivos se encarga de relacionar la posición de cada
registro con su contenido mediante la tabla de índices.
Desventajas:
Desaprovechamiento del espacio por quedar huecos intermedios cada vez que se
actualiza el archivo.
Se necesita espacio adicional para el área de índices.
Restricciones:
Una clave no puede ser null.
Requiere una implementación de igualdad para determinar si las claves son iguales.
SortedDictionary
Ventajas:
Operaciones de inserción y eliminación más rápidas para datos no ordenados.
Desventajas:
Gran uso de memoria con respecto a la búsqueda de elementos.
Restricciones:
Las claves son inmutables, siempre únicas y no pueden ser nulas.
SortedList
Ventajas:
Poder almacenar datos ordenados sin pasar por una rutina separada de ordenar el
contenido de una colección.
Puede aplicar la búsqueda binaria.
Desventajas:
Adiciones y eliminaciones más lentas de elementos de la lista.
Siempre debe estar ordenada.
Restricciones:
La clave debe ser de un tipo compatible con IComparable , ya sea un número entero
o una cadena.
8. Analice los tips de rendimiento de las clases vistas en los ítems previos de
Deitel. ¿Cuáles de ellos le resultan más llamativos? ¿Por qué?
ArrayList:
Al igual que con las listas enlazadas, insertar elementos adicionales en un objeto
ArrayList cuyo tamaño actual sea menor que su capacidad es una operación rápida.
Insertar un elemento en un objeto ArrayList que necesite crecer más para acomodarlo
es una operación lenta. Un objeto ArrayList que se encuentra al límite de su capacidad
debe reasignar su memoria y los valores existentes que están copiados en la misma.
HashTable:
El factor de carga en una tabla hash es un ejemplo clásico de una concesión entre
espacio/tiempo: al incrementar el factor de carga, obtenemos un mejor uso de la
memoria, pero la aplicación se ejecuta con más lentitud debido al aumento en los
conflictos de hash. Al reducir el factor de carga obtenemos una mayor velocidad en la
aplicación, debido a que se reducen los conflictos de hash, pero obtenemos un uso más
deficiente de la memoria, ya que una gran parte de la tabla hash permanece vacía.
SortedDictionary:
Desde el punto de vista del grupo, la clase SortedDictionary nos parece más llamativas
que las demás, ya que la inserción, eliminación y búsqueda de datos se realiza en un
tiempo mucho menor que a las demás clases.