Strutture di Dati Concetti Avanzati

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Programmazione Procedurale in Linguaggio C++

Strutture di Dati Concetti Avanzati

Rappresentazione Collegata – b

versione 2.1

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

2

Sommario

m

Uno Studio di Caso

ðL’Archivio di Figurine

m

Il Principio di Incapsulamento

m

Operazioni Notevoli

m

Libreria con Record e Puntatori

ðAnalisi delle Prestazioni e Varianti ðConfronto tra le Rappresentazioni

m

Limiti della Programmazione Procedurale

Strutture di Dati: Concetti Avanzati >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

Uno Studio di Caso

m

La gestione dell’archivio di figurine

ðscrivere un programma che gestisce in

memoria persistente un archivio di figurine dei calciatori per un’annata fissata

ðl’archivio deve essere mantenuto ordinato, per consentirne la stampa

ðdeve consentire di inserire tutte le figurine acquistate

ðed eliminare, eventualmente, i doppioni

Strutture di Dati: Concetti Avanzati >> Uno Studio di Caso

4

Uno Studio di Caso

m

Un’idea semplice

ðgestisco la collezione con una lista ordinata ðrappresentata inizialmente con array e

indicatore di riempimento

ðposso riutilizzare la libreria per le liste di numeri reali

m

Due problemi

ðl’inserimento ordinato ðl’eliminazione di duplicati

>> listaDiReali1.h

>> archivioFigurine1.cpp

(3)

Uno Studio di Caso

m

In questa lezione

ðvogliamo confrontare le rappresentazioni di una lista

m

Ma

ðprima dobbiamo porci un problema di riuso ðse esistono due (o più rappresentazioni) per

la lista, esisteranno due o più versioni per la relativa libreria

ðche rapporto c’è tra queste versioni ?

6

Uno Studio di Caso

m

In generale

ðla rappresentazione influenza

l’implementazione della libreria (il modo in cui sono realizzate le operazioni)

ðnon dovrebbe influenzare l’interfaccia (quali operazioni e come si utilizzano)

m

Di conseguenza

ðbisognerebbe progettare l’interfaccia in modo che sia comune alle varie implementazioni

(4)

Il Principio di Incapsulamento

m

Obiettivo

ðrendere dipendenti le applicazioni scritte sulla libreria esclusivamente dall’interfaccia ðe indipendenti dall’implementazione

ðin questo modo è possibile cambiare implementazione senza riscrivere le appl.

m

Il problema

ðprogettare correttamente l’interfaccia e le applicazioni

Strutture di Dati: Concetti Avanzati >> Il Principio di Incapsulamento

8

Il Principio di Incapsulamento

m

Un esempio di interfaccia mal progettata

ðlistaDiReali1.h

ðbasata su indicatore di riempimento ðl’interfaccia è mal progettata

m

Due problemi evidenti

ðrende visibili sottoprogrammi inopportuni (es:

leggiIndicatore)

ðper conoscere il numero di elementi, costringe ad utilizzare l’indicatore

(5)

Il Principio di Incapsulamento

m

Esempi di applicazione mal progett.

ðarchivioFigurine1.cpp

ðgestioneTemperature1.cpp

ðutilizzano l.indicatore ripetutamente

ðin effetti non c’è alternativa, vista la libreria ðil codice non è riutilizzabile su nessuna

implementazione che non preveda indicatore

>> listaDiReali1.h

>> gestioneTemperature1.cpp

10

Il Principio di Incapsulamento

m

Un esempio di interfaccia migliore

ðlistaDiReali2.h

m

Caratteristica

ðl’implementazione è sostanzialmente la stessa (basata su indicatore di riempimento) ðma cambia significativamente l’interfaccia, in

modo da non esporre dettagli inutili dell’implementazione

(6)

Il Principio di Incapsulamento

m

Le modifiche all’interfaccia

ðsparisce la proc. void leggiIndicatore() (che diventa una procedura interna e viene chiamata da void leggi())

ðnuova procedura void inizializza(lista& l) (precedentemente: l.indicatore = 0;)

ðnuova funzione int numeroElementi(lista l) (precedentemente l.indicatore)

12

Il Principio di Incapsulamento

m

Le modifiche all’interfaccia (cont.)

ðnuova funzione bool listaVuota(lista l)

(precedentemente l.indicatore == 0) ðnuova funzione bool listaPiena(lista l)

(precedentemente l.indicatore == MAXDIM) ðdefinizione typedef float tipoValori;

ðnuova funzione

tipoValori elementoInPosizione (int pos) (precedentemente l.valori[pos])

(7)

Il Principio di Incapsulamento

m

Esempi migliori di applicazioni

ðarchivioFigurine2.cpp

ðgestioneTemperature2.cpp

ðsono scritte rispettando la nuova interfaccia

m

Attenzione

ðtecnicamente è ancora possibile utilizzare per esempio l’indicatore (ma non viene fatto)

>> listaDiReali2.h

>> gestTemperature2.cpp

14

Il Principio di Incapsulamento

m

In effetti

ðla libreria è un esempio di “componente”

ðl’obiettivo è riutilizzarlo in più contesti ðpotendone cambiare all’occorrenza

l’implementazione

ðminimizzando l’accoppiamento con le appl.

m

E’ possibile enunciare, in questi casi

ðun principio di metodo sul modo di utilizzare i componenti

(8)

Il Principio di Incapsulamento

m

Principio di incapsulamento

ðè opportuno che l’implementazione di un componente sia quanto più possibile nascosta (“incapsulata”) al suo interno

ðil componente dovrebbe avere la più piccola interfaccia che ne consenta l’uso

ðsenza accoppiare il componente alle applicazioni scritte su di esso

16

Operazioni Notevoli

m

Archivio di Figurine

ðprima versione con array e indicatore di riempimento

m

Due operazioni interessanti

ðinserimento in posizione ordinata ðeliminazione dei duplicati

Strutture di Dati: Concetti Avanzati >> Operazioni Notevoli

(9)

Aggiunta in Posizione Ordinata

void aggiungiInOrdine(lista& l, int elem, bool& esito) { int posizione = cercaPosizioneOrdinata(l, elem);

aggiungi (l, elem, posizione, esito);

return;

}

int cercaPosizioneOrdinata(lista l, int elem) {

if (numeroElementi(l)==0 || (elem<elementoInPos(l, 0))) { return 0;

} else {

for (int i = 0; i < numeroElementi(l) - 1; i++) { if ((elem >= elementoInPosizione(l, i)) &&

(elem <= elementoInPosizione(l, i + 1))) { return i + 1;

} } }

return numeroElementi(l);

}

18

Eliminazione dei Duplicati

void eliminaDuplicati(lista& l) { int i = 0;

bool esito;

while (i < numeroElementi(l)) {

if (contaOccorrenze(l, elementoInPosizione(l, i)) > 1) { elimina (l, i, esito);

} else { i++;

} } return;

}

int contaOccorrenze(lista l, int elem) { int conta = 0;

for (int i = 0; i < numeroElementi(l); i++) { if (elementoInPosizione(l, i) == elem) {

conta++;

} }

return conta;

}

3 5 2 7

i = 0 i = 1

2

i = 2

3 5 7 2

i = 2 i = 3

(10)

Libreria con Record e Puntatori

m

Finora: libreria con array e indicatore

m

Il problema di questa soluzione

ðnon è possibile stabilire esattamente il numero massimo di figurine

ðscegliendo un numero molto grande c’è uno spreco notevole di memoria

ðrischio di esaurimento dello stack (“stack overflow”) nel caso di passaggio ripetuto per valore

Strutture di Dati: Concetti Avanzati >> Libreria con Record e Puntatori

20

Libreria con Record e Puntatori

m

Di conseguenza

ðè opportuno provare ad utilizzare una versione della libreria basata su puntatori

m

La prima versione della libreria

ðversione più semplice, già discussa ðtipo della lista = puntatore ad elemento

m

Lo sviluppo della libreria

ðfatto con test di regressione

>> listaPtr1.h

>> listaPtr1.cpp

>> listaPtrTest.cpp

(11)

Libreria con Record e Puntatori

m

La nuova versione dell’applicazione

ðarchivioFigurine2.cpp + listaPtr1.cpp

m

Vantaggi

ðrimosso il limite della dimensione massima ðevitati in parte gli sprechi di memoria

m

Infatti

ðla memoria necessaria per gli elementi è raddoppiata (valore + puntatore)

>> archivioFigurine2.cpp + listaPtr1.cpp

22

Libreria con Record e Puntatori

m Analizziamo le prestazioni

ðcerchiamo di stimare quanto sono efficienti le due implementazioni in termini di tempo

m Il metodo

ðnon calcoleremo i secondi (dipendono eccessivamente dal calcolatore)

ðviceversa, stimiamo il numero di operazioni dal processore per ciascun metodo

ðal variare della dimensione n della lista ðstima della “complessità computazionale”

(12)

Libreria con Record e Puntatori

m

Rappresentazione statica

ðaccesso ad un elemento: 1 accesso alla m.

(tempo indipendente dalla dimensione n) ðnumero di elementi: 1 accesso alla mem.

(tempo indipendente dalla dimensione n) ðoperazioni decisamente efficienti (rapide

anche su liste molto lunghe)

24

Libreria con Record e Puntatori

m Rappresentazione statica (continua)

ðinserimenti: complessità dipendente dalla posizione

m In coda

ðefficiente (numero costante di operazioni)

m In mezzo alla lista

ðcirca n/2 operazioni (spostamenti): per n grande è inefficiente

m In testa

ðcirca n operazioni (molto inefficiente)

(13)

Libreria con Record e Puntatori

m

Rappresentazione dinamica, I versione

ðaccesso ad un elemento: pos operazioni,

dove pos è la posizione (scansione)

ðnumero di elementi: n operazioni (scansione completa della lista)

ðentrambe le operazioni sono molto inefficienti

m

Attenzione

ðqueste operazioni sono molto utilizzate

26

Libreria con Record e Puntatori

m Rappresentazione dinamica, I versione

ðinserimenti

m In testa

ðmolto efficiente

m In mezzo

ðscansione (circa pos operazioni)

m In coda

ðscansione completa

m Similmente per le cancellazioni

(14)

Libreria con Record e Puntatori

m

In generale

ðquesta implementazione dinamica è estremamente inefficiente

m

Un possibile miglioramento immediato

ðaggiungere un ulteriore attributo intero per

tenere conto del numero di elementi

ðun esempio di rifattorizzazione del codice (“refactoring”)

ðmodifica per migliorarne la qualità

28

Libreria con Record e Puntatori

typedef float tipoValori;

struct elemento {

tipoValori valore;

elemento* next;

};

struct lista {

elemento* first;

int numeroElementi;

};

(15)

Libreria con Record e Puntatori

m

L’approccio corretto al refactoring

ðpartire da una versione verificata del codice ðper la quale sono stati sviluppati test di

regressione

ðeffettuare le modifiche progressivamente ðripetendo l’esecuzione dei test dopo ogni

modifica

ðin modo da intercettare immediatamente gli errori

>>> listaPtr2.h

>>> listaPtr2.cpp

30

Libreria con Record e Puntatori

m

Un ulteriore miglioramento (e refactoring)

ðaggiunta di un puntatore alla coda, per

migliorare l’efficienza delle operazioni in coda (inserimenti e cancellazioni)

m

Ovvero

struct lista {

elemento* first;

elemento* last;

int numeroElementi;

};

>>> listaPtr3.h

>>> listaPtr3.cpp

(16)

Libreria con Record e Puntatori

m

Riconsideriamo le prestazioni

ðnumero di elementi: efficiente

ðinserimenti/cancellazioni in testa: efficienti ðinserimenti/cancellazioni in coda: efficienti

m

Però

ðaccesso ad un elemento: richiede comunque la scansione

ðinserimenti e cancellazioni in mezzo alla lista: richiedono una scansione

32

Libreria con Record e Puntatori

m

Un’idea per migliorare queste operazioni

ðutilizzare una rappresentazione doppiamente

collegata

ðciascun elemento ha un puntatore al successivo ma anche al precedente ðin questo modo, avendo il puntatore alla

coda, la lista può essere attraversata in due direzioni diverse

(17)

Libreria con Record e Puntatori

typedef float tipoValori;

struct elemento { tipoValori valore;

elemento* next;

elemento* previous;

};

struct lista {

elemento* first;

elemento* last;

int numeroElementi;

};

3 -1 7 ^NULL

NULL

l.first l.last

34

Libreria con Record e Puntatori

m

Versione doppiamente collegata

ðun ulteriore refactoring

m

Vantaggio principale

ðin questo caso la scansione per ottenere il puntatore alla posizione x può essere fatta in entrambi i sensi

ðse x <= numeroElementi/2, in avanti ðse x > numeroElementi/2, indietro

>>> listaPtr4.h

>>> listaPtr4.cpp

(18)

Libreria con Record e Puntatori

elemento* puntatoreAllaPos (lista l, int pos) { elemento* p;

if (pos <= numeroElementi(l)/2) { p = l.first;

if (p != NULL) {

for (int i = 0; i < pos; i++) { p = p->next;

} } } else {

p = l.last;

if (p != NULL) {

for (int i = numeroElementi(l) - 1; i > pos; i--) { p = p->previous;

} } }

return p;

}

36

Libreria con Record e Puntatori

m

La versione finale dell’applicazione

ðnon cambia

m

Infatti

ðle quattro versioni della libreria implementano la stessa interfaccia

ðl’applicazione è scritta in modo da rispettare il principio di incapsulamento

(19)

Confronto tra le Rappresentazioni

m

In sintesi

ðdue principali rappresentazioni per una lista

m

Rappresentazione con memoria statica

ðbasata su array e indicatore di riempimento

m

Rappresentazione con memoria dinamica

ðrappresentazione collegata basata su record

e puntatori

Strutture di Dati: Concetti Avanzati >> Confronto

38

Confronto tra le Rappresentazioni

m

La differenza fondamentale

ðnella rappresentazione “statica” è necessario stabilire la dimensione massima della lista ðin tutti i casi in cui non è possibile prevedere

il numero di elementi della lista è inutilizzabile ðè necessario utilizzare la rappresentazione

“dinamica” basata sui puntatori

(20)

Confronto tra le Rappresentazioni

m

Utilizzo della memoria

ðnella rappresentazione statica c’è uno spreco inerente di memoria (all’array viene

assegnata la dimensione massima possibile) ðnella rappresentazione dinamica non c’è

spreco di memoria, ma la memoria

necessaria per ciascun elemento è doppia o addirittura tripla rispetto al caso precedente

40

Confronto tra le Rappresentazioni

m

Complessità computazionale

ðconfrontiamo la rappresentazione statica e quella dinamica doppiamente collegata

m

Rappresentazione statica

ðmolto efficiente l’accesso ad un elemento data la posizione, il calcolo della dimensione della lista, le operazioni in coda

ðinefficienti le operazioni in testa

ðinefficienti le operazioni in mezzo alla lista

(21)

Confronto tra le Rappresentazioni

m

Rappresentazione dinamica d.c.

ðmolto efficiente il calcolo del numero di elementi

ðmolto efficienti le operazioni in coda ðmolto efficienti le operazioni in testa ðper le operazioni in mezzo alla lista, e

l’accesso ad un elemento data la posizione la complessità dipende da n (la dimensione), ma è “ammortizzata” dalla doppia scansione

42

Confronto tra le Rappresentazioni

m

Scelta della rappresentazione ideale

ðsulla base di queste valutazioni

ðe delle esigenze specifiche dell’applicazione

m

Esempio

ðarchivio delle figurine

ðin questo caso l’operazione dominante è l’inserimento in posizione ordinata

(22)

Confronto tra le Rappresentazioni

m

Inserimento in posizione ordinata

ðscansione per cercare la posizione ðinserimento in posizione

m

Nella rappresentazione statica

ðcirca n operazioni

m

Nella rappresentazione dinamica

ðcomplessità molto più alta

ðla scansione della lista costa molto

44

Confronto tra le Rappresentazioni

m

Scansione della lista

ðaccesso all’elemento 0 (1 operazione) ðaccesso all’elemento 1 (2 operazioni) ðaccesso all’elemento 2 (3 operazioni) ð...

ðil numero totale cresce rapidamente

ðse n è la dimensione della lista, per scandire tutti gli elementi le operazioni sono

dell’ordine di (n² + 2n)/8

(23)

Confronto tra le Rappresentazioni

m

Di conseguenza

ðil problema principale della rappresentazione statica è la dimensione massima fissata

ðil problema principale della rappresentazione dinamica è il costo delle scansioni

m

Se questi due limiti fossero rimovibili

ðle due implementazioni sarebbero

approssimativamente equivalenti

46

Limiti della Programmazione Proced.

m

A questo punto

ðabbiamo visto una serie abbastanza ampia di tecniche delle programmazione procedurale ðpossiamo trarre alcune conclusioni sui limiti

di questo tipo di programmazione

m

Perché lo facciamo ?

ðper comprendere meglio alcune differenze con la programmazione a oggetti

Strutture di Dati: Concetti Avanzati >> Limiti della Programmazione Proced.

(24)

Limiti della Programmazione Proced.

m

I Problema: Incapsulamento

ðabbiamo visto che il principio di

incapsulamento è importante

ði punti del codice che possono variare

dovrebbero essere nascosti in modo da non influire sul resto

ðovvero: bisogna minimizzare l’accoppiamento tra i componenti dell’applicazione

48

Limiti della Programmazione Proced.

m

I Problema: Incapsulamento (cont.)

ðperò: non c’é un modo per imporlo nella

programmazione procedurale

ðes: anche correggendo l’interfaccia della libreria, il programma principale “vede” e può usare comunque l’indicatore di riempimento o il puntatore alla testa (sono contenuti nell’interfaccia)

ðil tutto è affidato alla disciplina del programmatore

(25)

Limiti della Programmazione Proced.

m

Cosa vorremmo avere (I)

ðun meccanismo per nascondere l’implementazione di un componente ðlasciando visibile solo la sua interfaccia ðovvero, la possibilità di dichiarare “private”

alcune parti di codice ðe “pubbliche” altre

50

Limiti della Programmazione Proced.

m

II Problema: Genericità

ðil codice delle librerie è poco riutilizzabile al cambiare del tipo degli elementi

ðlista di reali vs. lista di studenti

m

Cosa vorremmo avere (II)

ðuna sorta di “genericità”, per cui le librerie possono essere contenitori di vari tipi di elementi senza riscrivere il codice

(26)

Limiti della Programmazione Proced.

m

III Problema: Eccezioni

ðla gestione delle eccezioni che abbiamo studiato è insufficiente

ðconsente di gestire solo eccezioni nell’uso della memoria

ðnon consente di gestire molti altri tipi ðes: eccezioni nelle funzioni, eccezioni nei

sistemi esterni (es: file system)

52

Limiti della Programmazione Proced.

m

Cosa vorremmo avere (III)

ðuna funzionalità di comunicazione tra i moduli di un programma alternativa ai parametri

ðse tutto va bene, i moduli dovrebbero comunicare ordinariamente

ðse si verifica un’eccezione, questa dovrebbe essere esplicitamente “sollevata”,

comunicata e gestita

(27)

Limiti della Programmazione Proced.

m

IV Problema: Librerie di Sistema

ðla dotazione di librerie standard del

C/C++/FORTRAN è limitata

ðes: librerie per la programmazione grafica, librerie per l’accesso alla rete o a basi di dati ðogni compilatore utilizza librerie proprietarie ðcon il risultato di rendere il codice

pesantemente dipendente dalla piattaforma

54

Limiti della Programmazione Proced.

m

Cosa vorremmo avere (IV)

ðuna grossa collezione di librerie standard, implementate da tutti i compilatori

ðper la prog. grafica, l’accesso alla rete, le collezioni, l’accesso alle basi di dati ecc.

ðin modo che la piattaforma sia completa e standard

(28)

Limiti della Programmazione Proced.

m

Riassumendo

ðproblema di incapsulamento ðproblema di genericità

ðproblema di gestione delle eccezioni ðproblema delle librerie di sistema

m

La soluzione a questi problemi

ðle piattaforme moderne per la

programmazione a oggetti ðJava e .NET (>>)

56

Riassumendo

m

Uno Studio di Caso

ðL’Archivio di Figurine

m

Il Principio di Incapsulamento

m

Operazioni Notevoli

m

Libreria con Record e Puntatori

ðAnalisi delle Prestazioni e Varianti ðConfronto tra le Rappresentazioni

m

Limiti della Programmazione Procedurale

Strutture di Dati: Concetti Avanzati >> Sommario

(29)

Termini della Licenza

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Termini della Licenza

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.