Guia 5

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 10

1.

Cuando hablamos de estructuras auto - referenciadas nos referimos a clases


poseen variables del mismo tipo que dicha clase. ¿Qué ventajas prevé este
mecanismo? ¿Qué tipos de estructuras de datos se representan mejor con esta
forma de codificación?

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.

2. Describa las características y mecanismos de funcionamiento de SortedList.

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.

La clase SortedList posee 6 constructores:

-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?

Las ventajas que provee una estructura genérica se podrían detallar en lo


siguiente:
 Detectar conflictos de tipo en tiempo de compilación, a esto se lo conoce como
“Seguridad de tipos en tiempo de Ejecución”.
 Es posible definir, por ejemplo, una clase Pila genérica que sea la base para
poder crear varias clases Pila que almacenen distintos tipos de datos (Pila de
Double, Pila de Int, Pila de Char, Pila de String).
 En tiempo de compilación, el compilador se encarga de la seguridad de los
tipos en el código.
 En el caso de que hayamos definido una clase base Pila <y> y sus derivadas
como las mencionadas en el punto 2, el sistema en tiempo de ejecución se
encarga de la sustitución de los parámetros de tipo para nuestra clase
contenedora interactúe directamente con la clase Pila genérica.
 El compilador realiza la comprobación de tipos en los parámetros en los
parámetros de tipo de la clase, de esta forma se asegura que pueda utilizarse
con el código de la clase genérica.

4. Describa las características y mecanismos de funcionamiento de Hashtable y


Dictionary.

Cuando una aplicación crea objetos de tipos nuevos o ya existentes, necesita


administrarlos en forma eficiente. Las acciones de ordenar y obtener información con
los arreglos son eficientes si algún aspecto de nuestros datos coincide directamente con
el valor clave, y si esas claves son únicas y están estrechamente empaquetadas. Si
tenemos 100 empleados con números de Seguro Social de nueve dígitos, y queremos
almacenar y recuperar los datos de los empleados mediante el uso del número de
Seguro Social como clave, por lo general se requeriría un arreglo con 999,999,999, ya
que hay 999,999,999 números únicos de nueve dígitos. Si tenemos un arreglo de ese
tamaño, podríamos tener un rendimiento muy alto al ordenar y obtener los registros de
los empleados con sólo utilizar el número de Seguro Social como índice para el arreglo,
pero sería un gran desperdicio de memoria. Lo que se necesita es un esquema de alta
velocidad para convertir claves como los números de Seguro Social y los números de
pieza en los inventarios en índices únicos para el arreglo. Así, cuando una aplicación
necesite almacenar algo, el esquema podría convertir la clave de la aplicación
rápidamente en un índice, y el registro de información podría almacenarse en esa
ubicación del arreglo. Esto es la base de una técnica conocida como hashing, en la que
almacenamos datos en una estructura de datos conocida como tabla de hash. ¿Por qué
el nombre? Porque cuando convertimos una clave en un subíndice de un arreglo,
literalmente revolvemos los bits, haciendo un “picadillo (hash)” del número. En realidad,
este número no tiene un significado real más allá de su utilidad para almacenar y obtener
este registro de datos específico. Al igual que en el SortedList, los elementos están
compuestos por una pareja (clave, valor). No obstante, la tabla hash utiliza una “función
de dispersión” para colocar los elementos de forma que NO podemos recorrer la tabla
secuencialmente, pero por el contrario la búsqueda de elementos a partir del campo
clave es muy rápido. La tabla Hash tiene una capacidad inicial que se va ampliando a
medida que se necesita espacio. Si queremos inicializarla con un valor concreto porque
sabemos aproximadamente el número de elementos en el constructor podemos incluir
el parámetro.
Los diccionarios en C# implementan la interfaz IDictionary. Existen varios tipos de
Diccionario, pero el más utilizado es el diccionario genérico, a menudo denominado
Dictionary<TKey, TValue>: contiene una clave específica de tipo y un valor
correspondiente específico de tipo. Esto es básicamente lo que separa un Diccionario
de una Lista: los elementos de una lista vienen en un orden específico y se puede
acceder a ellos mediante un índice numérico, donde los elementos de un diccionario se
almacenan con una clave única, que luego se puede utilizar para recuperar el artículo
de nuevo. La capacidad de un diccionario es el número de elementos que el diccionario
puede contener. A medida que se agregan elementos al diccionario la capacidad
aumenta automáticamente según sea necesario mediante la reasignación de la matriz
interna.

5. Que método de manejo de duplicados describe Deitel & Deitel respecto de


HashTable?

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.

6. Compare, detalle diferencias y similitudes entre SortedDictionary y SortedList.


Identifique un caso de uso más favorables para cada una de ellas. Justifique sus
elecciones.

Anteriormente mencionamos que la clase SortedList es una colección de pares (clave,


valor) que se ordenan según las claves. Para guardar sus elementos utiliza una
hashtable.
Interfaces que implementa:
 IEnumerable
 ICollection
 IDictionary
 ICloneable

La clase SortedDictionary se usa para representar la colección de pares clave/valor.


Este par también está ordenado según las claves, pero a diferencia de SortedList, solo
se puede acceder a los pares a través de su clave, y no a través de un índice. Para
guardar sus elementos implementa un árbol binario.
Interfaces que implementa:
 ICollection
 IDictionary
 IEnumerable
 IReadOnlyCollection
 IReadOnlyDictionary

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.

Por otro lado, SortedList se debe usar cuando:


 Se requieren más búsquedas y menos operaciones de inserción y eliminación.
 Se requiere acceso al índice.
 La memoria es una sobrecarga.
 Los datos ya están ordenados (si no todos, la mayoría).

7. Realice una tabla comparativa de las estructuras vistas anteriormente en los


puntos 4 al 6 indicando ventajas, desventajas y restricciones de uso.

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.

Si el almacenamiento es de máxima importancia, use el método TrimToSize de la clase


ArrayList para recortar un objeto ArrayList a su tamaño exacto. Esto optimizará el uso
de la memoria del objeto ArrayList. Pero debe tener cuidado; si la aplicación necesita
insertar elementos, el proceso será más lento debido a que el objeto ArrayList debe
crecer en forma dinámica (el recorte no deja espacio para que crezca).

Tal vez parezca que el incremento predeterminado de la capacidad de un objeto


ArrayList (duplicar su tamaño) desperdicia espacio de almacenamiento, pero duplicar el
tamaño es una manera eficiente de que un objeto ArrayList crezca con rapidez al tamaño
más apropiado. Éste es un uso mucho más eficiente de tiempo que aumentar el tamaño
del objeto ArrayList un elemento a la vez, en respuesta a las operaciones de inserción.

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:

Como la clase SortedDictionary mantiene sus elementos ordenados en un árbol binario,


para obtener o insertar un par clave-valor se requiere un tiempo definido por O (log n),
que es rápido en comparación con el proceso de realizar una búsqueda lineal y después
la inserción.

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.

9. En el capítulo 25 de Deitel se describen métodos genéricos. Describa su uso.


Compare con sobrecarga de métodos. ¿Qué ventajas y desventajas identifica en
cada uno de ellos?

Los métodos genéricos nos permiten especificar, mediante la declaración de un solo


método, un conjunto de métodos relacionados. Los genéricos proporcionan seguridad
de tipos en tiempo de compilación.
Podemos escribir un método genérico para ordenar un arreglo de objetos y después
invocar al método genérico por separado con un arreglo int, un arreglo double, un arreglo
string y así sucesivamente, para ordenar cada tipo distinto de arreglo. El compilador
realiza la comprobación de tipos para asegurar que el arreglo que se pasa al método de
ordenamiento contenga sólo elementos del mismo tipo.
Si las operaciones realizadas por varios métodos sobrecargados son idénticas para
cada tipo de argumento, los métodos sobrecargados pueden codificarse en forma más
compacta y conveniente, usando un método genérico.
Se puede escribir una sola declaración de un método genérico, que pueda llamarse en
distintos momentos, con argumentos de tipos diferentes. Con base en los tipos de los
argumentos que se pasan al método genérico, el compilador maneja cada llamada al
método de manera apropiada.

Comparación entre métodos sobrecargados y genéricos


Código usando métodos sobrecargados:

Código usando un método genérico:

Ventajas: programa mas eficiente debido a un ahorro significativo en líneas de código


ya que con único método es posible realizar la misma función que utilizando métodos
sobrecargados.

También podría gustarte