PDF de programación - Capítulo 3. Conjuntos y diccionarios

104

Capítulo 3. Conjuntos y diccionarios

Suponiendo que el valor Di−1 de la permutación tiene una representación bina-
ria (d1, d2, . . . , dn), el siguiente valor Di viene dado por: si d1 = 0 entonces Di =
(d2, d3, . . . , dn, 0); en otro caso Di = (d2, d3, . . . , dn, 0) XOR K.

Por ejemplo, para B = 8 podemos tomar K = 5 y empezando con D1 = 1 tenemos

la siguiente permutación.

D1
001

D2
010

D3
100

D5
010

D4
D6
000
110
⊕101 ⊕101 ⊕101
=101 =111 =011

D7
110

1

2

4

5

7

3

6

De nuevo, esta función de redispersión tiene el inconveniente de producir las mismas
secuencias de búsqueda para los elementos sinónimos, ya que la permutación es prefija-
da de antemano. Una alternativa podría ser utilizar distintos valores iniciales para los
sinónimos. De esta forma, tenemos que el valor inicial D1 debería depender de la clave,
por ejemplo D1(x) = x mod (B − 1) + 1. Los siguientes valores serían calculados según el
algoritmo anterior.

Redispersión con saltos de tamaño variable

Basándonos en la idea de la redispersión con saltos de tamaño C, podemos definir
una función similar pero utilizando tamaños de paso distintos para valores de clave dis-
tintas. Los tamaños de paso válidos deberían ser primos respecto al tamaño de la tabla
B. Si B es un número primo, cualquier C entre 1 y B − 1 será válido. Con esto, la función
de redispersión sería:

hi(x) = (h(x) + iC(x)) mod B
Donde C(x) es una función cualquiera –al estilo de la función de dispersión– que
devuelve un valor en el intervalo: (1, . . . , B − 1). Por este motivo, esta técnica se suele
conocer también como dispersión doble. Por ejemplo, una función válida podría ser
C(x) = 1 + (x2/D + Ex) mod (B − 1).

Eligiendo C(x) de forma adecuada, podemos conseguir que los sinónimos produzcan

secuencias de búsqueda distintas, resolviendo así el problema del agrupamiento.

3.3. Combinando estructuras de datos

Hasta ahora hemos estudiado las estructuras de datos como realizaciones en memoria
de un tipo abstracto de datos. En la práctica, al diseñar una estructura, tenemos en
cuenta cuestiones de eficiencia que son obviadas en el estudio del tipo abstracto. En
una aplicación real necesitaremos, posiblemente, hacer adaptaciones de las estructuras
estudiadas e incluso combinar varias de ellas en lo que podríamos llamar una estructura
múltiple. Pero, ¿por qué iba a ser necesario combinar dos estructuras para los mismos
datos? Y ¿cómo hacer la combinación?

La eficiencia de una estructura de datos es un concepto relativo: la eficiencia se mide
en función de las operaciones que se vayan a utilizar sobre esa estructura. Una estructura

3.3. Combinando estructuras de datos

105

puede resultar eficiente para cierto tipo de operaciones pero muy ineficiente para otro tipo.
Por ejemplo, hemos visto que las tablas de dispersión son muy eficientes para acceder a
cierto elemento de forma directa según su clave. Pero ¿y si queremos acceder de forma
ordenada, por ejemplo buscar el máximo o el mínimo? O ¿cómo podríamos implementar
una operación que acceda por un atributo que no sea la clave? Deberíamos acceder a
todas las cubetas de la tabla, ver si están ocupadas o no, y en caso de estarlo comprobar
el elemento y actuar de forma adecuada. En definitiva, resultarían muy ineficientes para
ese tipo de operaciones.

3.3.1. Estructuras de datos múltiples

Si sobre unos mismos datos necesitamos distintos tipos de operaciones, entonces
posiblemente no exista una estructura que nos proporcione eficiencia para todas ellas.
En ese caso, puede ser adecuado combinar varias estructuras –que referencien a los mis-
mos datos– cada una de las cuales nos proporciona un acceso rápido para cierto tipo de
operaciones.

Supongamos, por ejemplo, que en una aplicación de gestión empresarial almacena-
mos información sobre los empleados. En concreto, tenemos el nombre de cada empleado,
su dirección, sueldo, DNI y teléfono (o teléfonos, si tiene más de uno). Las operaciones
que más se van a utilizar serán las siguientes:
A) Dado un DNI (A1), un nombre (A2) o un teléfono (A3), devolver todos los datos

B)

del empleado correspondiente.
Insertar (B1), eliminar (B2) o modificar (B3) un empleado, accediendo por
número de DNI.

C) Listar los empleados por sueldo (C1) o por número de DNI (C2).

Para almacenar los datos relativos a un empleado podemos utilizar un tipo de datos

Empleado, definido del siguiente modo:

tipo

Empleado = registro
Nombre: cadena
Direccion: cadena
DNI: entero
Telefonos: Lista[entero]
Sueldo: entero

finregistro

Pero, realmente el problema no es cómo representar un empleado, sino cómo alma-
cenar el conjunto de todos los empleados de forma que todas las operaciones anteriores
se puedan realizar de forma eficiente; es decir, cómo representar los datos.

Distintas estructuras de representación

Analicemos distintas posibles estructuras de representación para el problema.

Para facilitar las operaciones de tipo (C1) sería interesante almacenar los registros de
empleados en una lista ListaSueldos: Lista[Empleado], ordenada por valor del campo
Sueldo. El listado de los empleados por orden de sueldo se puede hacer fácilmente

106

Capítulo 3. Conjuntos y diccionarios

recorriendo esta lista. Pero ahora, ¿qué pasa con las operaciones (A), (B) y (C2),
de consulta por DNI, nombre o número de teléfono? Por ejemplo, para la (A2)
tendríamos que recorrer toda la lista hasta encontrar un elemento cuyo valor del
campo Nombre coincida con el buscado. Si tenemos n empleados, necesitaríamos un
O(n) en el caso promedio. Pero, es más, para la operación de consulta por número
de teléfono, (A3), además de recorrer toda la lista deberíamos consultar la lista
Telefonos dentro de cada empleado. El tiempo de ejecución sería un O(n r), siendo
r el número promedio de teléfonos por empleado. La representación es, por lo tanto,
adecuada para un tipo de operación pero ineficiente para los demás.

Para facilitar las operaciones de consulta por nombre, sería más conveniente tener
una tabla de dispersión donde las claves fueran los nombres y los valores fueran de
tipo Empleado, por ejemplo HashNombre: TablaHash[cadena, Empleado]. La consulta
por nombre sería muy rápida; usando un número de cubetas B ≈ n podríamos
alcanzar un O(1) para esas operaciones. Pero, ¿qué ocurre ahora para la consulta
por teléfono, por DNI o listar según el sueldo? Los teléfonos y los sueldos de los
empleados están almacenados en la tabla, pero intentar acceder por ellos resultaría
muy costoso. Por ejemplo, si usamos dispersión cerrada, deberíamos recorrer todas
las cubetas, comprobando las que no están vacías, y recorrer sus listas de teléfonos.
El orden de complejidad sería un O(B + n r), con B > n.

Para solucionar el problema anterior, podríamos usar una tabla de dispersión abier-
ta HashTelefonos: TablaHash[entero, Empleado] donde las claves fueran números de
teléfono y los valores de tipo Empleado. Usando ahora una tabla de tamaño B ≈ n
conseguiríamos implementar la operación de tipo (A3) de forma muy eficiente, en
un O(r) en promedio. Pero para todas las demás operaciones deberíamos recorrer
la tabla completamente. Por ejemplo, para la operación de consulta por DNI ten-
dríamos que recorrer toda la tabla y buscar un registro con ese DNI. El tiempo de
ejecución sería un O(B + n r). Además, si un empleado tiene más de un teléfono,
se estaría repitiendo información en la tabla.

Por otro lado, si consideramos las operaciones (A1) y (B), de consulta por DNI,
lo más conveniente sería usar una estructura de datos que nos permita acceder
rápidamente por DNI, como una tabla de dispersión. El inconveniente ahora es la
operación (C2) para listar ordenadamente los DNI. Ya hemos visto que las tablas
de dispersión resultan muy ineficientes para este tipo de operaciones. Una buena
solución sería utilizar un árbol binario de búsqueda, ArbolDNI, que dado un conjunto
de n datos nos proporciona un tiempo O(log n) para la búsqueda directa y O(n) para
el listado ordenado (con un recorrido en in-orden). Pero, nuevamente, optimizar las
operaciones que acceden por DNI implica hacer más costosas las operaciones que
acceden por otros campos.

Estructura de datos combinada

Está claro que ninguna estructura por separado nos proporciona una buena solución
para todos los tipos de operaciones. Cada una está orientada a optimizar cierta clase

3.3. Combinando estructuras de datos

107

de operaciones. La cuestión es ¿sería posible aprovechar lo mejor de cada una de ellas,
consiguiendo eficiencia en todas las operaciones? La respuesta es que sí; la solución consiste
básicamente en utilizar al mismo tiempo todas las estructuras antes propuestas, haciendo
que referencien al mismo conjunto de datos. Es decir, tenemos un mismo conjunto de
datos almacenados, pero diferentes estructuras de acceso a los mismos. Esta idea da lugar
a lo que se conoce como estructuras de datos múltiples. En nuestro caso, la estructura
sería como la mostrada en la figura 3.6.

Para no duplicar información, tanto la lista como las tablas de dispersión y el árbol
deberían contener punteros o referencias a registros de tipo Empleado. De esta forma, estos
datos no están repetidos, sino que cada empleado se almacena en memoria una sola vez.
La definición de los tipos sería la siguiente:

tipo

Empleados = registro

ListaSueldos: Lista[Puntero[Empleado]]
HashNombres: TablaHash[cadena, Puntero[Empleado]]
HashTelefonos: TablaHash[entero, Puntero[Empleado]]
ArbolDNI: ArbolBinarioBusqueda[entero, Puntero[Empleado]]

finregistro

HashTelefonos

0 1

2

....

B -1T

ArbolDNI

EMPLEADOS

Nombre: cadena
Dirección: cadena
DNI: entero
Telefonos: Lista[entero]
Sueldo: entero

HashNombres

0

1

2

.
.
.

B -1N

ListaSueldos

Figura 3.6: Ejemplo de estructura de datos múltiple. Varias estructuras referencian al
mismo conjunto de datos almacenados.

A continuaci´