Comparator

di il
14 risposte

Comparator

Buona sera a tutti voi, per la vostra (in)felicitá sono tornato nuovamente su questi lidi!
Ma veniamo subito al sodo!
A scuola, dopo ore e ore di teoria, e vacanze, siamo giunti all'albero binario di ricerca (passando per albero e albero binario). Ora che siamo alla pratica, vorrei fare un BST (binary searching tree) con i generics, e se ho capito bene, si deve usare il comparator. Ora, ho provato a capirci qualcosa del comparator, ma non ci ho capito assolutamente nulla. Quindi quel che chiedo io, come va usato? Come funziona? Sarebbe di grande aiuto anche del codice (io ho provato una roba tipo
 public class BST<T> {....
E anche
 public class BST<T implements Comparator<T>{...}> 
O una roba simile, ma ho fatto solo casino

14 Risposte

  • Re: Comparator

    KuroKami69 ha scritto:


    vorrei fare un BST (binary searching tree) con i generics, e se ho capito bene, si deve usare il comparator. Ora, ho provato a capirci qualcosa del comparator, ma non ci ho capito assolutamente nulla. Quindi quel che chiedo io, come va usato? Come funziona?
    Partiamo da un presupposto: in Java la comparazione degli oggetti è stata affrontata con l'uso di due interfacce specifiche: Comparable e Comparator. Comparable va implementato nella classe degli oggetti da comparare; Comparator si implementa in classi esterne, slegate dalla classe degli oggetti da comparare.

    Riguardo il BST (vedi qui su Wikipedia), la comparazione si applica ovviamente agli elementi dell'albero, per la ricerca ma ovviamente ANCHE per l'inserimento.

    Guarda l'esempio di BST su Wikipedia, lì ci sono dei numeri. Con i numeri è abbastanza intuitivo. Ma si può applicare a qualunque altro tipo di dato, stabilendo un criterio di ordinamento. Se ho delle stringhe es. "arancia", "cocco", "mandarino", "mela", "uva" e voglio ordinarle con un BST secondo la lunghezza (ripeto: lunghezza, non alfabeticamente), allora il BST può risultare così:
           "arancia"
              / \
             /   \
            /     \
        "mela"  "mandarino"
         /  \
        /    \
       /      \
    "uva"   "cocco"
    "uva" è a sx di "mela" perché più corto; "cocco" è a dx di "mela" perché più lungo.
    "mela" è a sx di "arancia" perché più corto; "mandarino" è a dx di "arancia" perché più lungo.

    Tutto questo in sostanza vuol dire che il criterio di ordinamento deve far parte del BST. Ovvero, quando crei un BST gli devi assegnare un criterio di ordinamento e quello deve restare tale per tutta la "vita" del BST.
    Il criterio non può cambiare né per l'inserimento né per la ricerca, perché è il criterio di ordinamento che struttura l'albero!

    Detto questo, la tua ultima definizione, ovvero:

    public class BST<T implements Comparator<T>{...}>

    semplicemente NON ha senso (è anche sbagliata, si usa extends non implements con i bound). Il T è il "segnaposto" per il tipo degli oggetti nell'albero. Applicare un bound (limite) con Comparator, non ha senso perché come detto prima, Comparator NON si implementa negli oggetti da comparare!

    Tecnicamente sarebbe più sensato se fosse:

    public class BST<T extends Comparable<T>>

    o in forma leggermente un po' più ampia

    public class BST<T extends Comparable<? super T>>

    Ma c'è una questione di concetto: io potrei voler mettere nel BST degli oggetti che NON implementano Comparable (es. dei java.net.URL) volendo però usare un Comparator. Ma gli oggetti, con quel bound, NON ci entrerebbero proprio! (per meglio dire: è il compilatore che non lo accetterebbe)

    Quindi ricapitoliamo:
    - si vuole stabilire il criterio di ordinamento SOLO con un Comparator esplicito (non è il caso più flessibile ma è lecito)
    - come detto prima, il criterio DEVE far parte del BST.

    Pertanto la cosa logica da fare è tenere il Comparator come attributo nel BST.
    public class BST<T> {
        private Comparator<? super T> comparatore;
    
        public BST(Comparator<? super T> comparatore) {
            this.comparatore = comparatore;
        }
    
        // .......
    }
  • Re: Comparator

    Ciao @andbin
    Grazie per la risposta, come sempre. Bene o male le differenze tra conparable e comparator mi sono chiarea, ma per essere sicuri, riassumiamo con parole semplici.
    Il comparable si usa in quelle classi dove poi io vglio fare un confronto tra i suoi oggetti, per rsempio ho la classe cane, e per poter confrontare 2 oggetti cane, allora devono essere comparable.
    Il comparator invece si usa in una classe che deve fare questi confronti.
    Ma sono 2 classi astratte se non erro, quindi il compare di comparator lo devo sovrascrivere se non erro. Pervhè nel costruttore dell'albero passi un oggetto comparator?
  • Re: Comparator

    KuroKami69 ha scritto:


    Bene o male le differenze tra conparable e comparator mi sono chiarea, ma per essere sicuri, riassumiamo con parole semplici.
    Il comparable si usa in quelle classi dove poi io vglio fare un confronto tra i suoi oggetti, per rsempio ho la classe cane, e per poter confrontare 2 oggetti cane, allora devono essere comparable.
    Il comparator invece si usa in una classe che deve fare questi confronti.
    Comparable si implementa nella stessa classe degli oggetti da comparare. Se hai una classe Libro e vuoi implementare Comparable, allora:

    public class Libro implements Comparable<Libro> { ...... }

    Dal momento che è nella classe degli oggetti da comparare, di Comparable ce ne può essere solo uno, ovvero può essere implementato una volta sola. Il criterio di comparazione con Comparable dovrebbe essere generalmente/tipicamente l'ordinamento "naturale" degli oggetti. Quale che sia dipende chiaramente dal significato della classe. Nel caso di Libro l'ordinamento naturale con Comparable potrebbe essere molto ragionevolmente per titolo del libro. Nel caso di una classe Persona potrebbe essere l'ordinamento classico per cognome/nome, ecc...

    Comparator invece si implementa in classi distinte dalla classe degli oggetti da comparare e quindi di criteri di ordinamento con Comparator ne puoi definire quanti ne vuoi!

    public class LibroPerAnnoPubblicazioneComparator implements Comparator<Libro> { ...... }

    public class LibroPerEditoreETitoloComparator implements Comparator<Libro> { ...... }

    public class LibroPerTipologiaETitoloComparator implements Comparator<Libro> { ...... }

    ecc.....

    KuroKami69 ha scritto:


    Ma sono 2 classi astratte se non erro
    Sono due interfacce.

    KuroKami69 ha scritto:


    Pervhè nel costruttore dell'albero passi un oggetto comparator?
    Perché così il BST riceve un oggetto (ovviamente sarà di una classe concreta che implementa Comparator) che rappresenta la "funzione" di comparazione tra due oggetti.
  • Re: Comparator

    Quindi se ho ben capito, mi dovrò fare una classe interfaccia che sarà il mio comparator, e poi lo dovrò usare nel BST giusto?
    onestamente comunque mi sfugge il perché ci hai messo il comparator nel costruttore della classe.
    se nel BST voglio immagazzinare dati diversi, interi, stringhe etc, questi vanno nella parte data del nodo, che viene creato dal BST. sostanzialmente io dovrei creare una classe, che ne so, Oggetto (tanto per dire un nome), che implementa comparator, che verrà poi passato come data del nodo?
  • Re: Comparator

    KuroKami69 ha scritto:


    Quindi se ho ben capito, mi dovrò fare una classe interfaccia che sarà il mio comparator
    "Nì". Tecnicamente certo che potresti farti una tua interfaccia di comparazione, è banale. Ma nel framework c'è già, è java.util.Comparator. Quindi perché farne un'altra??

    KuroKami69 ha scritto:


    onestamente comunque mi sfugge il perché ci hai messo il comparator nel costruttore della classe.
    se nel BST voglio immagazzinare dati diversi, interi, stringhe etc, questi vanno nella parte data del nodo, che viene creato dal BST. sostanzialmente io dovrei creare una classe, che ne so, Oggetto (tanto per dire un nome), che implementa comparator, che verrà poi passato come data del nodo?
    Ma allora scusa, forse NON hai ancora capito come funziona un BST (o in italiano ABR, "albero binario di ricerca") !

    In un BST, il nodo figlio sx è "minore" del nodo padre mentre il nodo figlio dx è "maggiore" del nodo padre. Questo NON è fatto così a caso, tanto per fare. Perché quando fai una ricerca nell'albero, questa logica ti permette di "scendere" nell'albero individuando ad ogni nodo da che parte andare, escludendo quindi il resto.

    Hai visto l'albero di esempio prima con "arancia", "mela", ecc..?? Bene, hai in memoria quel BST e vuoi cercare se è presente "cocco". Come ho mostrato, quell'albero contiene stringhe che nel BST sono ordinate secondo un criterio di comparazione che si basa sulla lunghezza delle stringhe.

    Quindi confronti innanzitutto "cocco" con la radice ("arancia"). Sul comparatore verrà invocato compare("cocco", "arancia"). Se la implementazione del Comparator si basa sulla LUNGHEZZA, restituirà <0 ("cocco" è più corto!).
    Quindi andrai verso SX e nota bene, tutto il ramo DX sotto "arancia" lo puoi completamente ignorare.

    Poi confronti "cocco" con "mela", il compare restituirà >0 ("cocco" è più lungo). Quindi andrai verso DX (e idem, tutto ciò che può stare a sx sotto "mela" lo puoi ignorare).

    Poi confronti "cocco" con "cocco". Il compare restituirà 0, hai trovato l'elemento!
  • Re: Comparator

    Certo che ho capito come funziona il BST, quello che non ho capoto è come funziona conparator. Se passo 2 oggetto che hanno uno 5 valori e uno 3, su cosa si basa il confronto? Se io passo un oggetto che ha una stringa e uno che ha un boolean, in base a cosa fa il confronto? Se io nel mio BST voglio passare, tanto per fare un qualcosa di inutile, deglil oggetti che mi rappresentano frutti diversi, e poi ci paaso degli oggetti con delle figre geometriche, e poi perchè mi gira male ci passo pure delle espressioni matematiche atte alla risoluzione, il confronto su cosa lo fa? Come lo fa? Ma sto dicendo un sacco di cavolate perchè con i generics quando creo un BST, quello accetterá solo un tipo di oggetto per volta. Tornando alla prima domanda, se passo degli oggetti frutto, con diversi attributi, il confronto come avviene? Su cosa lo fa? Parlo per l'inserimento, non per la ricerca
  • Re: Comparator

    KuroKami69 ha scritto:


    quello che non ho capoto è come funziona conparator.
    Allora ti conviene subito affrontare Comparable/Comparator perché sono concetti "importanti" usati in svariate collezioni e nei vari algoritmi forniti dal framework quali i sort/min/max/binarySearch e altro (nonché nella Stream API).

    KuroKami69 ha scritto:


    Se passo 2 oggetto che hanno uno 5 valori e uno 3, su cosa si basa il confronto?
    Comparable/Comparator hanno 1 metodo, che opera su 2 oggetti (per il compareTo di Comparable uno è "implicito" cioè l'oggetto su cui si invoca compareTo, per il compare di Comparator sono entrambi espliciti come argomenti).

    Le implementazioni di queste due interfacce sono molteplici e dipendono ovviamente dal significato della classe degli oggetti (es. Persona, Libro, ecc...) e dal criterio che si vuole applicare.

    Nel caso di un comparatore dal nome LibroPerAnnoPubblicazioneComparator, il compare andrà ad invocare un es. getAnnoPubblicazione() sui due oggetti ricevuti e compara i due anni per restituire <0 / 0 / >0

    Nel caso di un comparatore dal nome LibroPerEditoreTitoloComparator, il compare andrà ad invocare un es. getEditore() sui due oggetti ricevuti. Confronta le due stringhe, se una è minore/maggiore dell'altra hai già il risultato. Se sono uguali, andrà ad invocare un es. getTitolo() sui due oggetti e confronta i titoli per restituire <0 / 0 / >0

    Ma a chi USA un Comparator, tutto questo generalmente NON importa. Chi riceve/ha il riferimento ad un Comparator tipicamente NON sa nemmeno di che tipo sono gli oggetti (per via dei generics e della erasure). Sa solo che il Comparator ne può comparare due, quindi dice sostanzialmente al compare(): "dimmi se l'oggetto A è minore/maggiore/uguale dell'oggetto B". E sulla base del risultato operare di conseguenza (a seconda dell'algoritmo, es. un sort, un "min", un binary-search ecc...)
    Stop, tutto lì.

    KuroKami69 ha scritto:


    Se io passo un oggetto che ha una stringa e uno che ha un boolean, in base a cosa fa il confronto?
    Che di per sé non ha granché senso. Se vuoi dargliene uno tu "fittizio" di senso (per qualche motivo che potrei non sapere io), del tipo: i boolean vengono prima delle stringhe e true viene prima di false ... sei libero di farlo. Ma se lo fai devi avere ben chiaro perché.

    KuroKami69 ha scritto:


    Se io nel mio BST voglio passare, tanto per fare un qualcosa di inutile, deglil oggetti che mi rappresentano frutti diversi, e poi ci paaso degli oggetti con delle figre geometriche, e poi perchè mi gira male ci passo pure delle espressioni matematiche atte alla risoluzione, il confronto su cosa lo fa? Come lo fa?
    Idem.
  • Re: Comparator

    Credo di aver più o meno capito. Forse mi sto facendo confusione con gli esempi che ho visto su internet, ma ho visto che il metodo compare() lo overiddano sempre. Ho bisogno di farlo anche io quindi? Da quello che hai scritto te, posso intendere di si, ma solo per casi specifici. oppure mi basta semplicemente chiamare il compare e passare i 2 oggetti? Perchè per esempio, non so se è la stessa cosa, ma ho provato a fare 2 banalissimi oggetti con una stringa come unica variabile. Poi in un system.out ho chiamato il conpare(o1, o2) (le stringhe erano pippo e pluto) ma non mi dava 0, -1 o 1, mi dava solo valori positivi. Ho una grandissima confusione scusa
  • Re: Comparator

    KuroKami69 ha scritto:


    Forse mi sto facendo confusione con gli esempi che ho visto su internet, ma ho visto che il metodo compare() lo overiddano sempre.
    Se ti riferisci alla annotation @Override, è solo un pro-forma. Da Java 6 (in Java 5 no) è lecito mettere @Override anche nei metodi che implementano direttamente quelli di una interfaccia.
    Ma se implementi direttamente una interfaccia, non ci sono particolari "pericoli". Se implementi Comparator e ti sbagli a scrivere il metodo, es. scrivi Compare oppure commpare, o sbagli parametri o tipo di ritorno, semplicemente NON TI COMPILA proprio.
    Diciamo che se metti @Override sul compare, semplicemente hai 2 errori invece che 1 che ti avvertono che hai sbagliato nella implementazione.

    KuroKami69 ha scritto:


    Ho bisogno di farlo anche io quindi?
    Se vuoi DEFINIRE un criterio di comparazione, ovviamente DEVI implementarlo con Comparable (se è quello "naturale") o in classe esterna con Comparator.

    Esempio, hai una lista di stringhe (nomi di frutti), vuoi ordinarle con questo criterio: ordinate per lunghezza crescente e a parità di lunghezza, alfabeticamente in modo crescente.
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    public class ProvaCompare {
        public static void main(String[] args) {
            List<String> frutti = Arrays.asList("arancia", "mela", "pera", "uva", "albicocca", "mora", "fragola");
            System.out.println(frutti);
            Collections.sort(frutti, new MyStringLengthComparator());
            System.out.println(frutti);
        }
    }
    
    
    class MyStringLengthComparator implements Comparator<String> {
        @Override
        public int compare(String s1, String s2) {
            int r = Integer.compare(s1.length(), s2.length());  // confronta lunghezze
    
            if (r == 0) {
                r = s1.compareTo(s2);   // confronta stringhe
            }
    
            return r;
        }
    }
    L'output è:

    [arancia, mela, pera, uva, albicocca, mora, fragola]
    [uva, mela, mora, pera, arancia, fragola, albicocca]
  • Re: Comparator

    andbin ha scritto:


    Se vuoi DEFINIRE un criterio di comparazione, ovviamente DEVI implementarlo con Comparable (se è quello "naturale") o in classe esterna con Comparator.
    ok ma dato che non conosco a priori cosa viene inserito nel BST, non posso definire nulla.
    quindi mi basta semplicemente implementare l'interfaccia comparator, nel BST e richiamare il compare()?
  • Re: Comparator

    KuroKami69 ha scritto:


    ok ma dato che non conosco a priori cosa viene inserito nel BST, non posso definire nulla.
    Se tu vai poi a fare

    new BST<String>()

    lo sai cosa ci sarà dentro ... stringhe.

    Se scrivi

    new BST<Integer>()

    lo sai cosa ci sarà dentro ... interi Integer.

    E certo ... se scrivessi

    new BST<Object>()

    sarebbe molto "ampio" perché ci può stare qualunque cosa. Ma allora spetta a te valutare prima: a) perché e b) come definire la comparazione.

    Ma se hai tuo tipo specifico e sai come comparare i suoi oggetti .... non mi pare difficile comprendere il senso di es:

    new BST<Solido>(new VolumeSolidoComparator());

    Ovvero: voglio un BST di oggetti Solido comparati per il volume.

    KuroKami69 ha scritto:


    quindi mi basta semplicemente implementare l'interfaccia comparator, nel BST e richiamare il compare()?
    NO
  • Re: Comparator

    Comincio a farmi un'idea, ma ancora non ho chiara questa cosa.
    essendo il BST generico posso passargli sia un oggetto cubo, sia un oggetto testo. non posso fare un metodo di comparazione che vada bene per qualsiasi oggetto io ci metta dentro?
    voglio dire, come lo hai spiegato te, mi serve costruire un comparator per ogni attributo che voglio verificare, ma se appunto io faccio questo BST per te e non so per cosa lo usi, come implemento il comparator?
  • Re: Comparator

    KuroKami69 ha scritto:


    essendo il BST generico posso passargli sia un oggetto cubo, sia un oggetto testo.
    Alt. Il fatto che BST sia una classe "generica" (con l'uso dei generics) vuol dire innanzitutto che dovrà essere usata parametrizzata. In un BST<String> ci metti solo String. In un BST<Number> ci puoi mettere Integer, Long, Short ecc.. ma non String. In un BST<Solido> (ipotizzando Solido astratta) ci metti solo oggetti che sono sottotipi concreti di Solido, es. Cubo, Sfera, ecc... ma non String o Integer o altro.

    E se fai un BST<Object> .... sono affari tuoi. Nel senso che devi avere chiaro il perché e quali tipi di oggetti intendi trattare.

    KuroKami69 ha scritto:


    non posso fare un metodo di comparazione che vada bene per qualsiasi oggetto io ci metta dentro?
    . Puoi certamente fare un Comparator<Object> che "sa" di dover confrontare oggetti di vari tipi differenti (es. String, Integer, Boolean). Ma devi sapere TU quali tipi trattare. Non puoi fare un comparatore per "qualunque" tipo arbitrario che magari non conosci neanche o non è sotto il tuo controllo!

    KuroKami69 ha scritto:


    ma se appunto io faccio questo BST per te e non so per cosa lo usi, come implemento il comparator?
    Tu che scrivi la classe BST, NON sei tu che devi implementare il comparatore. Il comparatore lo dovrà implementare chi vorrà USARE la tua classe BST dato che, come ho detto prima, per istanziarlo dovrà passare una implementazione del comparatore.

    Il tuo BST semplicemente opererà "in funzione" di un Comparator che riceverà.

    ----------------------
    P.S. Se Comparator non ti fosse ancora chiaro, suggerisco un piccolo "esercizio".
    Fai prima un semplice metodo "min" su valori int con questa forma:

    public static int min(int[] array)

    Che è davvero banale (puoi anche ignorare i casi particolari es. quando l'array è vuoto).
    Poi prova a fare un min "generico" che usa Comparator:

    public static <T> T min(T[] array, Comparator<? super T> comp)

    Poi per provarlo, usa un array con i "frutti" del mio esempio precedente e quel MyStringLengthComparator.
    Se riesci a farlo, allora hai capito Comparator (non puoi non averlo capito se ci riesci ..).
  • Re: Comparator

    Daccordo, ci proverò appena riesco a essere a casa tranquillo, grazie
    Comunque io intendevo che dato che devo farlo come esercizio scolastico il BST, sarò poi io a usarlo, quindi sarò comunque io a dover implementare comparator
Devi accedere o registrarti per scrivere nel forum
14 risposte