[JAVA] Esercizio d'esame...problema a capire l'inizializzazione di matrici, helpme

[e-commerce84]

Ciao,
stò studiando per un esame che avrò tra poghi giorni ed ho qualche problema con la soluzione proposta in classe dal docente.

Il testo dice:
Si richiede il progetto di un dizionario, ossia un'insieme di associazionei, dove ogni associazione è del tipo PAROLA-TRADUZIONE e sia PAROLA che TRADUZIONE sono stringhe costituite da caratteri alfabetici minuscoli.
E' richiesta l'implementazione del solo operatore traduci() che data una PAROLA restituisce la sua TRADUZIONE.

In classe è stato risolto così:

/** TIPO ASTRATTO DI DATO:
	
	V = {{<p,t>: p ^ t sono stringhe costituite da caratteri alfabetici minuscoli} *NB: Si tratta di un insieme di insiemi
	perchè voglio rappresentare una collezione di associazioni parola-traduzione.
	
	O = { 1) traduci: Data una parola p, se p € Dizionario restituisce la traduzione t
	
	C = 0 (non ci sono costanti significative */
	
public class Dizionario{
	
	private string [][] d;		// Rappresendo le associazioni parola-traduzione mediante una matrice quadrata
	
	/** REQUIRES: Il parametro deve essere un array bidimensionale di n righe e due colonne, interamente popolato da
				  stringhe di caratteri minuscoli */
				  
	public Dizionario(String[][] x){	// COSTRUTTORE
		int i,j;
		
		d = new String[x.length];		// Crea un array di stringhe lungo come x (numero righe)
		
		for(i=0; i<x.length; i++){
			if(x[i].length != 2) throw new FailureException();
			
			d[i] = new String[2];
			
			for(j=0; j<2; j++){
				if(corretto(x[i,j])
					d[i][j] = x[i][j];
				else throw new FailureException;
			}
		}
	}
	
	/** EFFECTS: Restituisce la traduzione dell'oggetto ricevente
		@param: il riferimento ad una oggetto di tipo String
		@return: il riferimento ad un oggetto di tipo String */
		
	public String traduci(String p){
		int i;
		Strint ris = null;
		
		for(i=0; i<d.length; i++)
			if(d[i][0] equals(p))
				ris = d[i][1];
		
		return ris;
	}
}

Praticamente il dizionario viene semplicemente gestito tramite una matrice bidimensionali di n righe e sole due colonne: la prima colonna di ogni rig conterrà una PAROLA e la seconda colonna conterrà la sua TRADUZIONE. Il metodo traduci() è molto semplice...

La cosa che mi crea qualche problema è il costruttore...praticamente prende come parametro una matrice di stringhe e dentro al costruttore viene allocata un'altra matrice di stringhe nel quale viene copiato il parametro...solo che non capisco come lo faccia...

Venendo da C mi pare differente (anche se non tocco C da quasi un annetto)...mi potete illuminare un pochino su cosa sta fecendo esattamente?

Tnx

[banryu79]

Rispondo in fretta e furia:

Originariamente inviato da e-commerce84

Praticamente il dizionario viene semplicemente gestito tramite una matrice bidimensionale di n righe e sole due colonne: la prima colonna di ogni rig conterrà una PAROLA e la seconda colonna conterrà la sua TRADUZIONE. Il metodo traduci() è molto semplice...

Solo un appunto: se l'indicazione che leggo qui (evidenziato in grassetto):

/** TIPO ASTRATTO DI DATO:
	
	V = {{<p,t>: p ^ t sono stringhe costituite da caratteri alfabetici minuscoli} *NB: Si tratta di un insieme di insiemi
	perchè voglio rappresentare una collezione di associazioni parola-traduzione.
	
	O = { 1) traduci: Data una parola p, se p € Dizionario restituisce la traduzione t
	
	C = 0 (non ci sono costanti significative */

starebbe a indicare che la complessità computazionale del metodo 'traduci' è costante, allora è errata; il metodo 'traduci', per come è stato implementato (cicla in ordine su ogni indice-riga della matrice e controlla se il primo elemento è la parola cercata) denota una complessità lineare.
Inoltre, cosa da notare, se la stringa passata in ingresso non è compresa nel dizionario, il metodo esegue tutte le N iterazioni prima di tornare.
Questo giusto per essere coscienti della cosa.

Originariamente inviato da e-commerce84

La cosa che mi crea qualche problema è il costruttore...praticamente prende come parametro una matrice di stringhe e dentro al costruttore viene allocata un'altra matrice di stringhe nel quale viene copiato il parametro...solo che non capisco come lo faccia...

Venendo da C mi pare differente (anche se non tocco C da quasi un annetto)...mi potete illuminare un pochino su cosa sta fecendo esattamente?

La differenza che noti rispetto al linguaggio C è dovuta la fatto che in Java:
1) Non esistono i puntatori, esistono solo le reference (riferimenti) e non sono la stessa cosa;
2) il passaggio dei parametri ai metodi avviene sempre e solo per copia del valore.

Nello specifico il punto 2) significa che se passi una reference (come nel caso del tuo costruttore, dove 'x' è una reference a un oggetto di tipo String[][]) questa viene passata per copia del valore che contiene: la 'x' locale al metodo è una nuova reference il cui valore interno è lo stesso della reference passata in ingresso dal chiamante.

Il valore di una reference è l'indirizzo in memoria dove è memorizzato l'oggetto a cui ci si riferisce.

Quindi questo costruttore prende un riferimento a un oggetto String[][] già esistente, e dovendo inizializzare la reference locale alla classe ('d', di tipo String[][]) ad ogni iterazione del ciclo più esterno (ogni riga della matrice) alloca due nuove istanze di String (una per la PAROLA, l'altra per la TRADUZIONE) e copia le due String corrispondenti della matrice nelle due appena istanziate del dizionario 'd'.

Questo perchè in tal modo si vorrebbe realizzare una "copia interna" della matrice, in modo che agendo su i singoli nuovi oggetti istanziati nel dizionario non si vada a modificare quelli esterni della matrice passata al metodo.

In pratica l'esempio non è dei più felici per via della particolare natura degli oggetti String in Java (sono immutabili, il che vuol dire che se esegui un metodo che sembra avere l'effetto di modificare una String, in realtà stai creando un'altra String: il tipico caso è eseguire l'append tra oggetti string con l'operatore '+'; il risultato non è la modifica della String originaria ma la creazione di una nuova singola String ad ogni append eseguito [e anche questa affermazione non è del tutto corretta]).

Comuque questi sono probabilmente aspetti un po' più avanzati rispetto a ciò che state trattando adesso.

[e-commerce84]

Originariamente inviato da banryu79

Rispondo in fretta e furia:

Solo un appunto: se l'indicazione che leggo qui (evidenziato in grassetto):

/** TIPO ASTRATTO DI DATO:
	
	V = {{<p,t>: p ^ t sono stringhe costituite da caratteri alfabetici minuscoli} *NB: Si tratta di un insieme di insiemi
	perchè voglio rappresentare una collezione di associazioni parola-traduzione.
	
	O = { 1) traduci: Data una parola p, se p € Dizionario restituisce la traduzione t
	
	C = 0 (non ci sono costanti significative */

starebbe a indicare che la complessità computazionale del metodo 'traduci' è costante, allora è errata; il metodo 'traduci', per come è stato implementato (cicla in ordine su ogni indice-riga della matrice e controlla se il primo elemento è la parola cercata) denota una complessità lineare.
Inoltre, cosa da notare, se la stringa passata in ingresso non è compresa nel dizionario, il metodo esegue tutte le N iterazioni prima di tornare.
Questo giusto per essere coscienti della cosa.



La differenza che noti rispetto al linguaggio C è dovuta la fatto che in Java:
1) Non esistono i puntatori, esistono solo le reference (riferimenti) e non sono la stessa cosa;
2) il passaggio dei parametri ai metodi avviene sempre e solo per copia del valore.

Nello specifico il punto 2) significa che se passi una reference (come nel caso del tuo costruttore, dove 'x' è una reference a un oggetto di tipo String[][]) questa viene passata per copia del valore che contiene: la 'x' locale al metodo è una nuova reference il cui valore interno è lo stesso della reference passata in ingresso dal chiamante.

Il valore di una reference è l'indirizzo in memoria dove è memorizzato l'oggetto a cui ci si riferisce.

Quindi questo costruttore prende un riferimento a un oggetto String[][] già esistente, e dovendo inizializzare la reference locale alla classe ('d', di tipo String[][]) ad ogni iterazione del ciclo più esterno (ogni riga della matrice) alloca due nuove istanze di String (una per la PAROLA, l'altra per la TRADUZIONE) e copia le due String corrispondenti della matrice nelle due appena istanziate del dizionario 'd'.

Questo perchè in tal modo si vorrebbe realizzare una "copia interna" della matrice, in modo che agendo su i singoli nuovi oggetti istanziati nel dizionario non si vada a modificare quelli esterni della matrice passata al metodo.

In pratica l'esempio non è dei più felici per via della particolare natura degli oggetti String in Java (sono immutabili, il che vuol dire che se esegui un metodo che sembra avere l'effetto di modificare una String, in realtà stai creando un'altra String: il tipico caso è eseguire l'append tra oggetti string con l'operatore '+'; il risultato non è la modifica della String originaria ma la creazione di una nuova singola String ad ogni append eseguito [e anche questa affermazione non è del tutto corretta]).

Comuque questi sono probabilmente aspetti un po' più avanzati rispetto a ciò che state trattando adesso.

Quell' 1) significa solo metodo numero 1 e visto che che l'insieme degli operatori O da implementare è solo traduzione c'è solo quello

Holetto quello che mi hai scritto e credo di aver capito...dopo devo provare a rivederlo sul testo e provare a farmi un paio di esempi pratici perchè cmq è un argomento un po' impiccioso...in pratica il ciclo esterno alloca le righe e per ogni riga c'è un ciclo interno che alloca le colonne, giusto?

Volendo con questo giochetto potrei farmi anche delle matrici "non quadrate" (del tipo la prima riga ha 4 colonne, la seconda riga ha 2 colonne,la terza riga 5 colonne...) ?

Si la storia delle stringhe che sono oggetti costanti la sapevo...se non erano stringhe ma altri oggetti non costanti avrei dovuto effettuare una copia hard e mettere nelle celle della matrice il riferimento al nuovo oggetto creato per non avere rischi di far casini da altre parti

Tnx

[PGI-Bis]

Due note di colore. Java mutua da C l'esclusività del passaggio per copia e in Java i reference sono puntatori (quello che manca è l'aritmetica dei puntatori).

[e-commerce84]

Ed una cosa del genere sarebbe corretta?
Posso pure evitare di fare la validazione del fatto che le stringhe siano composte da soli caratteri alfabetici minuscoli in quanto metto una bella clausola REQUIRES e chissene frega...

d = new String[x.length][2];// Costruisco una matrice avente lo stesso numero di righe di x e avente sempre 2 colonne
		
		for(i=0; i<x.length; i++){		// Per ogni riga della nuova matrice d
			d[i][1] = x[i][1];		// Copia il contenuto della prima colonna della i-esima riga nella stessa posizione di d
			d[i][2] = x[i][2];	   // Copia il contenuto della seconda colonna della i-esima riga nella stessa posizione di d
		}

Sarebbe corretta una cosa del genere?

Tnx

[e-commerce84]

Ok...ora però ho qualche altro problema con la seconda parte dell'esame...sigh

Il testo del secondo esercizio(che si ricollega al primo esercizio) dice:

Problema 2.
Sia data la classe InsiemeDiFrazioni che rappresenta e gestisce insiemi di frazioni. Della classe
InsiemeDiFrazioni viene fornita la specifica, descritta come segue:
public class InsiemeDiFrazioni {
/** OVERVIEW: implementa un tipo di dati astratto i cui elementi
appartengono all’insieme V={ {f1, f2, ...., fn}: ogni elemento fi è
una frazione, cioè, una coppia di interi relativamente primi};
gli oggetti istanza di questa classe sono mutabili;
l’insieme vuoto è rappresentabile mediante questa classe.
*/
/** EFFECTS: crea l’oggetto corrispondente ad un insieme vuoto di frazioni
*/
public InsiemeDiFrazioni() { .... }
/** REQUIRES: x != null ed x non contenuto in this
EFFECTS: inserisce x in this
MODIFIES: this
*/
public void inserisci(Frazione x) { .... }
/** REQUIRES: x != null
EFFECTS: se x è contenuto in this restituisce true, altrimenti
restituisce false
*/
public boolean contiene(Frazione x) { .... }
/** REQUIRES: this != insieme vuoto
EFFECTS: restituisce la frazione in this il cui valore è più vicino ad
x
*/
public Object get(double x) { .... }
/** REQUIRES: x != null e x this != insieme vuoto
EFFECTS: rimuove x da this se x è contenuto in this
MODIFIES: this
*/
public void rimuovi(Frazione x) { .... }
public String toString() { .... }
}
Si consideri, infine, una classe di test per le due classi sopra descritte che contenga, oltre al metodo main, il metodo
getFirst che prende come parametro, indifferentemente, un InsiemeDiFrazioni o un Dizionario (classe da
definire al problema 1) e che estrae dalla collezione ricevuta come parametro l’elemento che risulta primo rispetto
all’ordinamento definito, rispettivamente, nell’insieme delle frazioni e nell’insieme { parola-traduzione}, cioè:
· un oggetto f1 di tipo Frazione precede un oggetto f2 di tipo Frazione se
f1.getValore() < f2.getValore()
dove double getValore() è un metodo definito nella classe Frazione;
· una coppia parola1-traduzione1 precede una coppia parola2-traduzione2 se parola1 precede
lessicograficamente parola2.
Si richiede il progetto e l’implementazione del metodo getFirst e di tutte le entità Java coinvolte.

Io l'ho pensato così: creo un'interface chiamata CollConMinimo che al suo interno contiene solamente un metodo abstract calcolaMinimo()
Poi creo altre due classi: una classe che chiamo DizionarioConMinimo che estende Dizionario precedentemente definita ed implementa CollConMinimo. Ed un'altra classe chiamata InsiemediFrazioniConMinimo che sempre estende la classe InsiemeDiFrazioni di cui mi è stata fornita la specifica ed implementa l''interfaccia CollConMinimo.

Per DizionarioConMinimo dovrebbe bastare questo codice, l'unica cosa è che dovrei implementare il metodo get nella classe Dizionario ma vabbè quello è un attimo:

public class DizionarioConMinimo extends Dizionario implements CollConMinimo{		// Ereditarietà multipla

	public DizionarioConMinimo(String[][] x){
		super(x);			// Invoca il costruttore della classe padre Dizionario passandogli la matrice di stringhe x
	}
	
	public Object calcolaMinimo(){
		
		int i = 1;
		boolean b = true;
		String s;
		
		try{
			s = get(0)
		}catch(IndiceErratoException e){}
		
		while(b){		// Finchè b è true
			try{		// Prova ad eseguire
				if(i.get(i).compare(s) < 0)	// Se l'i-esima stringa precede lessicograficamente la stringa contenuta in s
					s = get(i);				// Metti la stringa all'i-esimo posto in s
				}catch(IndiceErratoException e){b = false;}	// Quando viene sollevata l'eccezione imposta b a false per terminare il ciclo
				
			i++;		// Incrementa i per passare all'elemento successivo
		}
		
		return s;		// Restituisci la stringa calcolata
	}
}

Invece mi impippo nello scrivere il metodo calcolaMinimo per InsiemeDiFrazioniConMinimo in quanto dalla specifica non ho metodi per accedere agli oggetti della collezione di frazioni...qualche idea?

Poi vabbè per la classe di Test richiesta posso fare

public class Test{
       public Object getFirst(CollConMinimo c){
                  return c.calcolaMin();
       }
}

Mi date una mano?

Tnx

[e-commerce84]

up

[Ikon O'Cluster]

Secondo me il costruttore ti funziona anche se fai:

d = x

Ma non sono praticissimo di Java xkè lavoro in C++ e Java non lo tocco quasi mai, xkè non mi piace e genera programmi troppo pesanti e lenti. Cmq la soluzione in classe è un buon modo per far notare allo studente come possa essere importante il controllo sull'input. Quella matrice x non è detto che sia formattata correttamente. Laddove non c'è sicurezza sul formato dei dati è importante prevedere tutti i necessari controlli. Questo principio fondamentale è rivolto ad evitare bug difficilmente individuabili, quando il progetto assume dimensioni elevate. In tal caso infatti un formato non corretto potrebbe produrre un output alterato che a seconda dell'applicazione potrebbe anche passare per buono.