Esercitazione (compito 2-12-2002)

‰ Una coda ordinata (CO) è definita dalla seguente classe:

// CO.java --coda ordinata public class CO{ /* parte privata della classe */

public CO() {...} public void accoda(Comparable x) {...} public Object togli() {...}

Esercitazione

‰ Completare la classe CO con la parte privata e con il codice cherealizza i metodi e il costruttore

‰ La classe CO non deve avere altri metodi pubblici oltre a quellidefiniti sopra

‰ Scrivere una classe Main di prova che:

–

legga un file di testo composto da righe formate di parole (le parole sono sequenze di caratteri alfabetici separate da uno piu' spazi) inserendo le singole parole in una coda ordinata

–

trasferisca il contenuto della coda in una seconda coda ordinata eliminando le parole ripetute e vuoti la seconda coda trasferendo le parole sull'uscita standard una parola per riga

–

Il nome del file di ingresso deve essere passato al metodomain( ) come parametro della riga di comando.

Analisi: la classe CO

‰ Il metodo togli() deve restituire sempre l’oggetto piu’ piccolo presente nella coda

‰ Per questo ci sono due soluzioni possibili:

A.Il metodo accoda() non si cura dell’ordinamento degli oggetti,mentre il metodo togli() esegue la ricerca del minimoscandendo tutta la coda.

– In questo caso possiamo realizzare, al meglio, i metodi accoda() e togli() con andamenti asintotici O(1) e O(n), rispettivamente.

66

Analisi: la classe CO

B.Il metodo accoda() inserisce l’oggetto in modo da mantenere ordinato l’insieme dei dati, mentre il metodo togli() restituisce l’oggetto piu’ piccolo

–

In questo caso possiamo realizzare, al meglio, i metodi accoda() e togli() con andamenti asintotici O(n) e O(1), rispettivamente, usando nel metodo accoda l’algoritmo di ordinamento per inserimento (insertionSort)

–

l’ordinamento effettuato dal metodo accoda() avviene in un insieme gia’ ordinato

–

Il metodo togli() non modifica l’ordinamento nell’insieme

Soluzione con catena

‰ Scegliamo come contenitore la struttura dati catena

‰ Il metodo accoda() mantenga i dati ordinati in sensocrescente in modo che il dato piu’ piccolo si trovi nel primo nodo

‰ Il metodo togli() restituisce il dato contenuto nel primonodo

‰ Realizziamo la classe Nodo come classe interna della classe CO

Soluzione con array

‰ Scegliamo come contenitore la struttura dati arrayriempito parzialmente

‰ Il metodo accoda() mantenga i dati ordinati in sensodecrescente in modo che il dato piu’ piccolo si trovi nella locazione di indice arraySize -1

‰ Il metodo togli() restituisce il dato contenuto nellalocazione di indice arraySize -1

74

Classe di prova

import java.io.IOException;import java.io.FileReader;import java.util.Scanner;

public class MainCO{ public static void main(String[] args)

^{{ throws IOException}// Verifica argomenti su riga di comando

^{if(args.length < 1)}{ _{System.out.println(}

"uso: $java MainCO nomeFile");return;}

Classe di prova

// lettura file Scanner in = new Scanner( new FileReader(args[0])); CO storeCO = new CO();

^{while (in.hasNextLine()){} Scanner tok = new Scanner(in.nextLine());

while (tok.hasNext()) storeCO.accoda(tok.next()); _} tok.close();

in.close();

78

79

Prova del programma

‰ Usare un file di prova come file di ingresso, ad esempio un file come i seguenti

‰ Inserire in punti chiave del codice istruzioni di stampa a standard output per il debugging

– ad esempio nel motodo accoda(), dopo l’inserimento del dato, si stampino il valore della variabile objSize e i dati ordinati

//Inserimento nell’array

obj[i] = x;

objSize++;

//System.out.println(“objSize = “

Soluzione con tabella hash

// TR1.java --traduttore // soluzione efficiente realizzata con una// tabella hashimport java.io.*;import java.util.*;public class TR1_{ class Nodo

^{ String chiave; String attributo; Nodo prossimo;

Nodo (String c, String a, Nodo p) { chiave = c; attributo = a; _{} }} prossimo = p;

Soluzione con tabella hash

// parte privata private Nodo[] v; private static final int MAX = 97;

private int h(String ch)_{{ int n = 0;}

for (int i = 0; i < ch.length(); i++) n = ((31 * n) + ch.charAt(i)) % MAX;

return n; }

Soluzione con tabella hash

public String inItaliano(String x)_{{ Nodo p = v[h(x)];}

while (p != null) if (x.compareTo(p.chiave) == 0) return p.attributo; else p = p.prossimo;

return null; }

public String inInglese(String x)_{

_} return inItaliano(x);

} // fine della classe

Soluzione con doppia tabella hash

// TR2.java --traduttore // soluzione efficiente realizzata con due// tabelle hashimport java.io.*;import java.util.*;public class TR2{ class Nodo

{ … }

private Nodo[] inInglese;private Nodo[] inItaliano;private static final int MAX = 11;

private int h (String ch) { … }

Soluzione con doppia tabella hash

public String inItaliano(String x)_{{ Nodo p = inItaliano[h(x)];}

while (p != null) if (x.compareTo(p.chiave) == 0) return p.attributo; else p = p.prossimo; return null;

^}public String inInglese(String x)_{{ Nodo p = inInglese[h(x)];}

while (p != null) if (x.compareTo(p.chiave) == 0) return p.attributo; else p = p.prossimo; return null;

Classe di prova

import java.io.IOException;import java.util.Scanner;

public class Main{ public static void main(String[] arg) throws IOException{ Scanner in = new Scanner(System.in);TR2 diz = new TR2(arg[0]);

while (in.hasNext())

{ String parola = in.next(); String traduzione = diz.inInglese(parola); if (traduzione == null)

System.out.print("*" + parola + "* ");else System.out.print(traduzione + " ");_{} } }in.close();}System.out.println();

File di ingreso di prova

Lezione XXXIV Gi 24-Nov-2005

ADT Set Standard Error

Il flusso di errore standard

‰ Abbiamo visto che un programma Java ha sempre due flussi ad esso collegati

– il flusso di ingresso standard, System.in

– il flusso di uscita standard, System.out che vengono forniti dal sistema operativo In realtà esiste un altro flusso, chiamato flusso di

errore standard o standard error, rappresentato dall’oggetto System.err

– System.err è di tipo PrintStream come System.out

Il flusso di errore standard

‰ La differenza tra System.out e System.err è solo convenzionale

–

si usa System.out per comunicare all’utente i risultati dell’elaborazione o qualunque altro messaggio che sia previsto dal corretto e normale funzionamento del programma

–

si usa System.err per comunicare all’utente eventuali condizioni di errore (fatali o non fatali) che si siano verificate durante il funzionamento del programma

Il flusso di errore standard

‰ In condizioni normali (cioè senza redirezione) lo standard error finisce sullo schermo insieme allo standard output

‰ In genere il sistema operativo consente di effettuare la redirezione dello standard error in modo indipendente dallo standard output

–

in Windows è possibile redirigere soltanto lo standard output, mentre lo standard error rimane verso lo schermo

–

in Unix è possibile redirigere i due flussi verso due file distinti

ADT Set Realizzazione di un insieme

Insieme

Il tipo di dati astratto “insieme” (set) è un contenitore (eventualmente vuoto) di oggetti distinti (cioè non contiene duplicati)

–

senza alcun particolare ordinamento

–

senza memoria dell’ordine temporale in cui gli oggetti vengono inseriti o estratti

–

si comporta come un insieme matematico

Le operazioni consentite sull’insieme sono

–

inserimento di un oggetto

• fallisce silenziosamente se l’oggetto è già presente

–

verifica della presenza di un oggetto

–

ispezione di tutti gli oggetti, mediante un metodo cherestituisce un array di riferimenti agli oggetti contenuti nell’insieme, senza alcun requisito di ordinamento ditale array (anche perché i dati non sono ordinabili...)

Non esiste un’operazione di rimozione

– si usa la sottrazione tra insiemi (vedi in seguito)

Operazioni sugli insiemi

Per due insiemi A e B, si definiscono le operazioni

–

unione A ∪ B

• appartengono all’unione di due insiemi tutti e soli gli elementi che appartengono ad almeno uno dei due insiemi

–

intersezione A ∩ B

• appartengono all’intersezione di due insiemi tutti e soli gli elementi che appartengono ad entrambi gli insiemi

–

sottrazione A -B (oppure anche A \ B)

• appartengono all’insieme sottrazione A-B tutti e soli gli elementi che appartengono all’insieme A e non appartengono all’insieme B

• non è necessario che B sia un sottoinsieme di A

Insieme con array non ordinato

Quando si scrive una classe, è comodo scrivere prima le firme di tutti i metodi, con un corpo “vuoto”

‰ Invece di compilare tutto alla fine, si compila ogni volta che si scrive il corpo di un metodo

– in questo modo, si evita di trovarsi nella situazione in cui il compilatore segnala molti errori

Insieme con array non ordinato

Operazioni su insiemi: unione

Insiemi: intersezione e sottrazione

Insieme con array non ordinato

‰ Riassumendo, realizzando un insieme con un array non ordinato

– le prestazioni di tutte le primitive dell’insieme sono O(n)

– le prestazioni di tutte le operazioni che agiscono su due insiemi sono O(n²) Si può facilmente verificare che si ottengono le stesse

prestazioni realizzando l’insieme con una catena (prestazioni determinate dalla ricerca)

Insieme di dati ordinabili

‰ Cerchiamo di capire se si possono ottenere prestazioni migliori quando l’insieme contiene dati ordinabili

‰ Definiamo l’interfaccia “insieme ordinato”

Insieme di dati ordinabili

‰ Realizziamo l’interfaccia SortedSet usando un array ordinato

– dovremo definire due metodi add(), uno dei quali

impedisce l’inserimento di dati non ordinabili

Insieme con array ordinato

Operazioni su insiemi ordinati

‰ Gli algoritmi già visti per le operazioni sugli insiemigenerici possono essere utilizzati senza alcunamodifica anche per l’insieme ordinato, realizzatocon un array ordinato

–

infatti, un SortedSet è anche un Set

–

la complessità di tutti gli algoritmi (unione,intersezione e sottrazione) rimane O(n²), perchéil metodo add è rimasto O(n)

Senza sfruttare le informazioni sull’ordinamento dell’insieme, non è possibile ottenere prestazionimigliori...

Operazioni su insiemi ordinati

‰ Usare l’incapsulamento a oltranza può essere sconveniente…

‰ In questo caso, sapendo che

–

l’array ottenuto con il metodo toSortedArray è ordinato

–

l’inserimento nell’insieme avviene nel metodo add() con l’algoritmo di ordinamento per inserzione in un array ordinato

è possibile scrivere versioni più efficienti dei metodi già visti

Operazioni su insiemi: unione

Per realizzare l’unione, osserviamo che il problema è molto simile alla fusione di due array ordinati

– come abbiamo visto in MergeSort, questo algoritmo di fusione è O(n)

L’unica differenza consiste nella contemporanea eliminazione (cioè nel non inserimento…) di eventuali oggetti duplicati

– un oggetto presente in entrambi gli insiemi dovrà essere presente una sola volta nell’insieme unione

Operazioni su insiemi: unione

‰ Effettuando la fusione dei due array ordinati secondo l’algoritmo visto in MergeSort, gli oggetti vengono via via inseriti nell’insieme unione che si va costruendo

‰ Se gli inserimenti avvengono con oggetti in ordine crescente, l’ordinamento per inserzione in un array ordinato che viene usato dal metodo add() ha prestazioni O(1) per ogni inserimento!

–

il metodo add() ha quindi prestazioni O(log n)

• perché invoca contains() che è O(log n)

–

se gli inserimenti non avvengono in ordine crescente, il metodo add() ha prestazioni medie di tipo O(n)

Operazioni su insiemi: unione

Operazioni su insiemi: sottrazione