Il modo migliore per scoprire se una raccolta contiene o meno un elemento con una specifica qualità desiderata

Naviga le tue risposte
5

Sembra essere una cosa molto comune dover dire se qualche elenco o insieme contiene almeno un oggetto che corrisponde a una determinata condizione, eppure la mia ricerca e lettura precedente non ha mai trovato una buona pratica soddisfacente o un modello di progettazione di cui parlare. Nelle situazioni che sto pensando, il solo uso di "contiene" non è sufficiente, poiché il test che vogliamo eseguire non è strettamente basato sul metodo di uguaglianza della classe in questione.

Alcune cose che ho visto: 

// for-each with break
private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    boolean foundIt = false;
    for (Foo item: candidates) {
        if (<< item passes some test >>) {
            fountIt = true;
            break;
        }
    }
    return foundIt;
}   

// while-do with index counter
private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    boolean foundIt = false;
    int index = 0;
    while(!fountIt && index < candidates.size() - 1) {
        Foo item = candidates.get(index++);
        if (<< item passes some test >>) {
            fountIt = true;
        }
    }
    return foundIt;
}

Entrambi fanno il lavoro e si fermano non appena viene trovato un successo, forse risparmiando un po 'di tempo se siamo fortunati abbastanza per avere l'oggetto desiderato all'inizio della lista. Tuttavia, entrambi richiedono il loop dell'intero elenco per ottenere un risultato falso

Un'altra tecnica che ho visto in alcune circostanze è che allo stesso tempo viene generata la% originale% co_de (cioè recuperata dal database) per generare simultaneamente un List<Foo> . In questa tecnica, Map<FooKey, Foo> è una classe aggiuntiva (spesso interna) tenendo solo quegli attributi di un FooKey che formano la "qualità desiderata" e sovrascrive i metodi di uguaglianza e codice hash basati su quello. Quando hai bisogno di determinare se esiste un Foo desiderato, fai un'istanza di Foo esattamente con quella desiderata, quindi chiama new FooKey() sulla mappa. Extra sforzo in attacco, ma veloce e facile nel momento in cui ne hai bisogno.

Non riesco a metterlo un dito sopra. Ogni idea funziona, ma ognuna sembra un po 'hacky e inefficiente.

    
posta cobaltduck 23.05.2014 - 20:59
fonte

3 risposte

5

Algorithmically, la versione for-each e while-with-indexing implementa ricerca lineare . Questo va bene per le piccole collezioni o quando fai solo un controllo di tanto in tanto, ma se è un componente importante del tuo programma, ti consigliamo una struttura di mappatura dedicata che acceleri queste query facendo qualcosa di fondamentalmente diverso dalla ricerca lineare. Gli esempi includono gli alberi di ricerca binaria (dove è necessario definire un ordinamento coerente) e le tabelle hash (in cui è necessario definire una funzione hash coerente). Per la maggior parte dei predicati questo è banale, per altri sarebbe un codice in più (che definisce FooKey ), e per altri ancora è difficile o completamente poco pratico. Questa è una chiamata di giudizio in base ai criteri con cui si cerca.

Quando hai deciso di effettuare una ricerca lineare, ci sono diverse opzioni per implementarlo (ammesso che non ci sia già una buona implementazione - se è così, preferiscilo!). La variante for-each è abbastanza generale e IMHO elegante: funziona con qualsiasi iterable, non deve nemmeno essere supportata da una collezione concreta (cfr. Stream in Java 8). Il ciclo while con l'indicizzazione, d'altra parte, è molto limitato: è offensivamente lento per i contenitori che non possono fare accesso casuale (ad esempio liste collegate), e non funziona affatto per cose che non possono essere indicizzate. Vorrei mai raccomandare questo. Probabilmente esistono altre varianti, ma sono ancora più specializzate. Se implementi la ricerca lineare, implementala per i file iterabili.

Un altro problema è come fornisci il predicato. Tu potresti scrivere essenzialmente lo stesso ciclo ancora e ancora con solo la condizione diversa. Ma questo è soggetto a errori, prolisso e inefficiente. Ci dovrebbe essere solo una copia di questo ciclo, con la condizione passata come parametro. Se la tua lingua (versione) può farlo, usa una funzione / lambda di prima classe. Altrimenti, potresti emularlo con un'interfaccia e classi anonime. Dopo averlo fatto, Map s perde parte del suo fascino: non è più un ciclo lungo contro map.get(whatIWant) , è list.find(whatIWant) . Ovviamente hanno ancora un vantaggio in termini di prestazioni per le raccolte di grandi dimensioni.

Nota a margine: i loop possono essere leggermente più semplici, ad esempio scriverei il ciclo for-each come: 

private boolean doFoosHaveGoodQuality(List<Foo> candidates) {
    for (Foo item: candidates) {
        if (<< item passes some test >>) {
            return true;
        }
    }
    return false;
}
    
risposta data 23.05.2014 - 21:15
fonte
5

Entrambi i tuoi suggerimenti sono inutilmente prolissi e il tipo di input è troppo specifico. Prima di Java 8 scriverei: 

private boolean doFoosHaveGoodQuality(Iterable<Foo> candidates) {
    for (Foo item: candidates) {
        if (<< item passes some test >>) return true;
    }
    return false;
}

Con Java 8 questi loop noiosi non sono necessari: 

private boolean doFoosHaveGoodQuality(Collection<Foo> foos) {
    return foos.stream().anyMatch(foo -> ... some test ... );
}
    
risposta data 23.05.2014 - 22:37
fonte
3

Quando il tuo problema non ha una buona soluzione, risolvi un problema diverso.

Invece di scorrere la raccolta, avvolgere quella raccolta in un'altra classe che tiene traccia delle informazioni che desideri ogni volta che gli elementi vengono aggiunti o rimossi. Non commettere l'errore di presumere che le interfacce di raccolta fornite da Java soddisfino tutte le esigenze che incontrerai.

Per il caso base, la tua nuova classe avrà due oggetti: l'Elenco originale e un nuovo campo Set per la proprietà che ti interessa. Questo, naturalmente, presuppone che tu stia solo interrogando un piccolo numero di proprietà.

Ciò significa che è necessario mai consentire le operazioni di modifica sui contenitori interni. Esistono alcune funzioni di utilità in java.util.Collections per restituire una vista non modificabile di varie raccolte, per facilitare il porting dei chiamanti, ma se si effettua la muting ad es. attraverso un Iterator è una funzionalità utilizzata da alcuni dei tuoi chiamanti, dovrai implementarla.

    
risposta data 24.05.2014 - 00:41
fonte

Leggi altre domande sui tag

Esistono algoritmi per dividere o combinare le parole nella loro forma più comune? Qual è la differenza tra _Procedural Generation_ e _Random Generation_?