1 Collezioni in Java Collezioni Insiemi

(1)

Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 13

Insiemi

Tecniche di rappresentazione, MFSet e analisi ammortizzata

Collezioni

2 π

7 3

2

∩

∅

=

Dunque i numeri non sono animali!

Collezioni in Java

(2)

La specifica degli insiemi

Tipi: Element, Set Operatori:

NewSet: void → Set IsEmptySet: Set → bool In: Element, Set → bool Insert: Element, Set → Set Delete: Element, Set → Set Union: Set, Set →Set Intersection: Set, Set →Set Difference: Set, Set →Set

La specifica degli insiemi

NewSet() = A′ Post: A′ = ∅

IsEmptySet(A) = b Post: b = true sse A = ∅ In(x, A) = b Post: b = true sse x∈ A Insert(x, A) = A′ Post: A′ = A ∪ {x}

Delete(x, A) = A′ Post: A′ = A − {x}

Union(A, B) = A′ Post: A′ = A ∪ B Intersection(A, B) Post: A′ = A ∩ B Difference(A, B) Post: A′ = A − B

Il vettore di booleani

: un vettore con are rappresent può

si allora finito è ed

se A⊆U U χ_A

U a a a a a a a a a a a a a a

A={ ₂, ₅, ₆, ₈}⊆{₁, ₂, ₃, ₄, ₅, ₆, ₇, ₈, ₉, ₁₀}= 0 1 0 0 1 1 0 1 0 0

1 2 3 4 5 6 7 8 9 10

χA





∉

= ∈

A x

A x x

A 0 se

se ) 1

χ ( χAè la funzione

caratteristica di A

Spazio O(N) dove N = |U|

(3)

Il vettore di booleani

Pro:è facile scrivere il codice degli operatori

Insert (x, A)

C[IndexOf(x)] ← 1 return C

Union (A, B) for i← 1 to N do

C[i] ← A[i] or B[i]

return C

Contro:gli operatori In, Insert, Delete

sono O(1) Ma:

NewSet, IsEmptySet, Union, Intersection, Difference

sono Θ(N) Ragionevole solo se N

è abbastanza piccolo

Liste ordinate

U a a a a

A={₂, ₅, ₆, ₈}⊆

U deve essere ordinato linearmente

a2 a5 a6 a7

A

Intersezione

Intersection (A, B)

if A = Nil or B = Nil then return Nil// ∅ ∩ B = A ∩ ∅ = ∅ else if Head(A) < Head(B) // x = Head(A) < min(B), dunque x∉ B

then return Intersection(Tail(A), B)

else if Head(A) > Head(B) // y = Head(B) < min(A), dunque y∉ A then return Intersection(A, Tail(B))

else// x = Head(A) = Head(B), A∩ B = {x} ∪ ( (A – {x}) ∩ (B – {x}) ) return Cons(Head(A), Intersection(Tail(A), Tail(B))

Intersection è Θ(n + m) dove n = |A|, m = |B|

(4)

Partizioni di un insieme

88 14

98 25

62 52

79 30

23 31

42

1 29

96 50

Def. Una partizione di un’insieme finito S è un sottoinsieme {S1, …, Sk}⊆℘(S) t.c.

S = S1∪ … ∪ Sk ,e se i≠ j allora Si∩ Sj= ∅ Def. Una partizione di un’insieme finito S è un sottoinsieme

{S1, …, Sk}⊆℘(S) t.c.

S = S1∪ … ∪ Sk ,e se i≠ j allora Si∩ Sj= ∅

Merge-Find-Set (MFSet)

Tipi: Element, Set, MFSet Operatori:

Create: Set → MFSet Find: Element, MFSet→ Element Union: Element, Element → MFSet Semantica:

Create (A) = M Post: M = {{x}: x∈ A}

Find (x, M) = y Pre: x∈ X per qualche X ∈ M Post: y∈ X ∈ M, y rappr. canonico di X Union (x, y, M) = M′ Pre: x∈ X , y ∈ Y per certi X, Y ∈ M

Post: M′ = M – {X, Y} ∪ {X ∪ Y}

Se M è stato prodotto con Create(S) e da successive Union, allora M è una partizione di S

Merge-Find-Set (MFSet)

Che cos’è un

“rappresentante canonico”? A che serve?

È un elemento privilegiato x∈ X con

cui possiamo identificare X

InTheSamePart? (a, b, M) // true sse esiste X∈ M t.c. {a, b} ⊆ X x← Find (a, M), y ← Find(b, M)

return x = y

(5)

MFSet con le liste

{ {a, b, c, d}, {e, f, g}}

a b c d

a∈ S1

e f g

e∈ S2

MFSet con le liste

a b c d

a∈ S₁

e f g

e∈ S₂

a b c d

a∈ S1∪ S2

e f g

Riassegnare i riferimenti alla testa costa O(n)

MFSet con la foreste

x

b r f

h

a w

}}

, , { }, , , ,

{{xbr f haw M=

x 1

b 1

w 6

f 1

a 6

h 6

r 1 1 2 3 4 5 6 7

Vettore dei padri label

parent

(6)

Unione

x

b r f

h

a w

x

b r f

h

a w

∪ =

Union (u, v, M)

// Pre: u, v rappr. canonici di el. di M i← Index(u), j ← Index(v) M[i].parent← j

Union è O(1)

Find

Find (u, M) i ← Index(u)

while M[i].parent≠ i do i← M[i].parent return M[i].label

È O(h) dove h è l’altezza del nodo u

x

b r f

h

a w

Unione per peso

x

b r f

h

a w

x

b r f

h

a w

∪ =

oppure

x

b r f

h

a w

3 nodi su livello 2

2 nodi su livello 2

(7)

Unione per peso

Nel fare l’unione, l’albero con minore cardinalità conviene divenga figlio della radice di quello di cardinalità maggiore Nel fare l’unione, l’albero con minore cardinalità conviene divenga figlio della radice di quello di cardinalità maggiore

weight(x) = card(T), rank(x) = height(T) dove T il sottoalbero con root(T) = x

Unione per peso

x y Link (x, y)

M[Index(x)].parent← Index(y) M[Index(y)].weight←

M[Index(y)].weight + M[Index(x)].weight

Union (x, y, M)

if M[Index(x)].weight≤ M[Index(y)].weight then Link(x, y)

else Link(y, x)

Link(x, y)

Nuova analisi di Find

Teorema. Se Union è implementata con l’euristica Unione-per- peso, allora per ogni x: 2^rank(x)≤ weight(x),

quindi se n = card(T) con root(T) = x, allora rank(x) ≤ log n, ossia Find èΘ(log n).

Per induzione sul numero m di volte che Union si applica a Create(S) per ottenere T:

m = 0: allora n = 1 e rank(x) = 0, dunque ) ( 1

2

2^rank⁽^x⁾= ⁰= =weight x

(8)

Nuova analisi di Find

m > 0: siano rank(x) e rank′(x) le altezze di T dopo m – 1 ed m applicazioni di Union risp. Analogamente weight(x) e weight′(x)

Ultima chiamata di Union: Union(x, y, M) produce Link(y,x) i.e. weight(y) ≤ weight(x).

Nuova analisi di Find

Caso rank(x) < rank(y): allora rank′(x) = rank(x) e

) (

) ( ) (

) ( 2

2 ⁽⁾ ⁽⁾

x t weigh

y weight x weight

x weight

x rank x k ran

= ′

+

<

≤

′ =

Nuova analisi di Find

Caso rank(x) ≥ rank(y): allora rank′(x) = rank(y) + 1 e

) (

regola la per ) ( ) (

ind.

ip.

) ( ) (

2 2 2

2 ⁽⁾ ⁽⁾¹ ⁽⁾ ⁽⁾

x t weigh

y weight x weight

y weight y weight

y rank y rank y rank x k ran

= ′

+

≤

+

≤

+

=

= ⁺

′

(9)

Unione per rango

x y Link (x, y)

M[Index(x)].parent← Index(y) if M[Index(x)].rank = M[Index(y)].rank

then M[Index(y)].rank← M[Index(x)].rank + 1

Union (x, y, M)

if M[Index(x)].rank≤ M[Index(y)].rank then Link(x, y)

else Link(y, x)

Link(x, y)

Compressione del cammino

Nel calcolare Find(x, M), rendiamo ogni vertice incontrato tra x e la radice di T, cui x appartiene, figlio della radice Nel calcolare Find(x, M), rendiamo ogni vertice incontrato tra

x e la radice di T, cui x appartiene, figlio della radice

a b

c d

a b c

d

Find(a, M)

Compressione del cammino

Nel calcolare Find(x, M), rendiamo ogni vertice incontrato tra x e la radice di T cui appartiene, figli della radice Nel calcolare Find(x, M), rendiamo ogni vertice incontrato tra

x e la radice di T cui appartiene, figli della radice

Find (x, M)

if M[Index(x)].parent≠ Index(x) then

M[Index(x)].parent ← Find(M[Index(x)].label, M) return M[Index(x)].parent

Il campo rank non viene ricalcolato:

perciò M[Index(x)].rank≥ rank(x)

(10)

Come valutare una struttura dati?

T(m) = la somma dei tempi di m operazioni nel caso peggiore Tempo ammortizzato

Tempo ammortizzato

m m T( )

È una media, ma non si fanno ipotesi probabilistiche

Il metodo dell’aggregato

ADT Stack con MultiPop:

Multipop (S, k)

while not IsEmptyStack(S) and k > 0 do Pop(S)

k← k – 1

Qual è l’O-grande di T(m)?

Il metodo dell’aggregato

Ti∈O(fi) tempo dell’operazione Opiallora

i f

O f n

f O m m

T( )≤ ⋅ ( ( )), dove i∈ ( )per ogni Quindi, visto che Push e Pop

sono O(1) ma MultiPop è O(n), otteniamo n⋅O(n) = O(n²) È giusto, ma non vi pare

un po’ esagerato?

(11)

Operazioni prepagate

Il potenziale

S MultiPop(S, 4)

∅

MultiPop(S, 5) Push(a, S), Push(b, S), Push(c, S) Push(d, S), Push(e, S), Push(e, S)

Ω(n) Push perché MultiPop sia Ω(n)

Ho fatto una stima un po’

pesante

Il potenziale

Il costo di alcune operazioni è bilanciato dal vantaggio, l’

“energia potenziale”, accumulato da altre

(12)

Il potenziale

ℜ

∈ Φ )(D

La funzione potenziale associa un numero reale ad ogni configurazione D dei dati:

tempo ammortizzato = tempo reale + ∆Φ ) ( ) (

|)

(| +Φ −Φ ₋₁

= _i _i _i _i

i T D D D

A

) ( ) (

|) (|

)

( ₀

1 1

D D D T A n

A ⁿ _n

i i i n

i

i= +Φ −Φ

=

∑ ∑

=

Il potenziale

Se ∆Φ ≥ 0 in ogni caso, allora

) (

|) (|

) (

1 1

n A A D T n

T ⁿ

i i

n

i i i ≤ =

=

∑ ∑

=

cioè non si va mai in rosso.

i i

i s S

S) numerodeglielementiin

( =

Φ

1 ) 1 ( ) ( ) ( )

Push( 1 ⇒Φ −Φ 1 = 1+ − 1=

= i− i i− i− i−

i x,S S S s s

S

) , min(

)) , min(

(

) ( ) ( ) Multipop(

1 1

k s s

S S ,k S S

i i

i i i

i

−

=

−

=

Φ

− Φ

⇒

=

0 ha

si ) , min(

postok′= si₋1 k Ai=Ti−∆Φ=k′−k′=

Il potenziale

) (

|) (|

) (

1 1

n A A D T n

T ⁿ

i i

n

i i i ≤ =

=

∑ ∑

=

i i

i s S

S) numerodeglielementiin

( =

Φ

1 ) 1 ( ) ( ) ( )

Push( 1 ⇒Φ −Φ 1 = 1+ − 1=

= _i₋ _i _i₋ _i₋ _i₋

i x,S S S s s

S

) , min(

)) , min(

(

) ( ) ( ) Multipop(

1 1

k s s

S S ,k S S

i i

i i i

i

−

=

−

=

Φ

− Φ

⇒

=

0 ha

si ) , min(

postok′= si₋1 k Ai=Ti−∆Φ=k′−k′= ) ( ) 1 ( 1

|) (|

) ( ) (

1

Push D nO On

T n n A n T

n i

i + ∈ ⋅ =

⋅

≤

∑

=

(13)

Analisi ammortizzata di MFSet

Se realizzati con liste: T(n) ∈ O(n²) e quindi T(n)/n∈ O(n) Se realizzati con foreste e con unione-per-rango e compressione dei cammini:

) ) (log ( quindi e ) log ( )

(n On ^*n Tn n O ^*n

T = ∈

} 1 log : 0 min{

log^*n= i≥ ⁽ⁱ⁾n≤

5 2 log

4 65536 log

65536

*

=

Se ne conclude che T(n)/n è O(1) per ogni n “ragionevole”