Tavole dinamiche
Spesso non si sa a priori quanta memoria serve per
memorizzare dei dati in un array, in una tavola
hash, in un heap, ecc.
Può capitare quindi di aver allocato una certa
quantità di memoria per poi accorgersi, durante
l’esecuzione del programma, che non ci basta.
In tal caso bisogna allocare una memoria maggiore,
ricopiare il contenuto della vecchia memoria nella
nuova e rilasciare la vecchia memoria.
E’ anche opportuno, dopo aver rimosso molti
elementi, ridurre la memoria allocando una
memoria più piccola in cui memorizzare gli
elementi rimasti.
Vedremo come sia possibile aggiungere e togliere
un elemento dalla tavola in tempo ammortizzato
costante O(1) benché tali operazioni abbiano costo
maggiore quando comportano espansione o
riduzione della memoria.
Vedremo anche che questo si può fare garantendo
che la memoria inutilizzata sia sempre inferiore ad
una frazione costante della memoria allocata.
Supporremo che una tavola T abbia i seguenti
attributi:
a) un puntatore T.table alla memoria allocata.
b) due campi interi T.num e T.size, rispettivamente
il numero di elementi presenti nella tavola e la
dimensione della tavola.
Supporremo inoltre che sia possibile riservare e
rilasciare memoria con le due operazioni:
Allocate(n) che riserva memoria per n elementi e
restituisce un puntatore a tale memoria.
Free(p, n) che rilascia la memoria di dimensione
n puntata da p.
Le operazioni da realizzare sono:
Table(T) che crea una nuova tavola vuota T.
Insert(T, x) che inserisce l’oggetto x nella tavola T.
Delete(T, x) che rimuove l’oggetto x dalla tavola T.
Non ci cureremo di come gli elementi siano
organizzati nella memoria allocata o di altri
dettagli implementativi ma ci limiteremo ad
assumere che siano definite le tre operazioni:
memorizza l’elemento x nella
memoria puntata da p.
Pop(p, x)
rimuove l’elemento x dalla memoria
puntata da p.
Copy(q, p, n) ricopia n elementi dalla memoria
puntata da p alla memoria puntata da q.
Push(p, x)
Espansione
Consideriamo dapprima il caso in cui vengono eseguite
soltanto inserzioni di nuovi elementi e nessuna rimozione.
Definiamo come fattore di carico della tavola il rapporto
α = num / size.
Quando α = 1 la tavola è piena ed occorre espanderla
allocando nuova memoria.
Una euristica comune è raddoppiare la memoria, il che
garantisce un fattore di carico α > ½.
La definizione della funzione Table(T) che crea
una tavola vuota è:
Table(T)
T.size = 0
T.num = 0
T.table = nil
Essa richiede un tempo costante.
La definizione di Insert(x) è:
Insert(T,x)
if T.size == 0
T.table = Allocate(1)
T.size = 1
if T.num == T.size
p = Allocate(2 T.size)
Copy(p, T.table, T.num)
Free(T.table, T.size)
T.table = p
T.size = 2 T.size
Push(T.table, x)
T.num = T.num + 1
Per l’analisi di Insert possiamo assumere che le
operazioni Allocate, Free e Push richiedano
tempo costante e che Copy richieda tempo
proporzionale al numero di elementi copiati.
Consideriamo il costo di una sequenza di n Insert
eseguite a partire da una tavola vuota.
Il costo della k-esima Insert è 1 se non vi è
espansione ed è k se vi è espansione:
k-1 per copiare i k-1 elementi precedenti più 1 per
le altre operazioni.
Siccome T.size è sempre una potenza di 2 e
l’espansione si ha quando T.num = k-1 è uguale a
T.size, il costo della k-esima Insert è:
 k se k  1 è una potenza di 2
ck  
1 altrimenti
e il costo totale di n Insert è:
n
log2 ( n 1) 
k 1
j 0
C ( n)   c k  n 
j
log2 ( n 1)  1
2

n

2
 1  3n

Insert ha quindi costo ammortizzato:
O(3n)/n = O(1)
Il metodo degli accantonamenti mostra perchè il
costo ammortizzato è 3.
1. una unità di costo viene spesa subito per
l’inserimento dell’elemento stesso.
2. una viene attribuita come credito all’elemento
stesso per pagare la sua successiva ricopiatura.
3. la terza viene attribuita come credito ad un altro
elemento ricopiato prima e rimasto privo di
credito.
Quindi, al momento dell’espansione, ogni elemento
ha una unità di costo per pagarsi la ricopiatura.
Possiamo anche usare il metodo del potenziale
scegliendo una funzione potenziale Φ che vale 0
all’inizio e subito dopo una ricopiatura e che cresce
fino alla dimensione della tavola tra una
espansione e la successiva.
Una tale funzione è:   2 num  size
Subito dopo la
ricopiatura:
1
  2 size  size  0
2
Quando la tavola è
piena:
  2 size  size  size
num
32
size

2 num-size
16
8
4
2
1
12 4
8
16
32
i
Il costo ammortizzato di un inserimento senza
espansione è:
cˆk  ck   k   k 1
 1  ( 2 num k  sizek )  ( 2 num k 1  sizek 1 )
 1  2( num k 1  1)  sizek 1  2 num k 1  sizek 1
3
con espansione ĉ1 = 2 (tavola vuota) e per k > 1
cˆk  ck   k   k 1
 1  num k 1  ( 2 num k  sizek )  ( 2 num k 1  sizek 1 )
 1  num k 1  2( num k 1  1)  2 num k 1  2 num k 1  num k 1
3
Espansione e contrazione
Delete(x) si realizza con una Pop(T.table, x) che
rimuove l’elemento x dalla tavola.
Ad evitare uno spreco eccessivo di memoria è
opportuno contrarre la tavola quando il fattore di
carico α = num / size diventa troppo piccolo.
Questo si fa allocando una memoria più piccola,
ricopiando i T.num elementi presenti nella tavola,
e rilasciando la vecchia memoria.
La strategia ovvia è dimezzare la memoria quando
il fattore di carico α diventa ≤ 1/2.
Questo ci assicura un fattore di carico α > 1/2
anche in presenza di Delete.
Purtroppo, con questa strategia il costo
ammortizzato delle operazioni non è più costante.
Consideriamo una successione costituita da 2k Insert
seguite da 2k-2 gruppi di quattro operazioni
Insert - Delete - Delete - Insert
per un totale di n = 2k+1 operazioni.
In ogni gruppo la prima Insert comporta una
espansione di costo 2k e la seconda Delete una
contrazione di costo 2k.
Quindi ogni gruppo ha costo ≥ 2k+1
e in totale i 2k-2 gruppi hanno costo:
≥ 2k-2 2k+1 = n2/8 = Ω(n2)
e il costo ammortizzato è Ω(n2)/n = Ω(n).
Il problema è che dopo una espansione (che porta
α ad 1/2 e consuma tutti i crediti) non si eseguono
rimozioni sufficienti ad accumulare crediti per la
successiva contrazione.
Occorre quindi aspettare che sia stata rimossa
almeno una metà degli elementi, ossia che α
diventi 1/4.
La definizione della funzione Delete(x) è:
Delete(T, x)
if T.num ≤ T.size / 4
p = Allocate(T.size / 2)
Copy(p, T.table, T.num)
Free(T.table, T.size)
T.table = p
T.size = T.size / 2
Pop(T.table, x)
T.num = T.num - 1
Usiamo il metodo del potenziale con una funzione
potenziale  che vale 0 sia all’inizio che subito
dopo una espansione o contrazione e che cresce
fino a raggiungere il numero di elementi presenti
nella tavola quando il fattore di carico α aumenta
fino ad 1 o diminuisce fino ad 1/4.
Una funzione di questo tipo è
 2 num  size se   1 / 2

 size / 2  num se   1 / 2
num
size

32
16
8
4
2
1
12 4
8
16
32
48
i
Se α ≥ 1/2 il costo ammortizzato di un
inserimento senza espansione è:
cˆ k  ck   k   k 1
 1  ( 2 num k  sizek )  ( 2 num k 1  sizek 1 )
 1  2( num k 1  1)  sizek 1  2 num k 1  sizek 1
3
con espansione; ĉ1 = 2 (tavola vuota) e per k > 1:
cˆ k  ck   k   k 1
 1  num k 1  ( 2 num k  size k )  ( 2 num k 1  sizek 1 )
 1  num k 1  2( num k 1  1)  2 num k 1  2 num k 1  num k 1
3
Se α < 1/2 non vi è sicuramente espansione e il
costo ammortizzato di un inserimento è:
cˆ k  ck   k   k 1
 1  ( sizek / 2  num k )  ( sizek 1 / 2  num k 1 )
 1  sizek 1 / 2  ( num k 1  1)  sizek 1 / 2  num k 1
0
Se α ≤ 1/2 il costo ammortizzato di una rimozione
senza contrazione è:
cˆ k  ck   k   k 1
 1  ( sizek / 2  num k )  ( sizek 1 / 2  num k 1 )
 1  sizek 1 / 2  ( num k 1  1)  sizek 1 / 2  num k 1
2
mentre con contrazione è:
cˆk  ck   k   k 1
 1  num k 1  ( sizek / 2  num k )  ( sizek 1 / 2  num k 1 )
 1  num k 1  num k 1  ( num k 1  1)  2 num k 1  num k 1
2
Se α > 1/2 non vi è sicuramente contrazione e il
costo ammortizzato di una rimozione è:
cˆ k  ck   k   k 1
 1  ( 2 num k  size k )  ( 2 num k 1  sizek 1 )
 1  2( num k 1  1)  size k 1  2 num k 1  size k 1
 1
Esercizio 16
Assumere che la contrazione della tavola
dinamica venga effettuata quando α = 1/3
invece che quando α = 1/4 e che invece di
ridurre la sua dimensione ad 1/2 size essa venga
ridotta a 2/3 size.
Calcolare il costo ammortizzato delle
operazioni usando la funzione potenziale:
 = |2 num - size|