Tavole dinamicheSpesso 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.

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.

Supporremo inoltre che sia possibile riservare e rilasciare memoria con le due operazioni:

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:

Push(p, x) 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.

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.

Espansione

Quando α = 1 la tavola è piena ed occorre espanderla allocando nuova memoria.

Una euristica comune è raddoppiare la memoria, il che garantisce un fattore di carico α > ½.

Table(T) T.size = 0 T.num = 0 T.table = nil

La definizione della funzione Table(T) che crea una tavola vuota è:

Essa richiede un tempo costante.

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

La definizione di Insert(x) è:

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 è:

altrimenti1

2 di potenza una è 1 se kkck

e il costo totale di n Insert è:

nnncnC nn

j

jn

kk 3122)( 1)1(log

)1(log

01

2

2

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.

Quindi, al momento dell’espansione, ogni elemento ha una unità di costo per pagarsi la ricopiatura.

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.

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 è: sizenum 2

Subito dopo la ricopiatura: 0

2

12 sizesize

Quando la tavola è piena:

sizesizesize 2

421

8

16

32

12 4 8 16 32 i

num

size

2 num-size

Il costo ammortizzato di un inserimento senza espansione è:

3

2)1(21

) 2() 2(1

ˆ

1111

11

1

kkkk

kkkk

kkkk

sizenumsizenum

sizenumsizenum

cc

3

2 2)1(21

) 2() 2(1

ˆ

11111

111

1

kkkkk

kkkkk

kkkk

numnumnumnumnum

sizenumsizenumnum

cc

con espansione ĉ1 = 2 (tavola vuota) e per k > 1

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.

Espansione e contrazione

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.

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

La definizione della funzione Delete(x) è:

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.

2/1 se2/

2/1 se 2

numsize

sizenum

Una funzione di questo tipo è

421

8

16

32

12 4 8 16 32 i

num size

48

Se α ≥ 1/2 il costo ammortizzato di un inserimento senza espansione è:

3

2)1(21

) 2() 2(1

ˆ

1111

11

1

kkkk

kkkk

kkkk

sizenumsizenum

sizenumsizenum

cc

3

2 2)1(21

) 2() 2(1

ˆ

11111

111

1

kkkkk

kkkkk

kkkk

numnumnumnumnum

sizenumsizenumnum

cc

con espansione; ĉ1 = 2 (tavola vuota) e per k > 1:

Se α < 1/2 non vi è sicuramente espansione e il costo ammortizzato di un inserimento è:

0

2/)1(2/1

)2/()2/(1

ˆ

1111

11

1

kkkk

kkkk

kkkk

numsizenumsize

numsizenumsize

cc

Se α ≤ 1/2 il costo ammortizzato di una rimozione senza contrazione è:

2

2/)1(2/1

)2/()2/(1

ˆ

1111

11

1

kkkk

kkkk

kkkk

numsizenumsize

numsizenumsize

cc

mentre con contrazione è:

2

2)1(1

)2/()2/(1

ˆ

11111

111

1

kkkkk

kkkkk

kkkk

numnumnumnumnum

numsizenumsizenum

cc

Se α > 1/2 non vi è sicuramente contrazione e il costo ammortizzato di una rimozione è:

1

2)1(21

) 2() 2(1

ˆ

1111

11

1

kkkk

kkkk

kkkk

sizenumsizenum

sizenumsizenum

cc

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|