SortedSet e ordinamento esterno

di
manu2794
il
6 risposte
M
manu2794
Pochi posts
Iscritto da
mag, 2018
Messaggi:
4

SortedSet e ordinamento esterno

Buongiorno,
Sto cercando un modo per scrivere questo metodo:
public SortedMap<Coordinate,Integer> utilizzi(List<Tragitto> tragitti) {
La classe Tragitto ha due coordinate "origine" e "destinazione";
la classe Coordinate ha i campi int x e int y.

Il metodo chiede di ritornare una mappa ordinata decrescente in cui figurano come chiavi le posizioni più frequentemente utilizzate come destinazione e/o origine di uno dei tragitti della lista ricevuta e come valore un oggetto Integer pari al numero complessivo di utilizzi di quella posizione.
Il testo specifica di utilizzare un ordinamento esterno.

Qual è la soluzione migliore secondo voi?
P.S.: Versione Java 7

6 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: SortedSet e ordinamento esterno

    manu2794 ha scritto:

    Il metodo chiede di ritornare una mappa ordinata decrescente in cui figurano come chiavi le posizioni più frequentemente utilizzate come destinazione e/o origine di uno dei tragitti della lista ricevuta e come valore un oggetto Integer pari al numero complessivo di utilizzi di quella posizione.
    Il testo specifica di utilizzare un ordinamento esterno.
    SortedMap è una interfaccia quindi dovrai usare una sua implementazione, di norma TreeMap che è "sorted". Ma c'è una questione: dici "decrescente in cui figurano come chiavi le posizioni più frequentemente utilizzate", quindi il criterio di comparazione nella mappa NON è sugli oggetti Coordinate ma sul valore (quei Integer che avrai come valori)!
    Ora: con questa premessa risulta quindi scontato che DEVI usare un Comparator. E il comparator che implementi dovrà avere accesso alla mappa, perché dovrà ricevere due chiavi (TreeMap ordina sulle CHIAVI !) e poi fai tu un "lookup" per avere i valori che confronterai.

    Ma il punto è che quando hai in mano un oggetto Coordinate, per poter fare +1 sul valore, l'oggetto Coordinate lo devi prima cercare nella mappa. E non lo puoi fare con quel criterio detto prima.

    Quindi: prima fai un HashMap (quindi "veloce") con mappatura Coordinate--->contatore. Ogni Tragitto contribuisce con 2 oggetti Coordinate. Per ciascuna Coordinate, la cerchi nella mappa, se c'è fai +1 sul valore, se non c'è inserisci l'associazione con valore iniziale 1.

    Poi dopo TUTTA questa elaborazione, farai un TreeMap con un Comparator specifico che ordina sulla chiavi ma facendo "lookup" sui valori. Che è una cosa un po' "strana" normalmente ma si può fare.
  • M
    manu2794
    Pochi posts
    Iscritto da
    mag, 2018
    Messaggi:
    4

    Re: SortedSet e ordinamento esterno

    Ti ringrazio innanzitutto della risposta.
    Ho pensato anche io a una maniera simile per risolverlo ma non ho ben capito come fare il Comparator. Al comparator dovrei passare l'intera mappa? Cosi facendo avrei un compare con due mappe come parametri, mi sembra un po' prolisso, sicuramente ho capito male io.
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: SortedSet e ordinamento esterno

    manu2794 ha scritto:

    Al comparator dovrei passare l'intera mappa? Cosi facendo avrei un compare con due mappe come parametri
    No, detto così è sbagliato. Il compare() di Comparator, nel contesto delle sorted-map, riceve sempre e solo due CHIAVI.

    Comunque ci ho ragionato un po' e .... non è così banale. Partiamo dal punto semplice: quando devi conteggiare le occorrenze delle coordinate, ti conviene usare HashMap come detto prima. Quando hai finito questo step, qui viene la parte difficile.
    Il comparator va passato ad un costruttore di TreeMap. Non c'è altro modo, perché il criterio di comparazione non può cambiare in TreeMap successivamente.
    Il comparator NON può accedere al TreeMap stesso. Non perché non sia possibile tecnicamente (si fa) ma perché il comparator viene invocato ad ogni operazione di ricerca all'interno del TreeMap, anche quando si inserisce qualcosa. Se all'interno del comparator fai un get sulla stessa mappa, scateni altre ricerche che invocano di nuovo il comparator ecc... Morale: "esplode" tutto con un bel StackOverflowError.
    Il comparator potrebbe accedere al HashMap della prima fase. Questo sì, tecnicamente è possibile e non darebbe problemi.

    Il punto è che alla fine, ammesso di arrivare a popolare il TreeMap, avresti questo TreeMap il cui Comparator si basa su un'altra mappa, il HashMap. Quindi avresti sì l'ordinamento per valore (le occorrenze) e la iterazione darebbe quel ordine. Ma non ci potresti fare altro.

    Pertanto: alla luce di questo, ti è chiaro? Cosa pensi di fare? Sicuro che serva davvero un SortedMap<Coordinate,Integer> con criterio "per valore"?? E magari non si possa fare in altro modo?
  • M
    manu2794
    Pochi posts
    Iscritto da
    mag, 2018
    Messaggi:
    4

    Re: SortedSet e ordinamento esterno

    Si hai perfettamente ragione, scrivo la soluzione per altri eventuali utenti che ne abbiano bisogno.
    Ho chiesto a un compagno di corso e lui dopo l'HashMap, nello stesso metodo ha creato un Comparator con due oggetti Coordinate.
    Nel compare ha dichiarato due valori e inizializzati con i valori interi della mappa associati alle coordinate che ha come parametro il compare:
    
ComparatoreValori implements Comparator<Coordinate> {
	@Override
		public int compare(Coordinate c1, Coordinate c2) {
			int num1 = mappa.get(c1).intValue();
			int num2 = mappa.get(c2).intValue();
			if(num1 == num2) {
				if (c1.getX() == c2.getX())
					return c2.getY() - c1.getY();
				return c2.getX() - c1.getX();
			}
			return num2-num1;
		}
	}
    Qui oltre a comparare i valori della mappa compara poi anche le coordinate nel caso in cui i valori della mappa siano uguali.
    Successivamente basta creare il TreeMap con un'istanza del comparatore(sopra realizzato) e copiarci l'HashMap dentro.
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: SortedSet e ordinamento esterno

    manu2794 ha scritto:

    
ComparatoreValori implements Comparator<Coordinate> {
	@Override
		public int compare(Coordinate c1, Coordinate c2) {
			int num1 = mappa.get(c1).intValue();
			int num2 = mappa.get(c2).intValue();
			if(num1 == num2) {
				if (c1.getX() == c2.getX())
					return c2.getY() - c1.getY();
				return c2.getX() - c1.getX();
			}
			return num2-num1;
		}
	}
    Attenzione che con un comparator fatto così, NON si devono fare poi dei get sul TreeMap per chiavi inesistenti. Perché altrimenti ti becchi un NullPointerException su uno dei due intValue();

    E inoltre, la parte: 
    			if(num1 == num2) {
				if (c1.getX() == c2.getX())
					return c2.getY() - c1.getY();
				return c2.getX() - c1.getX();
			}
			return num2-num1;
    Non è granché bella. Se usi almeno Java 7 sappi che Integer ha un bellissimo public static int compare(int x, int y)
  • M
    manu2794
    Pochi posts
    Iscritto da
    mag, 2018
    Messaggi:
    4

    Re: SortedSet e ordinamento esterno

    Mi scuso se rispondo solo ora, l'esame è andato da un pezzo..
    Attenzione che con un comparator fatto così, NON si devono fare poi dei get sul TreeMap per chiavi inesistenti. Perché altrimenti ti becchi un NullPointerException su uno dei due intValue();
    Qui bastava quindi fare dei controlli sul null
    Non è granché bella. Se usi almeno Java 7 sappi che Integer ha un bellissimo public static int compare(int x, int y)
    Questo non lo sapevo, buono a sapersi.
    Grazie di tutto, penso di chiedere in questo forum per qualunque altro problema.
Devi accedere o registrarti per scrivere nel forum
6 risposte