Esercizio Calcolo Complessità Algoritmilia.deis.unibo.it/Courses/FondT2-0809-INF/lab/... ·...

Università di Bologna – A.A. 2008/2009

Fondamenti di Informatica T2

Modulo 2

Università degli Studi di Bologna

Facoltà di Ingegneria

Corso di Laurea in Ingegneria Informatica

Anno accademico 2008/2009

2

Esercizio Calcolo Complessità Algoritmi

2

• Si vuole realizzare un’applicazione grafica che

permetta all’utente di:

– selezionare un algoritmo di ordinamento fra quelli

messi a disposizione dall’applicazione


3


3

– misurare la complessità dell’algoritmo scelto sulla

base di un insieme di input, dove un input è

rappresentato da un array generico di valori

→l’utente deve indicare rispettivamente:

• la dimensione iniziale dell’array da ordinare;

• il numero di misure che vogliamo effettuare.

l’applicazione

dovrà effettuare

cinque misure,

con un insieme di

input generati in

modo casuale di

dimensione

crescente

(ESEMPIO: 1000,

2000, 3000, 4000,

e 5000),

4


4

→per l’algoritmo selezionato vengono effettuate diverse

misure, ciascuna relativa ad un input di dimensione

crescente e creato dall’applicazione in modo casuale

→ciascuna misura è rappresentata da diverse valutazioni

di complessità:

• numero di assegnamenti;

• numero di scambi;

• numero di confronti;

• tempo di esecuzione dell’algoritmo.


5


5

– visualizzare i risultati delle misure, relative

all’algoritmo scelto, attraverso due diversi tipi di vista:

• CHART VIEW

• TABLE VIEW

6


6

• CHART VIEW

visualizza per

ciascuna

misura i

risultati di ogni

valutazione

(es. numero di

scambi)


7


7

• TABLE VIEW visualizza

per ciascuna misura, i

risultati delle diverse

valutazioni

8

Realizzazione dell’Applicazione

8

• Prima il modello dei dati, compresi gli

algoritmi di ordinamento

• Poi l’interfaccia grafica

→Ancora pattern MVC con BaseGUI!!!


9

Cosa si misura

• Come anticipato, oltre al tempo d’esecuzione, si misurano il

numero di confronti, il numero di scambi, il numero di

assegnamenti

• Ogni operazione (confronto, scambio, assegnamento) è

astratta da un’interfaccia generica in modo che possa

essere “usata” dai vari algoritmi di ordinamento

9

class sortAlgorithms

«interface»

Assigner

+ assign(T[], T[], int, int) : void

«interface»

Switcher

+ flip(T[], int, int) : void

class util

«interface»

Comparator

+ compare(T, T) : int

È quella di sistema!

10

Algoritmi - SortAlgorithm• Il sistema di misurazione prevede l’utilizzo di diversi

algoritmi di ordinamento che devono essere

opportunamente modellati

• SortAlgorithm è una classe astratta che rappresenta

un generico algoritmo di ordinamento per un generico

array di valori

• Un algoritmo richiede:

• un oggetto per effettuare l’operazione di confronto

Comparator<T>

• un oggetto per effettuare l’operazione di scambio

Switcher<T>

• un oggetto per effettuare l’operazione di assegnamento

Assigner<T>


11

Algoritmi - SortAlgorithm

11

• Ha un metodo pubblico sort()che si occupa di

controllare l’esistenza degli oggetti “operatori” necessari

per l’operazione di confronto, scambio e assegnamento

• Solo se gli operatori esistono, richiama il metodo astrattointernalSort() che implementa (implementerà…)

l’algoritmo di ordinamento specifico della classe che estende SortAlgorithm


T

SortAlgorithm

+ getAssigner() : Assigner<T>

+ getComparator() : Comparator<T>

+ getName() : String

+ getSwitcher() : Switcher<T>

# internalSort(T[]) : void

+ setAssigner(Assigner<T>) : void

+ setComparator(Comparator<T>) : void

+ setSwitcher(Switcher<T>) : void

+ sort(T[]) : void

# SortAlgorithm(Comparator<T>, Switcher<T>, Assigner<T>, String)

+ SortAlgorithm()

12

SortAlgorithm - Codice

12

package sortAlgorithms;

public abstract class SortAlgorithm<T>

{

private Comparator<T> comparator;

private Switcher<T> switcher;

private Assigner<T> assigner;

private String name;

…

}


13


13

…

protected SortAlgorithm(Comparator<T> comparer,

Switcher<T> switcher, Assigner<T> assigner,

String name)

{

this.comparator = comparer;

this.switcher = switcher;

this.assigner = assigner;

this.name = name;

}

public SortAlgorithm()

{

}

…

14


14

…

public String getName()

{

return name;

}

public Comparator<T> getComparator()

{

return comparator;

}

public void setComparator(Comparator<T> comparer)

{

this.comparator = comparer;

}

…


15


15

…

public Switcher<T> getSwitcher()

{

return switcher;

}

public void setSwitcher(Switcher<T> switcher)

{

this.switcher = switcher;

}

…

16


16

…

public Assigner<T> getAssigner()

{

return assigner;

}

public void setAssigner(Assigner<T> assigner)

{

this.assigner = assigner;

}

…


17


17

…

public final void sort(T[] elements)

{

if (getComparator() == null ||

getSwitcher() == null ||

getAssigner() == null)

throw new IllegalStateException(

"getComparer() == null ||

getSwitcher() == null

|| getAssigner() == null");

internalSort(elements);

}

protected abstract void internalSort(T[] elements);

18

Algoritmi di Ordinamento

18

• Gli algoritmi da implementare sono

rispettivamente:

• Bubble Sort

• Merge Sort

• Naive Sort

• Quick Sort

• Ciascuno di questi algoritmi è stato presentato a

lezione in Fondamenti di Informatica T-1!


19

Algoritmi di Ordinamento

19


«interface»

Assigner


T

BubbleSort

+ BubbleSort(Comparator<T>, Switcher<T>, Assigner<T>)


T

MergeSort


+ MergeSort(Comparator<T>, Switcher<T>, Assigner<T>)

T:extends Comparable<T>

Naiv eSort

# internalSort(T[ ]) : void

+ NaiveSort(Comparator<T>, Switcher<T>, Assigner<T>)

T

QuickSort


+ QuickSort(Comparator<T>, Switcher<T>, Assigner<T>)

T

SortAlgorithm

+ getAssigner() : Assigner<T>

+ getComparator() : Comparator<T>

+ getName() : String

+ getSwitcher() : Switcher<T>


+ setAssigner(Assigner<T>) : void

+ setComparator(Comparator<T>) : void

+ setSwitcher(Switcher<T>) : void

+ sort(T[]) : void

+ SortAlgorithm(Comparator<T>, Switcher<T>, Assigner<T>, String)

+ SortAlgorithm()

«interface»

Switcher

+ fl ip(T[], int, int) : void

«interface»

util::Comparator


20

Bubble Sort - Codice

20


public class BubbleSort<T> extends SortAlgorithm<T>

{

public BubbleSort(Comparator<T> comparator,

Switcher<T> switcher, Assigner<T> assigner)

{

super(comparator, switcher, assigner,

"Bubble Sort");

}

public BubbleSort()

{

}

…

}


21

Bubble Sort - Codice

21

…

@Override

protected void internalSort(T[] elements)

{

boolean ordinato = false;

int n = elements.length;

while (n > 1 && !ordinato)

{

ordinato = true;

for (int i = 0; i < n - 1; i++)

if(getComparator().compare(elements[i],

elements[i + 1]) == 1)

{

getSwitcher().flip(elements, i, i + 1);

ordinato = false;

}

n--;}

}

22

Merge Sort - Codice

22


public class MergeSort<T> extends SortAlgorithm<T>

{

public MergeSort(Comparator<T> comparator,


{


”Merge Sort");

}

public MergeSort()

{

}

…

}


23

Merge Sort - Codice

23

…

@Override


{

T[] tmpElements = elements.clone();

Sort(elements, tmpElements, 0,

elements.length - 1);

}

…

24

Merge Sort - Codice

24

…

private void Sort(T[ ] elements, T[] tmpElements, int

left, int right)

{

if (left < right)

{

int center = (left + right) / 2;

Sort(elements, tmpElements,

left, center);

Sort(elements, tmpElements,

center + 1, right);

merge(elements, tmpElements,

left, center + 1, right);

}

}

…


25

Merge Sort - Codice

25

…

private void merge(T[ ] elements, T[] tmpElements,

int posLeft, int posRight,

int posEnd)

{

int endLeft = posRight - 1;

int posAux = posLeft;

int numElemen = posEnd - posLeft + 1;

…

}

…

26

Merge Sort - Codice

26

…

while (posLeft <= endLeft &&

posRight <= posEnd)

{

if(getComparator().compare(elements[posLeft],

elements[posRight]) < 0)

{

getAssigner().assign(elements,

tmpElements, posLeft, posAux);

posAux++;

posLeft++;

}

…


27

Merge Sort - Codice

27

…

else

{


tmpElements, posRight, posAux);

posAux++;

posRight++;

}

}

while (posLeft <= endLeft)

{


tmpElements, posLeft, posAux);

posAux++;

posLeft++;

}

…

28

Merge Sort - Codice

28

…

while (posRight <= posEnd)

{


tmpElements, posRight, posAux);

posAux++;

posRight++;

}

for (int i = 0;i < numElemen; i++, posEnd--)

getAssigner().assign(tmpElements,

elements, posEnd, posEnd);

}


29

Quick Sort - Codice

29


public class QuickSort<T> extends SortAlgorithm<T>

{

public QuickSort(Comparator<T> comparator,


{


"Quick Sort");

}

public QuickSort()

{

}

…

}

30

Quick Sort - Codice

30

…

@Override


{

Sort(elements, 0, elements.length - 1);

}

private void Sort(T[ ] elements, int left, int right)

{

int index = partition(elements, left, right);

if(left < index - 1)

Sort(elements, left, index - 1);

if(left < right)

Sort(elements, index, right);

}

…


31

Quick Sort - Codice

31

…

private int partition(T[ ] elements, int left,

int right)

{

int i = left;

int j = right;

T pivot = elements[(left + right) / 2];

while(i <= j)

{

while (getComparator().

compare(elements[i], pivot) < 0)

i++;

while (getComparator().

compare(elements[j], pivot) > 0)

j--;

…

32

Quick Sort - Codice

32

…

if (i <= j)

{

getSwitcher().flip(elements,

i, j);

i++;

j--;

}

}

return i;

}


33

Naive Sort - Codice

33


public class NaiveSort<T extends Comparable<T>> extends

SortAlgorithm<T>

{

public NaiveSort(Comparator<T> comparator,


{


"Naive Sort");

}

public NaiveSort()

{

}

…

}

34

Naive Sort - Codice

34

…

@Override

protected void internalSort(T[ ] elements)

{

int n = elements.length;

while (n > 1)

{

int p = getMaxPosition(elements, n);

if (p < n-1)

{

getSwitcher().flip(elements,

p, n - 1);

}

n--;

}

}

…


35

Naive Sort - Codice

35

…

private int getMaxPosition(T[ ] elements, int n)

{

int posMax = 0;

for (int i = 0; i < n - 1; i++)

if (getComparator().compare(elements[posMax],

elements[i]) < 0)

posMax = i;

return posMax;

}

36

Operazioni Misurabili• Poiché occorre fare misurazioni (conteggi) sulle operazioni (confronto,

scambio, assegnamento), occorre prevedere una classe astratta da cui

derivare tutte le operazioni in modo da dotare le implementazioni dei

servizi necessari all’esecuzione delle misure

• Tale classe, denominata OperationWithMeasure, è dotata di metodi

per incrementare il conteggio delle operazioni effettuate (la misura),

resettare la misura (nuova misura), ottenere il valore della misura.

36

class measurementSystem

OperationWithMeasure

+ getMeasure() : int

# incMeasure() : void

+ newMeasure() : void

# OperationWithMeasure()


37

Operazioni Misurabili

37


T

ComparatorWrapper

+ ComparatorWrapper(Comparator<T>)


T

DefaultAssigner


+ DefaultAssigner()


DefaultComparator


T

DefaultSwitcher

+ DefaultSwitcher()







«interface»

sortAlgorithms::

Switcher


«interface»

sortAlgorithms::Assigner


«interface»

util::Comparator


38

OperationWithMeasure -Codice

38

package measurementSystem;

public abstract class OperationWithMeasure

{

private int nOperations;

public OperationWithMeasure()

{

nOperations = 0;

}

public int getMeasure()

{

return nOperations;

}

…

}


39

OperationWithMeasure -Codice

39

…

public void newMeasure()

{

nOperations = 0;

}

protected void incMeasure()

{

nOperations++;

}

}

40

DefaultComparator

40

• Rappresenta una possibile implementazione di Comparator<T>

• Confronta due oggetti di tipo Comparable

→Per l’implementazione di compare(), sfrutta il metodo

compareTo() class measurementSystem

Comparator


DefaultComparator



- nOperations: int






41

DefaultComparator - Codice

41


public class DefaultComparator<T extends Comparable<T>>

extends OperationWithMeasure implements Comparator<T>

{

@Override

public int compare(T o1, T o2)

{

incMeasure();

return o1.compareTo(o2);

}

}

42

ComparatorWrapper

42

• Rappresenta una soluzione più

generica

• Incapsula un oggetto Comparator passato come

parametro al costruttore,

aggiungendo le funzionalità

richieste per la misurazione della

complessità (vedi in seguito)

• Il metodo compare() richiama il

metodo compare() dell’oggetto

incapsulato


Comparator


- nOperations: int





T

ComparatorWrapper

- innerComparator: Comparator<T>

+ ComparatorWrapper(Comparator<T>)


1


43

ComparatorWrapper - Codice

43


public class ComparatorWrapper<T> extends

OperationWithMeasure implements Comparator<T>

{

private Comparator<T> innerComparator;

public ComparatorWrapper(Comparator<T> comparator)

{

innerComparator = comparator;

}

@Override

public int compare(T arg0, T arg1)

{

incMeasure();

return innerComparator.compare(arg0, arg1);

}

}

44

DefaultAssigner

44

• Rappresenta una possibile implementazione di Assigner

• Assegna l’elemento di posizione source del primo array

all’elemento di posizione target del secondo array



- nOperations: int





«interface»

sortAlgorithms::Assigner


T

DefaultAssigner


+ DefaultAssigner()


45

Assigner - Codice

45


public interface Assigner<T>

{

public void assign(T[] elementSource, T[]

elementTarget, int source, int target);

}

46

DefaultAssigner - Codice

46


public class DefaultAssigner<T> extends OperationWithMeasure

implements Assigner<T>

{

public DefaultAssigner()

{

super();

}

public void assign(T[] elementSource, T[]

elementTarget, int source, int target)

{

super.incMeasure();

elementTarget[target] = elementSource[source];

}

}


47

DefaultSwitcher

47

• Rappresenta una possibile implementazione di Switcher

• Scambia l’elemento di posizione source con l’elemento

di posizione target nell’array passato come parametro



- nOperations: int





T

DefaultSwitcher

+ DefaultSwitcher()


«interface»

sortAlgorithms::

Switcher


48

Switcher - Codice

48


public interface Switcher<T>

{

public void flip(T[] elements, int source,

int target);

}


49

DefaultSwitcher - Codice

49


public class DefaultSwitcher<T> extends OperationWithMeasure

implements Switcher<T>

{

public DefaultSwitcher()

{

super();

}

public void flip(T[] elements, int source,

int target)

{

super.incMeasure();

T tmp = elements[source];

elements[source] = elements[target];

elements[target] = tmp;

}

}

50

Operazioni Misurabili

50

• Per poter conteggiare le operazioni effettuate occorre che

ad ogni operazione sia invocato il metodo incMeasure()

→ incMeasure() deve essere richiamata da ciascuna operazione:

Switcher.flip(), Assigner.assign(),

Comparer.compare()








51

I generici…

• Così generico (tramite l’uso dei generici) è molto bello… se

si volesse mantenere tutto generico occorrerebbe che

anche il Controller e, di conseguenza, le viste fossero

generici

• Però, chi mai andrà a cambiare il controller e le viste per

ordinare delle stringhe piuttosto che degli interi?

• E, soprattutto, il cambio di tipo incide sulle misure?

• Controller e viste saranno cablate sull’utilizzo degli interi!

51

52

Controller

52

• Il Controller dell’applicazione, MeasureController, è

responsabile:

– della creazione della view principale,

– dell’esecuzione delle misure sull’algoritmo selezionato dall’utente,

– della visualizzazione delle misure sulla view secondaria

selezionata dall’utente

class controllers

MeasureController

+ executeAlgorithm(String, int, int, String) : void

+ getAlgorithmFactory() : AlgorithmFactory<Integer>

+ getAvailableAlgorithms() : Set<String>

+ getModel() : List<Measure>

+ getViewFactory() : ViewFactory

+ MeasureController(List<Measure>, AlgorithmFactory<Integer>, ViewFactory)

+ start() : void


53

Controller

53

• È responsabile della creazione della view principale:

– per garantire il disaccoppiamento fra view e controller, il controller crea le view tramite la factory ViewFactory (v. dopo)

– il controller ha la responsabilità di informare la view principale

degli algoritmi messi a disposizione dall’applicazione (getAvailableAlgorithms())

– il controller ottiene i nomi degli algoritmi disponibili tramite la factory AlgorithmFactory

54

Controller

54

• È responsabile dell’esecuzione delle misure sull’algoritmo

selezionato dall’utente; riceve dalla view principale:

– il nome dell’algoritmo selezionato dall’utente,

– la dimensione di partenza dell’input ed il numero di misure da

effettuare,

– il tipo della view secondaria in cui visualizzare i risultati delle

misure effettuate


55

Controller

55

• È responsabile dell’esecuzione delle misure sull’algoritmo selezionato dall’utente; sfrutta AlgorithmFactory per:

– ottenere un’implementazione dell’algoritmo desiderato

– ottenere gli array da ordinare, ovvero l’input relativo a ciascuna

misura per l’algoritmo selezionato

• È responsabile della visualizzazione delle misure sulla

view secondaria selezionata dall’utente

– crea la view secondaria selezionata dall’utente tramite la ViewFactory passandogli le misure da visualizzare

56

Controller

56

• È responsabile della visualizzazione delle misure sulla

view secondaria selezionata dall’utente

– crea la view secondaria selezionata dall’utente tramite la ViewFactory passandogli le misure da visualizzare


57

Controller - Codice

57

package controllers;

public class MeasureController

{

private List<Measure> model;

private AlgorithmFactory<Integer> algorithmFactory;

private ViewFactory viewFactory;

public MeasureController(List<Measure> model,

AlgorithmFactory<Integer> algorithmFactory,

ViewFactory viewFactory)

{

this.model = model;

this.algorithmFactory = algorithmFactory;

this.viewFactory = viewFactory;

}

…

}

58

Controller - Codice

58

…

public List<Measure> getModel()

{

return model;

}

public AlgorithmFactory<Integer>

getAlgorithmFactory()

{

return algorithmFactory;

}

public ViewFactory getViewFactory()

{

return viewFactory;

}

…


59

Controller - Codice

59

…

public void start()

{

// Crea e mostra la view principale

MeasureView view =

viewFactory.createMeasureView(this);

view.showView();

}

public Set<String> getAvailableAlgorithms()

{

return algorithmFactory.

getAvailableAlgorithms();

}

…

60

Controller - Codice

60

…

public void executeAlgorithm(String name, int

minMeasureValue, int measureNumber, String

selectedView)

{

SortAlgorithm<Integer> algorithm =

getAlgorithmFactory().

getAlgorithm(name);

if (algorithm == null)

throw new IllegalArgumentException();

model = new ArrayList<Measure>();

…


61

Controller - Codice

61

…

for(int i = 1; i <= measureNumber; i++)

{

newMeasure(algorithm);

int arrayDimension = minMeasureValue * i;

Integer[] algorithmArray =

algorithmFactory.

getArrayToSort(arrayDimension);

long startTime =

System.currentTimeMillis();

algorithm.sort(algorithmArray);

long endTime =

System.currentTimeMillis();

…

62

Controller - Codice

62

…

model.add(new Measure(arrayDimension,

getNAssignes(algorithm),

getNFlips(algorithm),

getNComparisons(algorithm),

endTime - startTime));

}

createResultView(selectedView, algorithm);

}

…


63

Controller - Codice

63

…

private void createResultView(String type,

SortAlgorithm<Integer> algorithm)

{

if(type.equals("chart"))

{

viewFactory.createChartView(model,

algorithm.getName()).showView();

}

else

{

viewFactory.createTableView(model,

algorithm.getName()).showView();

}

}

…

64

Controller - Codice

64

…

private void newMeasure(SortAlgorithm<Integer>

algorithm)

{

((OperationWithMeasure)

algorithm.getComparator()).newMeasure();


algorithm.getSwitcher()).newMeasure();


algorithm.getAssigner()).newMeasure();

}

…


65

Controller - Codice

65

…

private int getNComparisons(SortAlgorithm<Integer>

algorithm)

{

return ((OperationWithMeasure)

algorithm.getComparator()).getMeasure();

}

private int getNFlips(SortAlgorithm<Integer>

algorithm)

{


algorithm.getSwitcher()).getMeasure();

}

private int getNAssignes(SortAlgorithm<Integer>

algorithm)

{


algorithm.getAssigner()).getMeasure();

}

66

AlgorithmFactory• AlgorithmFactory<T> è

un’interfaccia generica che astrae

le operazioni che seguono:

– Ottenere i nomi degli algoritmi di

ordinamento supportati

– Ottenere un’istanza di un algoritmo di

ordinamento dato un nome

– Ottenere un array da ordinare (del

tipo giusto…)

• È implementata da IntegerAlgorithmFactory

che la specializza per lavorare solo sugli Integer

66

class controllers

IntegerAlgorithmFactory

+ getAlgorithm(String) : SortAlgorithm<Integer>

+ getArrayToSort(int) : Integer[]


+ IntegerAlgorithmFactory()

«interface»

measurementSystem::AlgorithmFactory

+ getAlgorithm(String) : SortAlgorithm<T>

+ getArrayToSort(int) : T[]



67

AlgorithmFactory - Codice


public interface AlgorithmFactory<T>

{

public Set<String> getAvailableAlgorithms();

public SortAlgorithm<T> getAlgorithm(String name);

T[] getArrayToSort(int arrayDimension);

}

67

68

IntegerAlgorithmFactory - Codice

68

package controllers;

public class IntegerAlgorithmFactory implements

AlgorithmFactory<Integer>

{

private Map<String, SortAlgorithm<Integer>> algorithmMap

= new HashMap<String, SortAlgorithm<Integer>>();

private static Random intGenerator = new Random();

…

}


69


69

…

public IntegerAlgorithmFactory()

{

algorithmMap.put("Bubble Sort",

new BubbleSort<Integer>());

algorithmMap.put("Merge Sort",

new MergeSort<Integer>());

algorithmMap.put("Quick Sort",

new QuickSort<Integer>());

algorithmMap.put("Naive Sort",

new NaiveSort<Integer>());

}

70


70

…

@Override

public SortAlgorithm<Integer> getAlgorithm(

String name)

{

SortAlgorithm<Integer> algorithm =

algorithmMap.get(name);

if (algorithm != null)

{

algorithm.setComparator(

new DefaultComparator<Integer>());

algorithm.setAssigner(

new DefaultAssigner<Integer>());

algorithm.setSwitcher(

new DefaultSwitcher<Integer>());

}

return algorithm;

}…


71


71

…

@Override

public Integer[] getArrayToSort(int arrayDimension)

{

Integer[] algorithmArray =

new Integer[arrayDimension];

for(int i = 0; i < arrayDimension; i++)

algorithmArray[i] =

intGenerator.nextInt();

return algorithmArray;

}

@Override

public Set<String> getAvailableAlgorithms()

{

return algorithmMap.keySet();

}

72

ViewFactory• ViewFactory è l’interfaccia che astrae la creazione delle

viste

• È utilizzata dal controller per essere indipendente

dall’implementazione delle viste stesse

• Naturalmente, è necessario che le viste, a loro volta, siano

astratte da interfacce

72

class impl

DefaultViewFactory

+ createChartView(List<Measure>, String) : ChartView

+ createMeasureView(MeasureController) : MeasureView

+ createTableView(List<Measure>, String) : TableView

«interface»

v iews::ViewFactory

+ createChartView(List<Measure>, String) : ChartView

+ createMeasureView(MeasureController) : MeasureView

+ createTableView(List<Measure>, String) : TableView


73

ViewFactory - Codicepackage views;

public interface ViewFactory

{

public MeasureView createMeasureView(MeasureController

controller);

public TableView createTableView(List<Measure> measures,

String algorithmName);

public ChartView createChartView(List<Measure> measures,

String algorithmName);

}

73

74

DefaultViewFactory - Codicepackage views.impl;

public class DefaultViewFactory implements ViewFactory

{

@Override

public MeasureView createMeasureView(

MeasureController controller)

{

return new DefaultMeasureView(controller);

}

@Override

public ChartView createChartView(List<Measure> measures,

String algorithmName)

{

return new DefaultChartView(measures,algorithmName);

}

…

} 74


75

DefaultViewFactory - Codice

…

@Override

public TableView createTableView(List<Measure> measures,


{

return new DefaultTableView(measures,algorithmName);

}

75

76

Model

76

• Il model dell’applicazione è rappresentato da un insieme

di misure di complessità

• La misura è rappresentata rispettivamente da:

• dimensione dell’input per l’algoritmo

• valori relativi a ciascuna valutazione (confronto, assegnamento, scambio, e tempo di esecuzione)

class model

Measure

+ getArrayDimension() : int

+ getAssignes() : int

+ getComparisions() : int

+ getFlips() : int

+ getTime() : long

+ Measure(int, int, int, int, long)


77

Model - Codice

77

package model;

public class Measure

{

private int arrayDimension;

private int assignes;

private int flips;

private int comparisons;

private long time;

public Measure(int arrayDimension, int assignes, int

flips, int comparisons, long time)

{

this.arrayDimension = arrayDimension;

this.assignes = assignes;

this.flips = flips;

this.comparisons = comparisons;

this.time = time;

}

…

}

78

Model - Codice

78

…

public int getArrayDimension()

{

return arrayDimension;

}

public int getAssignes()

{

return assignes;

}

public int getFlips()

{

return flips;

}

…


79

Model - Codice

79

…

public int getComparisons()

{

return comparisons;

}

public long getTime()

{

return time;

}

80

View - DefaultMeasureView

80

• View principale ( ha un riferimento al controller)

• Implementa l’interfaccia MeasureView (pattern Factory)

che definisce il metodo showView()

• Estende JFrame

BorderLayout

FlowLayout BoxLayout

class impl

JFrame

ActionListener

DefaultMeasureView

+ actionPerformed(ActionEvent) : void

+ AlgorithmMeasure(String) : void

+ DefaultMeasureView(MeasureController)

# initGUI() : void

+ showView() : void

«interface»

v iews::MeasureView

+ showView() : void


81

MeasureView - Codice

81

package views;

public interface MeasureView

{

void showView();

}

82

DefaultMeasureView - Codice

package views.impl;

public class DefaultMeasureView extends JFrame implements

ActionListener, MeasureView

{

private JLabel minMeasureValueLabel;

private JLabel measureNumberLabel;

private JTextField minMeasureValue;

private JTextField measureNumber;

private MeasureController controller;

private Set<String> availableAlgorithm;

private JRadioButton tableViewRadioButton;

private JRadioButton chartViewRadioButton;

…

}


83


…

public DefaultMeasureView(MeasureController controller)

{

this.controller = controller;

initGUI();

}

public void showView()

{

setVisible(true);

}

…

84

DefaultMeasureView - Codice…

protected void initGUI()

{

setTitle("Complexity Measurer of Sorting Algorithms");

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

JPanel mainPanel = new JPanel();

mainPanel.setLayout(new BorderLayout());

JPanel settingPanel = new JPanel();

{

GridLayout layout = new GridLayout();

layout.setColumns(1);

layout.setRows(3);

settingPanel.setLayout(layout);

…


85


JPanel minMeasureValuePanel = new JPanel();

{

minMeasureValuePanel.setLayout(

new FlowLayout());

minMeasureValueLabel = new JLabel();

Font labelFont =

new Font(null, Font.BOLD, 12);

minMeasureValueLabel.setFont(labelFont);

minMeasureValueLabel.

setForeground(Color.BLUE);

minMeasureValueLabel.setText(

"Min Number of Values to Order: ");

minMeasureValue = new JTextField();

minMeasureValue.setPreferredSize(

new Dimension(80, 40));

…

86


minMeasureValuePanel.add(minMeasureValueLabel);

minMeasureValuePanel.add(minMeasureValue);

settingPanel.add(minMeasureValuePanel);

}

JPanel measureNumberPanel = new JPanel();

{

measureNumberPanel.setLayout(new FlowLayout());

measureNumberLabel = new JLabel();

Font labelFont = new Font(null, Font.BOLD, 12);

measureNumberLabel.setFont(labelFont);

measureNumberLabel.setForeground(Color.BLUE);

measureNumberLabel.setText(

"Number of Measures: ");

…


87


measureNumber = new JTextField();

measureNumber.setPreferredSize(

new Dimension(80, 40));

measureNumberPanel.add(measureNumberLabel);

measureNumberPanel.add(measureNumber);

settingPanel.add(measureNumberPanel);

}

88


JPanel measurePanel = new JPanel();

{

measurePanel.setLayout(new FlowLayout());

ButtonGroup group = new ButtonGroup();

Font radioButton =

new Font(null, Font.BOLD, 12);

chartViewRadioButton =

new JRadioButton("CHART VIEW");

chartViewRadioButton.setFont(radioButton);

group.add(chartViewRadioButton);

chartViewRadioButton.setSelected(true);

tableViewRadioButton =

new JRadioButton("TABLE VIEW");

tableViewRadioButton.setFont(radioButton);

group.add(tableViewRadioButton);

…


89


measurePanel.add(chartViewRadioButton);

measurePanel.add(tableViewRadioButton);

}

settingPanel.add(measurePanel);

}

mainPanel.add(settingPanel, BorderLayout.WEST);

JPanel algorithmSelectionPanel = new JPanel();

{

algorithmSelectionPanel.

setAlignmentY(Component.CENTER_ALIGNMENT);

algorithmSelectionPanel.setLayout(

new BoxLayout(algorithmSelectionPanel,

BoxLayout.Y_AXIS));

availableAlgorithm =

controller.getAvailableAlgorithms();

…

90


Font buttonFont = new Font(null, Font.BOLD, 12);

JButton button = null;

for(String algorithm : availableAlgorithm)

{

button = new JButton(algorithm);

button.setFont(buttonFont);

button.addActionListener(this);

algorithmSelectionPanel.add(button);

}

}

mainPanel.add(algorithmSelectionPanel,

BorderLayout.EAST);

add(mainPanel);

pack();

setLocationRelativeTo(this);

}


91


…

@Override

public void actionPerformed(ActionEvent evt)

{

if(evt.getSource() instanceof JButton)

{

JButton button = (JButton) evt.getSource();

if(measureNumber.getText().trim().equals("") ||

minMeasureValue.getText().trim().equals(""))

return;

AlgorithmMeasure(button.getText());

}

}

…

92


…

public void AlgorithmMeasure(String name)

{

String selectedView;

if(chartViewRadioButton.isSelected())

selectedView = "chart";

else

selectedView = "table";

controller.executeAlgorithm(name,

Integer.parseInt(minMeasureValue.getText()),

Integer.parseInt(measureNumber.getText()),

selectedView);

}


93

View - DefaultChartView

93

• View secondaria che si occupa di visualizzare i risultati di

ciascuna valutazione per tutte le misure effettuate

• Implementa l’interfaccia ChartView (pattern Factory)


• Estende JDialog

• Il controller le passa l’insieme di misure da visualizzare

BoxLayout

class impl

JDialog

DefaultChartView

+ DefaultChartView(List<Measure>, String)

# initGUI() : void

+ showView() : void

«interface»

v iews::ChartView

+ showView() : void

94

ChartView - Codice

94

package views;

public interface ChartView

{

void showView();

}


95

DefaultChartView - Codice

95

package views.impl;

public class DefaultChartView extends JDialog implements

ChartView

{

private List<Measure> measures;

private String algorithmName;

public DefaultChartView(List<Measure> measures,


{

this.measures = measures;

this.algorithmName = algorithmName;

initGUI();

}

…

}

96


96

…


{

setVisible(true);

}


{

setTitle("Complexity Measure Charts of the " +

algorithmName + " Algorithm");

setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);

this.setModal(false);


mainPanel.setAlignmentY(Component.CENTER_ALIGNMENT);

mainPanel.setLayout(new BoxLayout(mainPanel,

BoxLayout.Y_AXIS));

…


97


97

…

int[] arrayDimension = new int[measures.size()];

int[] arrayAssign = new int[measures.size()];

int[] arrayFlip = new int[measures.size()];

int[] arrayComparision = new int[measures.size()];

long[] arrayTime = new long[measures.size()];

int i = 0;

for(Measure measure: measures)

{

arrayDimension[i] = measure.getArrayDimension();

arrayAssign[i] = measure.getAssignes();

arrayFlip[i] = measure.getFlips();

arrayComparision[i] = measure.getComparisions();

arrayTime[i] = measure.getTime();

i++;

}

…

98


98

…

JPanel assignPanel =

PlotComplexityCharts.plotMeasure("Assigns",

arrayDimension, arrayAssign);

JPanel flipPanel =

PlotComplexityCharts.plotMeasure("Flips",

arrayDimension, arrayFlip);

JPanel comparisionPanel =

PlotComplexityCharts.plotMeasure("Comparisions",

arrayDimension, arrayComparision);

JPanel timePanel =

PlotComplexityCharts.plotMeasure("Time",

arrayDimension, arrayTime);

mainPanel.add(assignPanel);

mainPanel.add(flipPanel);

mainPanel.add(comparisionPanel);

mainPanel.add(timePanel);

…


99


99

…

JScrollPane scroll = new JScrollPane(mainPanel);

add(scroll, "Center");

setSize(400, 500);


}

100

PlotComplexityCharts

100

• DefaultChartView sfrutta il metodo plotMeasure()

della classe statica PlotComplexityCharts, da cui

ottiene un pannello contenente il grafico relativo

all’andamento di una valutazione per l’insieme di misure

effettuate

• plotMeasure() richiede:

• il nome della valutazione (es. “Assegnamento”)

• le dimensioni degli input di ciascuna misura (array di int)

• le valutazioni delle diverse misure (array di int o di long)

• La classe non deve essere realizzata perché vi è stata

fornita!


101

PlotComplexityCharts - Codice

101

package controls;

public class PlotComplexityCharts

{

public static JPanel plotMeasure(String measure, int[] n,

int[] measures)

{

XYSeries series = new XYSeries("");

for (int i = 0; i < n.length; i++)

{

series.add(n[i], measures[i]);

}

return createChartPanel(plot("", measure, series));

}

…

}

102


102

…

public static JPanel plotMeasure(String measure, int[] n,

long[] measures)

{

XYSeries series = new XYSeries("");

for (int i = 0; i < n.length; i++)

series.add(n[i], measures[i]);

return createChartPanel(plot("", measure, series));

}

…


103


103

…

private static JPanel createChartPanel(JFreeChart chart)

{

ChartPanel chartPanel = new ChartPanel(chart);

chartPanel.setPreferredSize(new java.awt.Dimension(500,

270));

return chartPanel;

}

private static JFreeChart plot(String measureDesc,

String measure, XYSeries series)

{

XYSeriesCollection data =

new XYSeriesCollection(series);

JFreeChart chart =

ChartFactory.createXYLineChart(measureDesc, "Array

Dimension", measure,

data, PlotOrientation.VERTICAL, true, true, false);

return chart;

}

104

View - DefaultTableView• View secondaria che si occupa di visualizzare per ogni

misura, i risultati di ciascuna valutazione

• Implementa l’interfaccia TableView (pattern Factory)


• Estende JDialog

• Il controller gli passa l’insieme di misure effettuate

BoxLayout

class impl

JDialog

DefaultTableView

+ createNewPanel(int, int, int, int, int, long) : JPanel

+ DefaultTableView(List<Measure>, String)

# initGUI() : void

+ showView() : void

«interface»

v iews::TableView

+ showView() : void


105

TableView - Codice

105

package views;

public interface TableView

{

void showView();

}

106

DefaultTableView - Codicepackage views.impl;

public class DefaultTableView extends JDialog implements

TableView

{

private List<Measure> measures;

private String algorithmName;

public DefaultTableView(List<Measure> measures, String

algorithmName)

{

this.measures = measures;

this.algorithmName = algorithmName;

initGUI();

}

…

}


107

DefaultTableView - Codice…


{

setVisible(true);

}


{

setTitle("Complexity Measure Charts of the " +

algorithmName + " Algorithm");

setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);

this.setModal(false);


mainPanel.setAlignmentY(Component.CENTER_ALIGNMENT);

mainPanel.setLayout(new BoxLayout(mainPanel,

BoxLayout.Y_AXIS));

…

108


int i = 1;

for(Measure measure: measures)

{

JPanel measurePanel = createNewPanel(i++,

measure.getArrayDimension(),

measure.getAssignes(),

measure.getFlips(), measure.getComparisions(),

measure.getTime());

mainPanel.add(measurePanel);

}

JScrollPane scroll = new JScrollPane(mainPanel);

add(scroll, "Center");

setSize(300, 300);


}

…


109

DefaultTableView - Codicepublic JPanel createNewPanel(int measureNumber, int

arrayDimension, int assignes, int flips, int

comparisions, long time)

{


mainPanel.setLayout(new BorderLayout());

JPanel titlePanel = new JPanel();

{

titlePanel.setLayout(

new FlowLayout(FlowLayout.CENTER));

titlePanel.setBackground(Color.white);

Font labelFont = new Font(null, Font.BOLD, 12);

JLabel titleLabel = new JLabel("Measure Number: " +

measureNumber);

titleLabel.setFont(labelFont);

titlePanel.add(titleLabel);

}

mainPanel.add(titlePanel, BorderLayout.NORTH);

110


JPanel measurePanel = new JPanel();

{

measurePanel.setLayout(new GridLayout(5,1));

JLabel dimensionLabel = new JLabel("Array Dimension: " +

arrayDimension);

measurePanel.add(dimensionLabel);

JLabel assigneLabel = new JLabel("Number of Assignes: "

+ assignes);

measurePanel.add(assigneLabel);

JLabel flipLabel = new JLabel("Number of Flips: " +

flips);

measurePanel.add(flipLabel);

…


111

DefaultTableView - Codice

…

JLabel comparisionsLabel = new JLabel("Number of

Comparisons: " + comparisions);

measurePanel.add(comparisionsLabel);

JLabel timeLabel = new JLabel("Execution Time: " +

time);

measurePanel.add(timeLabel);

}

mainPanel.add(measurePanel, BorderLayout.CENTER);

return mainPanel;

}

112

Program - Codice

public class Program

{

public static void main(String[] args)

{

new MeasureController(new ArrayList<Measure>(),

new IntegerAlgorithmFactory(),

new DefaultViewFactory()).start();

}

}


113


• Scaricare dal sito del corso lo start kit

dell’esercitazione (comprende la classe PlotComplexityCharts e due jar da

importare nel progetto)

• Buon Lavoro!

113

Esercizio Calcolo Complessità Algoritmilia.deis.unibo.it/Courses/FondT2-0809-INF/lab/... ·...

Documents

Transcript of Esercizio Calcolo Complessità Algoritmilia.deis.unibo.it/Courses/FondT2-0809-INF/lab/... ·...