[JAVA]Aiuto! ArrayList in restituzione di una ricerca?

[giogts]

Premetto che sono agli inizi con java,
Per una applicazione (raccolta punti promossa da un’azienda)dovrei svolgere questo caso d'uso:
l’applicazione cerca i premi con il maggior numero di richieste;
Per fare questo, ho scritto il seguente metodo:

public ArrayList<Premio> cercaPremiPiuRichiesti() {
        assert (elencoPremi.size() != 0) : "Attenzione! Non ci sono premi!";
        ArrayList<Premio> risultato = new ArrayList<Premio>();        
        for (int i = 0; i < elencoPremi.size()-1; i++) {
            Premio premio = this.getPremio(i);
            Premio premioSuccessivo = this.getPremio(i+1);
            if (premio.getRichieste() > premioSuccessivo.getRichieste()) {
                risultato.add(premio);
            }
        }
        return risultato;
    }

Ora il problema è che mi restituisce la lista risultato che ha sempre e solo un oggetto, il primo che trova nel confronto; quando in realtà dovrebbero essere due o più i premi che hanno il numero di richieste più alte, per esempio due premi hanno 8 richieste, e che quindi dovrebbero finire nella lista!
Non so se sono riuscito a spiegarmi bene, ma praticamente non riesco a farmi restituire da un confronto(l'if) una lista di oggetti, dove sto sbagliando?

Vi metto anche il metodo (del controllo) che stampa il risultato:

private void schermoCercaPremiPiuRichiesti(Collezione collezione) {
        System.out.println("---------------------------------");
        System.out.println("   Ricerca Premi più richiesti   ");
	System.out.println("---------------------------------");
        ArrayList<Premio> risultato = collezione.cercaPremiPiuRichiesti();
         System.out.println("Risultato della ricerca: ");
        for (Premio premio : risultato) {
            System.out.println(premio);
        }
}

[Morfeo XP]

L'algoritmo con il quale fai la ricerca dei premi più richiesti non è corretto.
Innanzitutto dovresti stabilire il numero di premi più richiesti che il metodo deve restituire o in alternativa i premi con più di n richieste. Ad esempio i 3 premi più richiesti o i premi con più di 100 richieste.

[banryu79]

E in ogni caso nella libreria del JDK c'è una interfaccia che si chiama Comparable (c'è anche Comparator): implementandola ti semplificheresti non poco il lavoro di riordino di una collezione di oggetti delle stesso tipo secondo un criterio da te definito.

Ad esempio:
- devo ordinare una collezione di oggetti Premio
- il criterio di ordinamento tra gli oggetti Premio è per numero di richieste, in ordine discendente.

Implemento nella mia classe Premio l'interfaccia Comparable

public class Premio implements Comparable
{
   // membri di istanza...

   // costruttore...

   // metodi di istanza...
  
  // implementazione metodo compareTo definito in Comparable
  // supponendo che il metodo getRichieste() torni un intero 
  public int compareTo(Premio other)
  {
       // così stabilisce un ordine ascendente
       // return  this.getRichieste() - other.getRichieste();

       // così stabilisce un ordine discendente:
       return  other.getRichieste() - this.getRichieste();
  }

}

Faccio riordinare una collezione di oggetti Premio dalla classe Collections nel JDK (java.util.Collections)

//... ove appropriato, nell'applicazione:

// elencoPremi è un ArrayList<Premio> contenente i vari premi in ordine sparso
Collections.sort(elencoPremi);

// ora elencoPremi è ordinato secondo il criterio che abbiamo stabilito
// nell'implementazione dell'interfaccia Comparable nella classe Premio
// cioè in ordine discendente: elencoPremi.get(0) torna il Premio con maggiori richieste.

Tenendo poi conto delle indicazioni che ti ha dato Morfeo XP e supponendo si debba restituire i primi N premi con maggiori richieste:

public ArrayList<Premio> cercaPrimiPremi(int N) 
{
    assert (elencoPremi.size() != 0) : "Attenzione! Non ci sono premi!";
    assert (N > 0 && N <= elencoPremi.size()) : "Numero premi richiesti non valido";
    
    ArrayList<Premio> primiPremi = new ArrayList<Premio>(N);        
    
    int loopCounter = 0;
    Iterator<Premio> iterator= elencoPremi.iterator();
    while(loopCounter < N  &&  iterator.hasNext())
    {
        primiPremi.add(iterator.next());
    }
    return  primiPremi;
}

Supponendo invece si debbano restituire tutti i premi che abbiano almeno N richieste o più:

public ArrayList<Premio> cercaPremiConRichieste(int numRichieste) 
{
    assert (elencoPremi.size() != 0) : "Attenzione! Non ci sono premi!";
    assert (numRichieste > 0) : "Numero richieste specificate per i premi non valido";
    
    ArrayList<Premio> premiFiltrati = new ArrayList<Premio>();        
    
    // essendo elencoPremi gia' ordinato in ordine discendente basta
    // continuare a inserire tutti i Premi incontrati dal primo in poi fino a che
    // presentano il numero minimo di richieste desiderato 

    Iterator<Premi> iterator = elencoPremi.iterator();
    while (iterator.hasNext())
    {
        Premio candidato = iterator.next();

        if (candidato.getRichieste() < numRichieste)
        {
             break;
        }
       
        premiFiltrati.add(candidato);
    }

    return  premiFiltrati;
}

[giogts]

grazie 1000 ad entrambi, però io non ho bisogno di stabilire il numero di premi più richiesti che il metodo deve restituire o i premi con più di n richieste, primo perchè non è richiesto dalle specifiche, e per questo non vorrei complicarmi troppo la vita, e secondo perchè i premi li immette l'utente all'inizio, quindi il metodo non saprà mai a priori quanti premi ci sono e quanti dovranno essere inseriti nel risultato....
per questo mi sembra superfluo ordinare la lista o stabilire quanti premi dovranno essere restituiti,

vi faccio un esempio,
premio1: friggitrice, richieste 8
premio2: pirofila, richieste 7
in questo caso il metodo dovrebbe restituire un arraylist con solo un elemento, cioè la friggitrice.

premio1: friggitrice, richieste 6
premio2: pirofila, richieste 6
premio3: orologio, richieste 3
premio4: felpa, richieste 6
in questo caso il metodo dovrebbe restituire un arraylist con 3 oggetti, cioè quelli che hanno il numero più alto di richieste(che è 6)

vorrei evitare l'uso di comparatori e iteratori (prematuro per il livello dell'esercizio)
quello che mi blocca è cosa devo scrivere dentro l'if per confrontare le richieste di un premio con le richieste di un altro premio

[Morfeo XP]

Cosa dovrebbe restituire in questo caso?

premio1: friggitrice, richieste 6
premio2: pirofila, richieste 4
premio3: orologio, richieste 3
premio4: felpa, richieste 5
premio5: borsone, richieste 5

[banryu79]

Originariamente inviato da Morfeo XP

Cosa dovrebbe restituire in questo caso?

premio1: friggitrice, richieste 6
premio2: pirofila, richieste 4
premio3: orologio, richieste 3
premio4: felpa, richieste 5
premio5: borsone, richieste 5

Se non ho capito male dovrebbe restiuire solo un premio: friggitrice, 6, giusto?
Cioè torna sempre e solo l'istanza(o le istanze) con il valore di richieste maggiore.

[giogts]

Originariamente inviato da banryu79

Se non ho capito male dovrebbe restiuire solo un premio: friggitrice, 6, giusto?
Cioè torna sempre e solo l'istanza(o le istanze) con il valore di richieste maggiore.

esatto, solo il premio (o i premi) con il numero di richieste maggiore

[banryu79]

metodo 1: con Comparable e Colloctions.sort(), come sopra, quindi iteri prendendo il maggiore (primo elemento) e continui a prendere elementi finchè quello successivo ha valore uguale a quello attuale in termini di numero richieste.

metodo 2: by hand, devi comunque ordinare, perchè non ti basta prendere un elemento il cui valore sia il maggiore ma bensì tutti gli elementi (uno o più) il cui valore sia il maggiore.

// ordina la collezione dei premi, quindi torna la lista dei premi con il maggior
// numero di richieste:
public ArrayList<Premio> cercaPremiPiuRichiesti(ArrayList<Premio> listaPremi)
{
    assert(listaPremi.size() > 0 bla bla bla...);

    ArrayList<Premio> sortedList = mergeSort(listaPremi);
    // ora sortedList contiene i Premi ordinati per richieste, in ordine discendente.
    // chiaramente il metodo mergeSort() te lo devi implementare tu, se non ti puoi appoggiare alle classi del JDK
    
    ArrayList<Premio> result = new ArrayList<Premio>(1);
    
    int index = 0;
    int maxValue = -10000;
    while (index < sortedList.size())
    {
        Premio premio = sortedList.get(index);
        
        if (premio.getRichieste() < maxValue)
            break;

        maxValue = premio.getRichieste();
        result.add(premio);
        index++;
    }

    return result;
}

[Morfeo XP]

Perfetto. Abbiam chiarito il discorso riguardante i premi con il maggior numero di richieste...

Per cercare il premio o i premi con il maggior numero di richieste potresti adottare un ArrayList ordinato, come proposto da banryu79, oppure fare una doppia scansione dell'ArrayList (non ordinato). La prima scansione per cercare il premio con la maggior richiesta e la seconda per trovare ed inserire nel ArrayList da restituire, i premi (o il premio) con la maggiore richiesta.
Ovviamente è possibile fare una sola scansione dell'ArrayList per cercare i premi con maggior richiesta, ma visto che il numero di premi sicuramente non sarà maggiore di 50, si possono adottare soluzioni non ottimali.

[banryu79]

Originariamente inviato da Morfeo XP

... visto che il numero di premi sicuramente non sarà maggiore di 50...

E questo dove sta scritto? Cioè, io non lo sapevo

[Morfeo XP]

E' solo una mia supposizione...

[banryu79]

Originariamente inviato da Morfeo XP

E' solo una mia supposizione...

Ah, beh, sono rimasto spiazzato dalla parola "sicuramente"... Alla faccia della supposizione

[giogts]

grazie proverò in entrambi i modi, poi vi faccio sapere quale scelgo

[giogts]

rieccomi, ho deciso di utilizzare i due cicli per le due scansioni dell'ArrayList, in modo da non utilizzare cose non ancora studiate, e che quindi non dovrei usare, praticamente ho fatto così:

public ArrayList<Premio> cercaPremiPiuRichiesti() {
        assert (elencoPremi.size() != 0) : "Attenzione! Non ci sono premi!";
        ArrayList<Premio> risultato = new ArrayList<Premio>();
        Premio p = elencoPremi.get(0);
        for (Premio premio : elencoPremi) {
            if (premio.getRichieste() > p.getRichieste()) {
                p = premio;
                risultato.add(p);
            } 
        }
        for (Premio premio : elencoPremi) {
            if (premio.getRichieste() == p.getRichieste()) {
                risultato.add(premio);
            }
        }
        return risultato;
    }

la maggior parte delle volte funziona bene, ma non capisco perchè a volte, cioè dopo che ho modificato le richieste di un premio, mi restituisce due volte lo stesso premio, cioè nel risultato mi trovo due elementi che sono lo stesso premio(cioè sia p che lo aggiungo nel primo ciclo e sia premio, che è uguale a p, dal secondo ciclo), dove sbaglio?

[banryu79]

public ArrayList<Premio> cercaPremiPiuRichiesti() {
        assert (elencoPremi.size() != 0) : "Attenzione! Non ci sono premi!";
        ArrayList<Premio> risultato = new ArrayList<Premio>();
        Premio p = elencoPremi.get(0);
        for (Premio premio : elencoPremi) {
            if (premio.getRichieste() > p.getRichieste()) {
                p = premio;
                risultato.add(p);
            } 
        }
        for (Premio premio : elencoPremi) {
            if (premio.getRichieste() == p.getRichieste()) {
                risultato.add(premio);
            }
        }
        return risultato;
    }

Nel primo ciclo usi un oggetto Premio (p) di appoggio per tenerti memorizzato l'ultimo premio con valore maggiore.

Nel secondo ciclo riutilizzi l'oggetto p (che attualmente punta a uno dei premi nell'array e incidentalmente è l'ultimo Premio che ha passato il controllo sulle richieste maggiori) per fare i confronti di uguaglianza con gli altri premi, solo che iteri di nuovo tutti i premi contenuti nell'array: ma almeno un Premio non lo devi confrontare: il Premio puntato da p stesso!

Altrimenti confronti un Premio (già inserito una volta in risultato) con se stesso e il confronto di uguaglianza passa per forza, così te lo ritrovi inserito una seconda volta.

[PGI-Bis]

Quello che hai scritto non funziona. Il primo ciclo accumula nella lista tutti i premi le cui richieste siano maggiori dell'ultimo inserito.

Il secondo aggiunge tutti quelli che le cui richieste siano uguali a quelle del premio più richiesto, tra cui il più richiesto precedentemente già inserito.

Il codice è sempre codice di qualcosa. Il qualcosa che devi codificare è, in questo caso, un algoritmo.

Prova a scandire idealmente il tuo array alla ricerca dei premi più richiesti.

[per ogni premio p nella lista premi]

se p è il primo elemento allora il suo numero di richieste è anche il massimo attuale.

[se p è il primo elemento allora aggiungo p ai risultati]

Nel caso in cui p non sia il primo elemento che succede?

Si danno tre casi: o le richieste di p sono maggiori del massimo (che è un qualsiasi elemento contenuto nei risultati), o sono minori del massimo o sono uguali al massimo.

Se è minore non ce ne frega nulla: a noi interessa il top del top.

[se p.richieste < delle richieste di un qualsiasi premio in risultati non si fa nulla]

Se è uguale allora è un risultato utile: è uno dei massimi richiesti

[se p.richieste = alle richieste di un qualsiasi premio in risultati allora aggiungo p ai risultati]

Se è maggiore allora abbiamo un nuovo massimo. Sappiamo che tutti gli elementi in risultati hanno lo stesso numero di richieste perchè questo ha fatto il nostro algoritmo fino ad adesso, quindi tutti i valori già accumulati vanno scartati, perchè non sono massimi, e il premio corrente viene aggiunto solo soletto ai risultati

[se p.richieste > delle richieste di un qualsiasi premio in risultati allora svuoto risultati e ci metto p]

Riepilogando, in pseudo codice meno pseudo di prima l'algoritmo è:

ArrayList risultati
per ogni elemento p di elencoPremi
	if risultati.size() == 0 //xchè risultati è vuoto solo se p è il primo elemento
		risultati.add(p)
	else if(p.richieste = risultati.get(0).richieste) 
		risultati.add(p)
	else if(p.richieste > risultati.get(0).richieste) 
		risultati.clear(), 
		risultati.add(p);
return risultati

E' giusto? Bisognerebbe darne una dimostrazione logica ma fortunatamente non sono in grado di farlo. Intuitivamente appare corretto.

E qui inizi a codificare, cioè a tradurre in codice java il tuo algoritmo.

[banryu79]

Originariamente inviato da PGI-Bis

Quello che hai scritto non funziona. Il primo ciclo accumula nella lista tutti i premi le cui richieste siano maggiori dell'ultimo inserito.

Ma porc... è vero, chiedo venia

[giogts]

Originariamente inviato da PGI-Bis

Quello che hai scritto non funziona.

ti assicuro che funziona, il primo ciclo prende correttamente il premio che ha il maggior valore di richieste, il problema credo che sia come dice banryu79, non dovrei includere p nel secondo ciclo di confronto, ma come faccio ad escluderlo?
inoltre non sono sicuro di aver capito la tua risposta
il fatto è che sono agli inizi, quindi magari non riesco ancora a capire il tuo ragionamento

[PGI-Bis]

Sei certo di non aver testato il metodo con una seguenza particolare di premi? Lo chiedo perchè balza agli occhi una sequenza che certamente non produce risultati corretti.

Supponiamo di avere la seguente lista di premi (indico solo il numero di richieste);

1 2 3 4 5 5

Denoto a [=, >, <] b le operazioni a.getRichieste() [=, >, <] b.getRichieste(). Intendo per a = numero a.getRichieste() = quel numero.

il tuo algoritmo (la successione di operazioni sedicenti atomiche che producono un risultato a partire da un valore) è:

p è il primo premio nella lista (cioè 1)
per ogni premio x nella lista (incluso p)
se x > p aggiungi x ai risultati, p = x

Applichiamo questa prima parte alla lista 1 2 3 4 5. Io direi che capiti questo:

p vale 1,

x vale 1, x > p = falso, continua [risultati = vuoto ]
x vale 2, x > p = vero, aggiungi x, p = x, [risultati = 2]
x vale 3, x > p = vero, aggiungi x, p = x, [risultati = 2, 3]
x vale 4, x > p = vero, aggiungi x, p = x, [risultati = 2, 3, 4]
x vale 5, x > p = vero, aggiungi x, p = x, [risultati = 2, 3, 5]
x vale 5, x > p = false, continua [risultati = 2, 3, 5]

La seconda parte dice:

per ogni premio x nella lista
se x = p allora aggiungi x a lista

Dall'applicazione della prima parte risulta p = 5

l'iterazione fa questo:

x vale 1, x = p falso, continua
x vale 2, x = p falso, continua
x vale 3, x = p falso, continua
x vale 4, x = p falso, continua
x vale 5, x = p vero, aggiungi x, [risultati = 2, 3, 5, 5]
x vale 5, x = p vero, aggiungi x, [risultati = 2, 3, 5, 5, 5]

Questo risultato è corretto?

[banryu79]

Originariamente inviato da giogts

ti assicuro che funziona, il primo ciclo prende correttamente il premio che ha il maggior valore di richieste, il problema credo che sia come dice banryu79, non dovrei includere p nel secondo ciclo di confronto, ma come faccio ad escluderlo?

No lascia, ha ragione PGI, il tuo metodo non è corretto perchè per particolari sequenze di input sembra fare il suo dovere, mentre per altre no.

Invece prova a prendere spunto dal suo primo post: il processo mentale che ti ha descritto è un buon esempio del modo di procedere quando ci si trova difronte la neccessità di scrivere un piccolo algoritmo; ti ha illustrato passo-passo i singoli step di costruzione teorica dell'algoritmo per risolvere uno specifico problema e ti ha scritto pure il pseudocodice.

Solo alla fine, quando si ha una ragionevole certezza della correttezza logica del proprio algoritmo, si procede con l'implementazione del codice.

Io ti consiglio di rileggerti con calma il suo post, armarti di carta e penna, pensare al tuo problema: cosa ricevi in ingresso, cosa devi produrre in uscita e quindi scrivere in pseudo codice tutti i singoli passaggi logici che compongono la tua soluzione.