Download Estructuras de Datos Avanzadas

Técnicas Avanzadas de Programación
Estructuras de Datos Avanzadas
Héctor Navarro
Heaps
• Árbol esencialmente completo: si todo nodo
interno, con la posible excepción de un nodo
especial, tiene exactamente dos hijos. El
nodo especial, si existe, está situado en el
nivel K-1 y posee un hijo izquierdo, pero no
derecho. Todas la hojas están en el nivel K o
en los niveles K y K-1. Ninguna hoja de nivel K1 está a la izquierda de un nodo interno del
mismo nivel
Heaps
• Árbol esencialmente completo: si todo nodo
interno, con la posible excepción de un nodo
especial, tiene exactamente dos hijos. El nodo
especial, si existe, está situado en el nivel K-1
y posee un hijo izquierdo, pero no derecho.
Todas la hojas están en el nivel K o en los
niveles K y K-1. Ninguna hoja de nivel K-1 está
a la izquierda de un nodo interno del mismo
nivel
Heaps
• Árbol esencialmente completo: si todo nodo
interno, con la posible excepción de un nodo
especial, tiene exactamente dos hijos. El nodo
especial, si existe, está situado en el nivel K-1 y
posee un hijo izquierdo, pero no derecho.
Todas la hojas están en el nivel K o en los
niveles K y K-1. Ninguna hoja de nivel K-1 está
a la izquierda de un nodo interno del mismo
nivel
Heaps
• Árbol esencialmente completo: si todo nodo
interno, con la posible excepción de un nodo
especial, tiene exactamente dos hijos. El nodo
especial, si existe, está situado en el nivel K-1 y
posee un hijo izquierdo, pero no derecho.
Todas la hojas están en el nivel K o en los
niveles K y K-1. Ninguna hoja de nivel K-1 está
a la izquierda de un nodo interno del mismo
nivel
Heaps
• Intuitivamente es un árbol en el que los nodos
internos se han subido lo más posible en el
árbol y los nodos hoja del último nivel lo más
a la izquierda posible
Heaps
• En un árbol binario esencialmente completo
con altura K hay un nodo en el nivel 0, dos
nodos en el nivel 1, y así sucesivamente 2K-1
nodos en el nivel K-1 y al menos uno, pero no
más de 2K en el nivel K. La altura de un árbol
esencialmente completo es K=log n
Heaps
• Estos árboles pueden fácilmente almacenarse
en un arreglo. Si la raíz está almacenada en la
posición 1 del arreglo, el hijo izquierdo de un
nodo p está en la posición 2p y su hijo
derecho en la posición 2p+1
• El padre del nodo en la posición p está en p/2.
Heaps
• Un heap es un AEC, en donde la clave de cada
subárbol es mayor o igual a la clave de todos
sus hijos, y cada subárbol es también un heap.
• En un heap existe una relación de orden
parcial, a diferencia de los árboles de
búsqueda
• Esta relación existe entre cada nodo y sus
descendientes y ascendientes
Heaps
Pos
0
Valor 10
1
2
3
4
5
6
7
8
9
10
1
7
3
11
8
5
9
14
12
10
Heaps
Pos
0
Valor 10
1
2
3
4
5
6
7
8
9
10
1
7
3
11
8
5
9
14
12
10
• La posición 0 del arreglo contiene la posición
del último elemento del heap
• En un heap encontrar el elemento mayor (o
menor) siempre es de O(1)
• Suele hablarse de MaxHeap y MinHeap
Heaps
• Inserción
– Insertar el elemento en la última posición libre del
arreglo
– El elemento “flota” hasta su posición final
• Por ejemplo, insertar 2 en el heap del ejemplo
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
1
7
3
11
8
5
9
14
12
10
2
10
Heaps
• Inserción
– Insertar el elemento en la última posición libre del
arreglo
– El elemento “flota” hasta su posición final
• Por ejemplo, insertar 2 en el heap del ejemplo
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
1
7
3
11
8
5
9
14
12
10
2
11
p=11. ppadre = 11/2 = 5
Heaps
• Inserción
– Insertar el elemento en la última posición libre del
arreglo
– El elemento “flota” hasta su posición final
• Por ejemplo, insertar 2 en el heap del ejemplo
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
1
7
3
11
2
5
9
14
12
10
8
11
p=5. ppadre = 5/2 = 2
Heaps
• Inserción
– Insertar el elemento en la última posición libre del
arreglo
– El elemento “flota” hasta su posición final
• Por ejemplo, insertar 2 en el heap del ejemplo
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
1
2
3
11
7
5
9
14
12
10
8
11
p=2. ppadre = 2/2 = 1
Heaps
• Encontrar la siguiente posición libre del heap:
O(1)
• Flotar el elemento: O(log n)
• Inserción: O(1)+O(log n) = O(log n)
Heaps
• Eliminación
– Siempre se elimina el elemento de la raíz
– El último elemento se coloca de primero
– El elemento se hunde hasta su posición final
• Por ejemplo, eliminar en el heap anterior
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
1
2
3
11
7
5
9
14
12
10
8
11
Heaps
• Eliminación
– Siempre se elimina el elemento de la raíz
– El último elemento se coloca de primero
– El elemento se hunde hasta su posición final
• Para hundir se compara con ambos hijos. Se
intercambia con el mayor (menor)
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
8
2
3
11
7
5
9
14
12
10
--
10
p=1. HI: 1*2 = 2. HD: 1*2+1 = 3
Heaps
• Eliminación
– Siempre se elimina el elemento de la raíz
– El último elemento se coloca de primero
– El elemento se hunde hasta su posición final
• Para hundir se compara con ambos hijos. Se
intercambia con el mayor (menor)
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
2
8
3
11
7
5
9
14
12
10
--
10
p=2. HI: 2*2 = 4. HD: 2*2+1 = 5
Heaps
• Eliminación
– Siempre se elimina el elemento de la raíz
– El último elemento se coloca de primero
– El elemento se hunde hasta su posición final
• Para hundir se compara con ambos hijos. Se
intercambia con el mayor (menor)
Pos 0
1
2
3
4
5
6
7
8
9
10
11
Val
2
7
3
11
8
5
9
14
12
10
--
10
p=5. HI: 5*2 = 10. HD: 5*2+1 = 11
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
2
5
1
8
9
5
3
6
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
2
5
1
8
9
5
3
6
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
2
5
1
8
9
5
3
6
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
2
5
8
1
9
5
3
6
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
2
6
8
1
9
5
3
5
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
7
9
6
8
1
3
5
2
5
4
Heaps
• Heapify: convertir un arreglo de elementos
comparables en un heap:
heapify(T[0..N])
{
for(i = N/2; i>0; i--)
hundir(T, i);
}
O(n log n)
9
8
6
7
1
3
5
2
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
hundir(T, 1);
}
}
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
hundir(T, 1);
}
}
7
2
5
1
8
9
5
3
6
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
O(N log N)
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
hundir(T, 1);
1
}
}
9
8
6
7
3
5
2
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]); O(1)
T[0]--;
hundir(T, 1);
}
}
9
8
6
7
1
3
5
2
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--; O(1)
hundir(T, 1);
}
}
2
8
6
7
1
3
5
9
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
hundir(T, 1); O(log N)
}
}
2
8
6
7
1
3
5
9
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
hundir(T, 1);
}
}
8
7
6
5
1
3
2
9
5
4
Heaps
• HeapSort
HeapSort(T[0..N])
{
Heapify(T);
for(i = N; i > 1; i--)
{
swap(T[1], T[i]);
T[0]--;
4
hundir(T, 1);
7
8
}
}
O(N log N) + O(N)*(O(1) +O(1) +O(log N))=
O(N log N) + O(N)*O(log N)=
O(N log N) + O(N log N) = O(N log N)
1
2
3
5
9
5
6
ANÁLISIS AMORTIZADO
Análisis Amortizado
• En análisis de complejidad muchas veces se
toma el peor caso como referencia para
estudiar el comportamiento de un algoritmo
• Algunas veces esto no se hace ya que el peor
caso es mucho peor que el caso promedio
• Por ejemplo, QuickSort
Análisis Amortizado
• Cuando se analizan las operaciones de
estructuras de datos muchas veces no basta
tomar el peor caso sino ver el
comportamiento a lo largo del tiempo
• Un ejemplo propuesto por Cormen propone la
operación Multipop(p,k) que realiza k
operaciones de pop sobre una pila p
Análisis Amortizado
• Si analizamos una llamada aislada a Multipop
veremos que es de O(K)
• Ahora analicemos el comportamiento de N
llamadas a Multipop
• La primera llamada es de O(K), suponiendo
K>=S (tamaño de la pila)
• Las siguientes llamadas serán todas de O(1)
Análisis Amortizado
• Finalmente la complejidad promedio será:
N
O( S )   O(1)
i 2
N

O( S )  O( N )
 O(1)
N
Ya que podemos suponer que hay suficientes
llamadas a Multipop para que N>S
• Este tipo de análisis se llama análisis amortizado
ya que una de las operaciones está “comprando a
crédito” el costo de otras operaciones
Análisis Amortizado
• Existen diversas técnicas para hacer análisis
amortizado. Estudiaremos el método del
potencial
• Suponemos una estructura de datos inicial D0
sobre la que se realizan n operaciones
• ci es el costo de aplicar la operación sobre la
estructura Di-1 y obtener Di
Análisis Amortizado
• Existe una función de potencial φ que mapea
cada estructura de datos Di a un número real
φ(Di).
• El potencial puede irse acumulando hasta que
en algún momento el potencial es liberado
• El costo amortizado de hacer la operación iésima se calcula como:
Análisis Amortizado
• El costo total de hacer n operaciones será:
Análisis Amortizado
• Para el ejemplo de la pila, podemos definir φ
como el número de elementos de la pila
• SI la pila está vacía, el potencial es 0
• A medida en que se incrementan el número
de elementos de la pila, el potencial se
incrementa, hasta “liberarlo” llamando a
multipop
Análisis Amortizado
• El costo amortizado de la operación push será:
• Para la operación multipop(p,k) con
k’=min(k,s), en donde s es el número de
elementos en la pila, k’ elementos serán
sacados de la pila. El costo de la operación es
k’
Análisis Amortizado
• Podemos concluir entonces que el costo
amortizado de la operación de multipop es de
O(1).
• Luego, hacer n operaciones arbitrarias será de
O(n) en promedio
HEAPS DE FIBONACCI
Heaps de Fibonacci
• Tienen la ventaja de que las operaciones en
donde no se eliminan elementos son de O(1)
• Sumamente útiles cuando el número de
operaciones de eliminación son pocas en
comparación a las demás operaciones
• En particular el algoritmo de Dijkstra es
sumamente eficiente con esta
implementación
Heaps de Fibonacci
• Un heap de Fibonacci es una colección de
árboles ordenados
Heaps de Fibonacci
• Representación
Heaps de Fibonacci
• Nótese el apuntador al mínimo elemento del
heap (min[H])
• En la representación se usan listas circulares
para hacer todos los nodos iguales
• Todo nodo tiene un apuntador a algún hijo
(cualquiera) y a su padre
Heaps de Fibonacci
• Las listas circulares tienen como ventaja que
se pueden eliminar nodos con O(1)
• Dos listas circulares pueden concatenarse con
O(1)
Heaps de Fibonacci
struct NodoHeapFib{
NodoHeapFib *p, *h;
NodoHeapFib *izq, *der;
int k;
int grado;
bool marca;
};
Heaps de Fibonacci
struct NodoHeapFib{
NodoHeapFib *p, *h;
NodoHeapFib *izq,*der;
int k;
Almacena la clave del nodo
int grado;
bool marca;
};
Heaps de Fibonacci
struct NodoHeapFib{
NodoHeapFib *p, *h;
NodoHeapFib *izq,*der;
int k;
Indica el grado del nodo
int grado;
(número de hijos)
bool marca;
};
Heaps de Fibonacci
struct NodoHeapFib{
NodoHeapFib *p, *h;
NodoHeapFib *izq,*der;
int k;
int grado;
Indica si un nodo ha
bool marca;
perdido algún hijo desde la
};
última vez que se convirtió
en hijo de otro nodo.
Inicialmente es falso
Heaps de Fibonacci
• Es importante el número de nodos n en un
heap de Fibonacci
• Luego veremos que el grado máximo de
cualquier heap de Fibonacci con n nodos es
D(n) = O(log n)
Heaps de Fibonacci – Función de
potencial
• Cada árbol en la raíz del heap suma un punto
a la función de potencial, ya que la extracción
del valor mínimo trabaja sobre el número de
árboles
• También hay que tomar en cuenta el número
de nodos ya marcados, ya que la operación de
decrementar clave debe recorrer todos los
nodos marcados
Heaps de Fibonacci – Función de
potencial
• En donde T(Di) es el número de árboles en la
raíz del heap y m(Di) es el número de nodos
marcados
• Para evitar problemas numéricos se utiliza:
Heaps de Fibonacci - Operaciones
• Creación: hacer n=0 y min[H] = NULL
• Inserción: para insertar un nodo x en un heap
H, primero iniciar los valores del nodo:
x.p = NULL;
x.h = NULL;
x.izq = x.der = x;
x.grado = 0;
x.marca = false;
Heaps de Fibonacci - Operaciones
• Enlazar el nodo x con la lista de árboles de H:
min[H].izq.der = x;
min[H].izq = x;
if(min[H]==NULL || x.clave < min[H].clave)
min[H] = x;
Heaps de Fibonacci - Operaciones
• Valor mínimo: es trivial ya que se tiene el
apuntador min[H]
• Unión: La unión de dos heaps consiste en
concatenar las listas de los heaps H1 y H2, y
buscar el elemento mínimo. Ambas
operaciones son de O(1) ya que hay sólo dos
candidatos a ser el mínimo: min[H1] y min[H2]
Heaps de Fibonacci - Operaciones
• Extracción del nodo mínimo: es la operación
más complicada. Primero se localiza el nodo
mínimo mediante min[H]. Todos sus hijos
pasan directamente a la raíz.
Heaps de Fibonacci - Operaciones
• El siguiente paso es consolidar el bosque para
reducir el número de árboles en la raíz de H.
Esto lo hace la función consolidar(H):
1. Encontrar dos nodos x, y en la raíz con el mismo
grado (x.k < y.k)
2. Enlazar y a x, removiendo y de la raíz y
poniéndolo como hijo de x. El grado de x se
incrementa y la marca de y se pone en falso
Heaps de Fibonacci - Operaciones
• Se hace uso de un arreglo auxiliar A de
apuntadores a nodos tal que A[i] apunta al
último nodo de grado i encontrado (o a NULL
si no se ha encontrado). Puede demostrarse
que el tamaño de A nunca será mayor a log(n)
Heaps de Fibonacci - Operaciones
Heaps de Fibonacci - Operaciones
• Decremento de una clave: para decrementar
el valor de un nodo x en un heap H primero es
necesario comprobar que efectivamente el
nuevo valor de la clave es menor que el actual
• Luego se compara el nuevo valor con el valor
del padre de x (y)
• Si x es menor se remueve de la lista de hijos
de y y se pone en la raíz de H (poniendo la
marca de x en falso)
Heaps de Fibonacci - Operaciones
• Ahora el nodo y debe marcarse ya que perdió
a un hijo
• En caso de que y ya hubiera sido marcado
previamente, hay que llevar al nodo y a la raíz
y repetir el proceso (marcar al padre de y)
Heaps de Fibonacci - Operaciones
• Eliminación de nodos: para eliminar un nodo
x de un HF H simplemente se decrementa la
clave de x hasta -∞ y luego extraemos el
mínimo nodo de H.
Complejidad – Decremento del
mínimo
• Si antes de hacer la operación habían T(Hn-1)
árboles, ahora habrán T(Hn-1)+m’(Hn-1)
• En donde m’(H) es cuántos nodos marcados
seguidos hay en el heap H
Complejidad – Decremento del
mínimo
• Ahora, el costo de una operación de
decremento de mínimo será:
• El nuevo heap tendrá ahora m(Hn) nodos
marcados:
Complejidad – Decremento del
mínimo
• Luego:
CONJUNTOS DISJUNTOS
Conjuntos Disjuntos
• Útiles para el procesamiento de conjuntos o
clases de equivalencia para responder
preguntas del tipo ¿es x equivalente a y?
• Se definen dos tipos de operaciones básicas:
unión y pertenencia
Conjuntos Disjuntos
• La estructura de datos a usar es un bosque
• La unión equivale a unir dos árboles
• La pertenencia equivale a conocer si dos
elementos se encuentran en el mismo árbol
Conjuntos Disjuntos
• En un comienzo cada árbol del bosque
contiene a un solo elemento. Se supone que al
comienzo cada elemento pertenece a un único
conjunto
• Haciendo operaciones de unión se forman
árboles más complejos
Conjuntos Disjuntos
{A} {B} {C} {D} {E} {F} {G}
Conjuntos Disjuntos
• unión(D,G) genera:
{A,D,G} {B} {C} {D} {E} {F}
Conjuntos Disjuntos
• unión(A,G) genera:
{A,D,G} {B} {C} {E} {F}
Conjuntos Disjuntos
• unión(B,F) genera:
{A,D,G} {B,F} {C} {E}
Conjuntos Disjuntos
• unión(E,F) genera:
{A,D,G} {B,F,E} {C}
Estructura de Datos
• Para el tipo de operaciones que soportan los
conjuntos disjuntos no es necesario tener
apuntadores a los hijos, sino a los padres
• ¿Cuándo dos elementos están en el mismo
conjunto?
Estructura de Datos
• Se puede usar un arreglo de índices del nodo
padre
• Este arreglo lo llamaremos padre
• Cuando padre[i]=0, significa que ese nodo
es la raíz del árbol
Estructura de Datos
1
i
2
3
4
5
6
7
1
2
3
4
5
6
7
padre[i] 0
0
0
0
0
0
0
Estructura de Datos
1
3
i
7
2
6
4
5
1
2
3
4
5
6
7
padre[i] 0
1
2
2
2
1
0
Unión pertenencia
• Unión-pertenencia: la operación de
pertenencia busca la raíz de los árboles en
donde están ambos elementos. Si la raíz
coincide retorna verdad. En caso contrario
falso. El parámetro unión indica si los
conjuntos deben unirse
Unión pertenencia
int pertenencia(int x, int y, int union)
{
int i=x, j=y;
while(padre[i]>0) i=padre[i];
while(padre[j]>0) j=padre[j];
if (union && (i!=j)) padre[j]=i;
return i!=j;
}
Unión pertenencia
• La implementación es muy sencilla, aunque su
comportamiento en el peor caso es muy malo.
¿cuál es la complejidad en el peor caso?
• La complejidad depende de la altura del árbol.
Para mantener la complejidad en lo mínimo la
idea es mantener siempre el árbol con altura
mínima
Unión pertenencia
1
1
2
6
2
3
3
4
5
7
4
5
7
6
Unión pertenencia
• Cuando se unen dos árboles, uno queda como
raíz, y el otro baja un nivel. Para minimizar la
altura del árbol, parece lógico que quede
como raíz el árbol con mayor cantidad de
descendientes
Unión pertenencia
• Con este fin se debe mantener siempre la
información sobre la cantidad de
descendientes de cada nodo raíz
• Para evitar el uso de otro arreglo, en lugar de
usar 0 para nodos raíces, se coloca un número
negativo cuyo valor absoluto es igual al
número de descendientes de este nodo
Unión pertenencia
1
2
5
6
4
3
7
i
1
padre[i] -3
2
3
4
5
6
7
1
5
5
-2
1
6
Compresión de caminos
• Otra idea consiste en que cada vez que se
hace una operación de unión pertenencia,
todos los nodos visitados se colocan como
hijos directos de la raíz del árbol respectivo
Compresión de caminos
1
2
5
6
4
7
8
10
3
9
union-pertenencia(7, 10)
Compresión de caminos
1
2
5
6
4
7
8
10
3
9
union-pertenencia(7, 10)
Compresión de caminos
1
2
5
6
4
7
8
10
3
9
union-pertenencia(7, 10)
Compresión de caminos
1
2
5
6
7
4
10
8
9
union-pertenencia(7, 10)
3
Compresión de caminos
int pertenencia(int x, int y, int union)
{
int i=x, j=y;
while(padre[i]>0) i=padre[i]; // buscar la raiz de este arbol
while(padre[j]>0) j=padre[j]; // y de este tambien
while(padre[x]>0) {t=x; x=padre[x]; padre[t]=i;}
while(padre[y]>0) {t=y; y=padre[y]; padre[t]=j;}
if (union && (i!=j))
{
if (padre[j] < padre[i])
{
padre[j]+=padre[i]-1; padre[i]=j;
} else
{
padre[i]+=padre[j]-1; padre[j]=I;
}
}
return i!=j;
}
Complejidad en tiempo
• No es fácil analizar la complejidad en tiempo
de la operación de unión-pertenencia
• Tarjan demostró que realizar una operación de
u-p se ejecuta en tiempo proporcional a
log*(n) – logaritmo iterado de n (¿cuántas
veces hay que aplicarle logaritmo a n para
llegar a 1?)
• Como log*(n) crece tan lentamente, en la
práctica se considera una operación de O(1)
TABLAS HASH
Tablas Hash
• Un método para hacer referencia
directamente a los registros en una tabla por
medio de transformaciones sobre la clave para
obtener direcciones en la tabla
• Si se sabe que las claves son enteros distintos
entre 0 y N-1, puede almacenarse la clave i en
la posición i-ésima
Tablas Hash
• La dispersión o hashing es una generalización
de este método en aplicaciones en donde no
se tiene ningún conocimiento concreto sobre
los valores de las claves
Tablas Hash
• Una búsqueda por dispersión
consiste de dos pasos:
• Evaluar la función de dispersión
• Resolver las colisiones
Funciones de dispersión
• Se necesita una función que transforme claves
(habitualmente enteros o cadenas cortas de
caracteres) en direcciones de la tabla en el
intervalo [0, M-1]
• M es el número de registros que se pueden
calcular en función a la memoria disponibe
Funciones de dispersión
Una función de dispersión debe:
• Ser fácil de calcular
• Ser una aproximación de una función
“aleatoria”, que para cada entrada toda salida
sea igualmente probable
Funciones de dispersión
• El primer paso consiste en transformar la clave
en un número entero para poder hacer
operaciones aritméticas sobre él
• Para claves pequeñas esto es trivial, usando la
representación binarias internas de los
caracteres
• Para representaciones mayores, extraer
algunos bits de la clave y empaquetarlos
Funciones de dispersión
• El segundo paso consiste en tomar éste
número y aplicarle alguna transformación
para llevarlo al intervalo [0,M-1]. La forma
más sencilla de realizar esto consiste en
seleccionar M primo y para cualquier clave k
aplicar la transformación h(k)=k mod M
Funciones de dispersión
• Supongamos por ejemplo la clave “CLAVE” y
M=101. Obteniendo la representación:
0001101100000011011000101
• Equivalente al número:
3540677 en base 10
• Luego, 3540677 mod 101 = 21, por lo que a la
palabra “CLAVE” le correspondería la posición
21 de la tabla
Funciones de dispersión
• Hay muchas claves posibles, y relativamente
pocas posiciones en la tabla, por lo que a
muchas claves le corresponden la misma
posición
• Si la clave es muy grande, por ejemplo
“CLAVEGRANDE” obtenemos un número no
representable en una palabra, por lo que hay
que buscar alternativas
Manejo de colisiones
• Encadenamiento separado: cada entrada de
la tabla contiene una lista con todos los
elementos que fueron mapeados a esa
entrada. Para buscar un elemento es
necesario recorrer toda la lista hasta
encontrarlo o determinar que no está
Manejo de colisiones
• Exploración lineal (M>N): si hay una colisión
se busca en la próxima entrada libre en la
tabla
• Cuando se está buscando un elemento, se
busca hasta encontrarlo, o hasta llegar a una
posición vacía de la tabla
• Al llegar a una posición vacía de la tabla,
significa que el elemento no está en la tabla
Funciones hash
Cuando se va a aplicar una función hash a un
string es necesario decidir cuales caracteres
tomar:
• Todos los caracteres
• Caracteres al final o en el medio
Métodos para strings
• Método de adición: sumar los valores de los
caracateres del string y al final aplicar el
módulo de ser necesario
unsigned char hash(char *str) {
unsigned char h = 0;
while (*str) h += *str++;
return h;
}
Métodos para strings
• Método del XOR: se aplican XORs exclusivos
sobre los caracteres del string y al final aplicar
el módulo de ser necesario
unsigned char hash(char *str) {
unsigned char h = 0;
while (*str) h ^= *str++;
return h;
}
Métodos para strings
• Método de la multiplicación: Cuando M=2N.
La clave es multiplicada por una constante y
luego se extraen los bits necesarios para
indexar la tabla. Knuth recomienda usar el
radio dorado para encontrar esta constante
(Radio dorado)
• Es la proporción ϕ tal que la suma de dos
números es al mayor de estos lo que el mayor
es al menor. Esto es, si a>b:
Métodos para strings
• Por ejemplo si la tabla tiene M=32 entradas, y
se utilizará una tabla de 8 bits para indexarlo,
el multiplicador será 28ϕ≈158
• Luego, dada cualquier clave K, lo primero que
se hace es mutiplicarla por 158. El resultado
tendrá 16 bits, y se toman los 5 bits mas
significativos del byte menos significativo
Métodos para strings
• Por ejemplo, para K=101, tenemos
158K=158*101=15958=(0011111001010110)2
• Los 5 bits mas significativos del byte menos
significativo son (01010) 2=10
• Luego, a la clave 101 le corresponde la
entrada 10 de la tabla
Métodos para strings
• Método aleatorio: Introduce una introducción
aleatoria para intentar dispersar mejor los datos:
unsigned char rand8[256];
unsigned char hash(char *str) {
unsigned char h = 0;
while (*str != NULL) h = rand8[h ^ *str++];
return h;
}
rand8 contiene los 256 caracteres barajados aleatoriamente
hashpjw
• P. J. Weinberger’s Compiler: función
implementada por Weinberger para usarla en
tablas de símbolo de compiladores, es todavía
sumamente usadada
hashpjw
#define M 211
int hashpjw(char *s)
{
char *p;
unsigned h=0, g;
for (p=s; *p!=0; p++)
{
h = (h << 4) + *p;
if (g=h & 0xf0000000)
{
h=h^(g>>24);
h=h^g;
}
}
return h % M;
}
Evaluación de tablas hash
• Para evaluar que tan buena es una tabla hash
en comparación a otra una idea es medir el
tamaño promedio de las listas en cada entrada
de la tabla
• Esto, no funciona, ya que puede observarse
que este promedio será siempre igual para el
mismo número de elementos
Evaluación de tablas hash
• Otra idea es medir el número total de accesos
necesarios para visitar todas las claves de la
tabla
• Suponiendo que el número de elementos en
la entrada i de la tabla es Bi, es fácil ver que
para acceder a todos los elementos de esa
entrada se necesitan:
Evaluación de tablas hash
• Luego, para visitar todos los elementos de la
tabla hash, se necesitarían:
BINARY INDEXED TREE O
FENWICK TREE
¿Qué son?
• Es una estructura de datos que provee
métodos eficientes para el cálculo y
manipulación de frecuencias y frecuencias
acumulativas
• Supongamos que tenemos un arreglo de n
posiciones y podemos sumarle uno a
cualquier posición del arreglo o conocer la
suma de los valores del arreglo entre dos
índices k,l
¿Qué son?
• Una primera aproximación al problema
permite realizar la operación de suma en O(1)
y la operación de consulta en O(n)
• Si realizamos m operaciones de consulta
tenemos O(n*m)
• Usando árboles de Fenwick la consulta es de
O(m log n)
Notación
• f[i]: frecuencia del elemento i. Por ejemplo, si
f[4]=7 significa que el 4 se repite 7 veces
• c[i]: frecuencia acumulada. c[i]=f[1]+…+f[i]
• MaxVal: Valor máximo que tendrá fecuencia
mayor a 0
• tree[i]: suma de frecuencias almacenadas en
el árbol
Notación
• tree[i] almacena la suma de frecuencias entre
i0 y i1 en donde:
• r es la posición del bit menos significativo
encendido de i. Por ejemplo, si i=12 (1100), r
será 2 (de derecha a izquierda el primer bit
está en la posición 0)
• i0 = i-2^r+1
• i1 = i
Notación
Luego, para tree[12] tenemos i0=9, i1=12
• tree[12] = f[9] + f[10] + f[11] + f[12]
Calcular:
• tree[6]
• tree[8]
• tree[3]
Ejemplo
18
10
2
4
1
5
1
1
1
3
2
3
1
2
1
0
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f
1
0
1
0
3
2
2
1
1
0
2
1
1
2
0
1
c
1
1
2
2
5
7
9
10
11 11
13
14
15
17
17
18
Ejemplo
• Para calcular por ejemplo c[14]:
c[14] = tree[14]+tree[12]+tree[8]
• Para calcular por ejemplo c[9]:
c[9] = tree[9]+tree[8]
Obtener el bit 1 menos significativo
• Sea ~x el complemento de un número
• Recordemos que cualquier número x puede
escribirse como a1b en donde b son todos bits
en 0
• Por ejemplo, para 101000:
– a = 10
– b = 000
Obtener el bit 1 menos significativo
• Luego, recordemos que –x = ~x + 1
~x + 1 = ~(a1b)+1 = ~(a)0~(b) + 1 =
~(a)0~(0...0)+1 = ~(a)01…1 + 1 = ~(a)10…0
= ~(a)1b
• Luego, el bit encendido menos significativo
puede calcularse con x & (-x)
Frecuencia acumulada
• Si deseamos calcular la frecuencia acumulada
en un índice i, primero debemos sumar tree[i].
• Luego si i tiene la forma a1b tenemos que
tree[i] almacena f[a0b+1]+…+f[i]
• Resta calcular f[1]+…+f[a0b]
• Es decir, ahora debemos calcular la frecuencia
acumulada en el índice i-(i&-i)
Frecuencia acumulada
int acum(int idx)
{
int sum = 0;
while (idx > 0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
Modificar el valor de una frecuencia
• Supongamos que se desea modificar la
frecuencia de f[i]
• Primero debemos modificar el valor en tree[i]
• Suponiendo que i=a1b
• Si hacemos a1b+1b obtenemos:
i’=(a+1)0b
• tree[i’]=f[(a+1)0b-2^r+1]+…+f[(a+1)0b]
• Por lo tanto tree[i’] también contiene a f[i]
Modificar el valor de una frecuencia
void update(int idx ,int val)
{
while (idx <= MaxVal)
{
tree[idx] += val;
idx += (idx & -idx);
}
}