Inserimento mantenendo ordine in TREEMAP

di il
14 risposte

Inserimento mantenendo ordine in TREEMAP

Salve a tutti,
ho una domanda riguardante i TreeMap.
Io ho un certo numero di elementi generici di tipo E; devo gestire questi elementi inserendoli in un TreeMap<E, Integer> per poi operarci sopra successivamente.
Nel mio caso il campo Integer associato ad ogni elemento E rappresenta il suo numero di occorrenze.
Per comodità vorrei creare questo albero già ordinato in modo tale da non dover compiere l'operazione in seguito.
L'ordine che voglio imporre è dall'elemento con più occorrenze (quindi con campo Integer maggiore) all'elemento con meno ed, in caso di parità, da quello con campo E maggiore a quello minore.
Leggendo la documentazione mi sono accorto che l'unico modo che ho per creare questo treemap, rispettando l'ordinamento da me voluto, è quello con il costruttore
public TreeMap(SortedMap<K,? extends V> m)
Veniamo al mio problema: se una volta costruito il mio albero, volessi aggiungerci un altro elemento in un secondo momento, come potrei inserirlo e mantenere l'ordinamento?
Esiste un modo?
Grazie a tutti in anticipo

14 Risposte

  • Re: Inserimento mantenendo ordine in TREEMAP

    riccac ha scritto:


    Per comodità vorrei creare questo albero già ordinato in modo tale da non dover compiere l'operazione in seguito.
    TreeMap MANTIENE (e SEMPRE) le chiavi ordinate. Può farlo presupponendo che gli oggetti-chiave implementino Comparable. Oppure specificando un opportuno Comparator esplicito.

    Quindi:
    a) I tuoi oggetti-chiave implementano Comparable ---> nulla di particolare: usi il costruttore TreeMap()
    b) I tuoi oggetti-chiave NON implementano Comparable oppure vuoi un criterio differente ---> implementi un Comparator e usi il costruttore TreeMap(Comparator<? super K> comparator)
  • Re: Inserimento mantenendo ordine in TREEMAP

    Grazie andbin, però ci sono delle cose che non capisco nella tua risposta.
    Che il TreeMap mantenga sempre l'ordinamento rispetto alle chiavi va bene, ma è proprio quello il mio problema.
    Io voglio che un inserimento successivo alla chiamata del costruttore mantenga un ordinamento da me stabilito: ordine decrescente delle ocorrenze (valori ) e, a parità di valori, dalla chiave più grande alla più piccola.
    La soluzione b che mi hai proposto non fa comunque al caso mio perchè decido io come ordinare i vari elementi, ma solamente in base alle chiavi, non in base ad un "misto" di valori e chiavi, come serve a me...sbaglio? Grazie comunque dell'aiuto
  • Re: Inserimento mantenendo ordine in TREEMAP

    riccac ha scritto:


    Che il TreeMap mantenga sempre l'ordinamento rispetto alle chiavi va bene, ma è proprio quello il mio problema.
    Io voglio che un inserimento successivo alla chiamata del costruttore mantenga un ordinamento da me stabilito: ordine decrescente delle ocorrenze (valori ) e, a parità di valori, dalla chiave più grande alla più piccola.
    La soluzione b che mi hai proposto non fa comunque al caso mio perchè decido io come ordinare i vari elementi, ma solamente in base alle chiavi, non in base ad un "misto" di valori e chiavi, come serve a me...sbaglio? Grazie comunque dell'aiuto
    Credo che non hai compreso Comparable/Comparator. Leggi perché ne ho parlato sul forum appena qualche settimana fa.

    Detto questo (e dopo che hai letto quello), sappi che TreeMap mantiene ordinate le CHIAVI (non c'entrano i valori!) basandosi su un criterio di ordinamento che può essere definito da Comparable O Comparator. E il criterio lo definisci TU.
  • Re: Inserimento mantenendo ordine in TREEMAP

    Scusa andbin, mi sono letto quello che mi hai linkato e mi sono andato anche a cercare degli esempi online...ma continuo a non capire una cosa: come posso ordinare nel modo che serve a me se il comparatore è solamente sulle chiavi???
    Non capisco cosa mi stai cercando di far capire perdonami.
    TreeMap(Comparator<? super K> comparator) questo non vuole dire che il comparatore è solo per le chiavi??
  • Re: Inserimento mantenendo ordine in TREEMAP

    riccac ha scritto:


    come posso ordinare nel modo che serve a me se il comparatore è solamente sulle chiavi???
    TreeMap "sa" solo mantenere ordinate tutte le sue entry (chiave-valore) per la CHIAVE. E il criterio dell'ordinamento è dato da Comparable O Comparator applicato alle CHIAVI.

    Nessuno però ti impedisce di fare un "barbatrucco". In un tuo Comparator quando ti viene chiesto di comparare le chiavi es. C1 vs C2, tu vai a prendere i valori associati V1 e V2 (presuppone che il comparatore abbia il riferimento alla mappa, questo è l'aspetto meno bello), compari i VALORI e poi dici con il valore di ritorno del compare() se C1 è minore/uguale/maggiore di C2.

    Non è molto bello in generale (e non si fa quasi mai una cosa del genere). Se devi arrivare a questo .... probabilmente un TreeMap non è la struttura più appropriata o forse c'è dell'altro da valutare.
  • Re: Inserimento mantenendo ordine in TREEMAP

    OK ora ho capito cosa intendevi, in effetti funzionerà come soluzione ma non mi sembra quella con più stile.
    Purtroppo devo usare per forza un TreeMap come struttura perchè sto facendo un progetto.
    Grazie mille per l'aiuto andbin.
  • Re: Inserimento mantenendo ordine in TREEMAP

    Da quello che hai scritto, stai implementando un Bag, cioe' un Set in cui tieni traccia del numero di volte che un certo item e' stato inserito/rimosso dal Bag (il numero di occorrenze) e vuoi, inoltre, mantenere tale struttura ORDINATA per numero di OCCORRENZE.

    In Set e' come un Bag, in cui l'unica infomazione che ti serve sapere e' se l'elemeno e' presente nel set oppure no, NON il numero di volte in cui e' presente.

    NON SI PUO FARE con una sola struttura dati, DEVI implementare una TUA struttura dati che combina almeno DUE altre strutture dati:

    1) un generico HasMap<Item,Integer> per mantenere la coppia <item,numero di occorrenze>. In questo caso non ti serve nessun particolare ordine
    2) un TreeMap<Integer,List<Item>> per manterere l'ordine per numero di occorrenze (NOTA che ho scritto List<Item> NON Item)

    3) quindi implementare le operazioni

    - add(Item)
    - add(Item, count)
    - remove(Item)
    - remove(Item,count)
    - contains(item)
    - count(Item)
    - inRange(minCount,maxCount)

    in modo opportuno.

    La soluzione di usare un TreeMap in cui l'ordine viene fatto sul VALORE e NON sulla chiave e' TOTALMENTE SBAGLIATA.
    Ci si potrebbe scrivere un libro nell'elencare tutti i motivi, ma il piu' semplice e':

    quella struttura dati NON SI USA IN QUEL MODO

    Se insisti nell'utilizzare il TreeMap<Item,Integer>, la cosa e' fattibilissima, ma

    L'ORDINE DEVE ESSERE FATTO SULLE CHIAVI, NON SUI VALORI!
  • Re: Inserimento mantenendo ordine in TREEMAP

    riccac ha scritto:


    Purtroppo devo usare per forza un TreeMap come struttura perchè sto facendo un progetto.
    Allora devi fare per forza così. Una implementazione di Comparator che possiede il riferimento alla TreeMap e ad ogni invocazione di compare() fai un "lookup" dei valori, così che puoi considerare per il criterio sia chiavi che valori.

    Ripeto: non è bellissimo ma tecnicamente "si fa".
  • Re: Inserimento mantenendo ordine in TREEMAP

    @adbin: NON SI FA

    Evitiamo di dare indicazioni false e tendenzione a persone inesperte:ci sono un sacco di rogne con il tuo approccio.

    Te ne fornisco uno:
    concettualmente si dovrebbe avere: compare(K1,K2) == 0 SE E SOLO SE K1==K2
    ora se hai K1 <> K2 MA compare(K1,K2) == 0, il comportamento della struttura dati DIPENDE dalla particolare implementazione fatta, NON da un particolare requirement.

    Nel momento in cui DIPENDI da una particolare implementazione, NON C'E' NESSUNA GARANZIA che usando versioni diverse di Java questo comportamento venga mantenuto.

    Altro problema: l'ordine NON E' DINAMICO, ma viene utilizzato quando un element viene inserito nella struttura.
    SE uno AGGIORNA SOLO il contatore, NON VIENE AUTOMATICAMENTE AGGIORNATO l'ordine della chiave all'interno della struttura, PERCHE' la chiave NON E" STATA coinvolta. Come conseguenza, la chiave mantine el'ordine del PRIMO inserimento, ANCHE se il contatore e' cambiato.

    Ci sono altre N-MILA rogne, che non sto qui' ad elencare ...

    Tranquillo, e' capitato: il classico programmatore alle prime armi si e' basato sull'ordine di inserimento mantenuto dalla HashTable in una delle prime implementazionei in Java. Quando abbiamo aggiornato la VM ci siamo trovati con l'applicazione non funzionava piu'.
    Ho perso quasi un mese per capire dove stesse il problema.
  • Re: Inserimento mantenendo ordine in TREEMAP

    migliorabile ha scritto:


    @adbin: NON SI FA

    concettualmente si dovrebbe avere: compare(K1,K2) == 0 SE E SOLO SE K1==K2
    ora se hai K1 <> K2 MA compare(K1,K2) == 0, il comportamento della struttura dati DIPENDE dalla particolare implementazione fatta, NON da un particolare requirement.
    Lo so che non si dovrebbe mai fare ... non devi dirlo a me.

    La documentazione di TreeMap è molto chiara:

    Note that the ordering maintained by a tree map, [....], must be consistent with equals if this sorted map is to correctly implement the Map interface.

    Poi dice anche per completezza:

    This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method

    E va bene. Poi però dice anche:

    The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

    Ovvero: PUO' anche essere inconsistente con equals, TreeMap non ha problemi di per sé .... semplicemente così fallisce nel rispettare il contratto generale di Map.
    Ora: è un problema se fallisce in questo contratto di Map? La risposta è semplice per me: DIPENDE

    Se io faccio un TreeMap con ordine "particolare" come detto prima basato anche sui valori e poi lo passo ad una API, libreria o che altro (non sotto il mio controllo comunque) che "vede" la mappa magari solo come Map e si aspetta una consistenza con equals .... qui CERTO che è un problema.

    Ma se il TreeMap è "mio", lo uso solo io, non ci devo fare alcuna generalizzazione, non mi interessa fare alcuna considerazione sulla uguaglianza delle chiavi con equals ..... beh, tecnicamente è tutto sotto il mio controllo e come caso limite si può tecnicamente fare.

    Non so se per @riccac può andare bene o no, io ovviamente NON ho visione completa di cosa deve fare e perché.
  • Re: Inserimento mantenendo ordine in TREEMAP

    La questione e' molto semplice: se io e te possiamo anche ABUSARE di un particolare comportamento, perche' SAPPIAMO che cosa stiamo facendo, questo non e' valido per chi e' alle prime armi,e che deve fare un esercizio per IMPARARE ad usare queste strutture dati.

    Meglio EVITARE di fornire TRICK che la controparte non sarebbe in grado di gestire (se non funziona, come modificare il TRICK per ottenere il risultato voluto? )
  • Re: Inserimento mantenendo ordine in TREEMAP

    migliorabile ha scritto:


    se io e te possiamo anche ABUSARE di un particolare comportamento, perche' SAPPIAMO che cosa stiamo facendo
    Io e te sì, sappiamo cosa facciamo.

    migliorabile ha scritto:


    Meglio EVITARE di fornire TRICK che la controparte non sarebbe in grado di gestire
    Ok d'accordo.

    @riccac:
    A questo punto (e ripeto, NON sapendo bene obiettivi/motivazioni di cosa devi fare), come suggerimento: perché non usare una lista di oggetti (dove ciascun oggetto ha tutte le informazioni utili) da tenere e mantenere ordinata secondo la tecnica del "binary-search"? Ci sarebbero ovviamente cose da valutare a riguardo.

    P.S. sempre per @riccac: prova a spiegare meglio COSA devi fare in generale.
  • Re: Inserimento mantenendo ordine in TREEMAP

    Allora io dovevo fare una classe che passato in input un file di testo, memorizzasse dentro a un TreeMap (capisco non sia la struttura dati più adatta a quello che devo fare, però è una consegna e dovrei rispettarla) ogni parola e la relativa occorrenza nel file.
    Tra i vari metodi da implementare c'è incCount(string), che incrementa di uno l'occorrenza del parametro data, se presente, altrimenti lo inserisce e setta a 1 il suo numero di occorrenze.
    Devo implementare anche un iteratore, ed è per questo che volevo crearmi un albero "ordinato" secondo il mio criterio: così non avrei dovuto copiare il mio albero in un set (con tree.entrySet()) e ordinare il set con un mio comparatore (in modo tale che l'iteratore visiti gli elementi ordinati), ma avrei solamente copiato l'albero nel set e iterato subito.
    Per questo chiedevo se ci fosse un modo per inserire un elemento in un albero, rispettando comunque un ordinamento da me scelto.
    Non era una questione particolarmente importante, era solo che mi piaceva di più come soluzione.
  • Re: Inserimento mantenendo ordine in TREEMAP

    riccac ha scritto:


    Allora io dovevo fare una classe che passato in input un file di testo, memorizzasse dentro a un TreeMap ogni parola e la relativa occorrenza nel file.
    Ascolta, se vuoi avere una "mappa" che associa parola-->n.occorrenze allora TreeMap va anche bene e senza fare nulla di particolare di per sé terrebbe ordinate le parole. Se alla fine di tutta la analisi delle occorrenze vuoi ottenere un elenco delle parole ordinate per OCCORRENZE, TreeMap non va molto bene, nel senso che considerare anche i valori nel criterio di ordinamento, tecnicamente si fa ma NON è una buona cosa (come ampiamente detto).

    Si può fare questo in altri modi. Ma qui bisogna vedere COSA puoi usare. Se ti è stato imposto di usare 1 solo TreeMap ... allora forse l'esercizio è posto/fatto male. Se avessi maggiore libertà si può vedere ...
Devi accedere o registrarti per scrivere nel forum
14 risposte