Il modo più efficiente per vedere se un ArrayList contiene un oggetto in Java

Question

Ho un ArrayList di oggetti in Java.Gli oggetti hanno quattro campi, due dei quali utilizzerei per considerare l'oggetto uguale ad un altro.Sto cercando il modo più efficiente, dati questi due campi, per vedere se l'array contiene quell'oggetto.

La chiave è che queste classi sono generate in base a oggetti XSD, quindi non posso modificare le classi stesse per sovrascrivere il file .equals.

Esiste un modo migliore del semplice scorrere e confrontare manualmente i due campi per ciascun oggetto e quindi interromperli quando vengono trovati?Sembra così complicato, cercare un modo migliore.

Modificare: l'ArrayList proviene da una risposta SOAP non suddivisa in oggetti.

Answer 1

Dipende da come efficiente è necessario che le cose siano. È sufficiente iterare sulla lista alla ricerca per l'elemento che soddisfa una certa condizione è O (n), ma lo è anche ArrayList.Contains se è possibile implementare il metodo Equals. Se non stai facendo questo in loop o cicli interni di questo approccio è probabilmente più che bene.

Se si ha realmente bisogno di molto efficienti velocità di look-up a tutti i costi, è necessario fare due cose:

1. aggirare il fatto che la classe viene generato: Scrivere una classe adattatore che può avvolgere la classe generata e che attuare equals () in base su questi due campi (ammesso che sono pubblici). Non dimenticare di anche implementare hashCode () (*)
2. Avvolgere ogni oggetto con tale scheda e metterlo in un HashSet. HashSet.contains ( ) ha costante tempo di accesso, cioè O (1) invece di O (n).

Naturalmente, la costruzione di questo HashSet ha ancora un O (n) Costo. Si sta solo andando a guadagnare nulla se il costo di costruzione della HashSet è trascurabile rispetto al costo totale di tutte le contiene () controlla che dovete fare. Cercando di costruire una lista senza duplicati è un caso del genere.

---

* () Implementazione hashCode () è meglio farlo da XOR'ing (^ operatore) i codici hash degli stessi campi che si sta utilizzando per l'attuazione equals (ma moltiplicare per 31 per ridurre la possibilità di cedere XOR 0)

Answer 2

È possibile utilizzare un comparatore con metodi built-in di Java per l'ordinamento e ricerca binaria. Supponiamo di avere una classe come questa, dove a e b sono i campi che si desidera utilizzare per l'ordinamento:

class Thing { String a, b, c, d; }

Si potrebbe definire il comparatore:

Comparator<Thing> comparator = new Comparator<Thing>() {
  public int compare(Thing o1, Thing o2) {
    if (o1.a.equals(o2.a)) {
      return o1.b.compareTo(o2.b);
    }
    return o1.a.compareTo(o2.a);
  }
};

Poi ordinare l'elenco:

Collections.sort(list, comparator);

E finalmente fare la ricerca binaria:

int i = Collections.binarySearch(list, thingToFind, comparator);

Answer 3

Dato vostri vincoli, sei bloccato con la forza bruta di ricerca (o la creazione di un indice, se la ricerca sarà ripetuta). Si può elaborare qualsiasi su come viene generato il ArrayList -. Forse c'è qualche scappatoia c'è

Se tutto quello che stai cercando è il codice più bella, è consigliabile utilizzare le classi Apache Commons Collections, in particolare CollectionUtils.find () , pronto fatto sintattica zuccheri:

ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...

Object found = CollectionUtils.find(haystack, new Predicate() {
   public boolean evaluate(Object input) {
      return needleField1.equals(input.field1) && 
             needleField2.equals(input.field2);
   }
});

Answer 4

Se la lista è ordinati , è possibile utilizzare un ricerca binaria . Se no, allora non c'è modo migliore.

Se stai facendo questo un sacco, sarebbe quasi certamente vale la pena di ordinare l'elenco per la prima volta. Poiché non è possibile modificare le classi, si dovrà utilizzare un Comparator di fare la cernita e la ricerca.

Answer 5

Anche se il metodo uguale erano confrontando questi due campi, quindi logicamente, sarebbe proprio lo stesso codice che lo fai manualmente.OK, potrebbe essere "disordinato", ma è comunque la risposta corretta

Answer 6

Se sei un utente del mio PerOgni DSL , può essere fatto con una query Detect.

Foo foo = ...
Detect<Foo> query = Detect.from(list);
for (Detect<Foo> each: query) 
    each.yield = each.element.a == foo.a && each.element.b == foo.b;
return query.result();

Answer 7

  

C'è un modo migliore di solo scorrendo e confrontando manualmente i due campi per ogni oggetto e poi rompere quando si trova? Che sembra proprio così disordinato, alla ricerca di un modo migliore.

Se la vostra preoccupazione è la manutenibilità si potrebbe fare quello che Fabian Steeg suggeriscono (che è quello che vorrei fare) anche se probabilmente non è il 'più efficace' (perché si deve ordinare l'array e poi eseguire la ricerca binaria ), ma certamente il più pulito e migliore opzione.

Se sei veramente interessati con efficienza, è possibile creare una lista implementazione personalizzata che utilizza il campo nel vostro oggetto come l'hash e usare un HashMap come deposito. Ma probabilmente questo sarebbe troppo.

Poi si deve cambiare il luogo in cui si compila i dati da ArrayList per YourCustomList.

Come:

 List list = new ArrayList();

 fillFromSoap( list );

A:

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

L'implementazione sarebbe qualcosa di simile al seguente:

class MyCustomSpecialList extends AbstractList  { 
    private Map<Integer, YourObject> internalMap;

    public boolean add( YourObject o ) { 
         internalMap.put( o.getThatFieldYouKnow(), o );
    }

    public boolean contains( YourObject o ) { 
        return internalMap.containsKey( o.getThatFieldYouKnow() );
    }

}

Più o meno come un HashSet, il problema qui è l'HashSet si basa sulla buona implementazione del metodo hashCode, che probabilmente non è necessario. Invece si utilizza come l'hash "quel campo si sa" che è quello che rende un oggetto è uguale all'altro.

Naturalmente l'attuazione di un elenco dal lotto zero 'più difficile del mio frammento di sopra, è per questo che dico che il Fabian Steeg suggerimento sarebbe migliore e più facile da implementare (anche se qualcosa di simile sarebbe più efficiente)

Raccontaci cosa hai fatto alla fine.

Answer 8

Forse un elenco non è quello che ti serve.

TreeSet sarebbe un contenitore migliore. È possibile ottenere O (log N) l'inserimento e il recupero, e ha ordinato l'iterazione (ma non permetterà i duplicati).

LinkedHashMap potrebbe essere ancora meglio per il vostro caso d'uso, controllare che troppo.

Answer 9

Costruire un HashMap di tali oggetti in base al valore del campo come chiave potrebbe essere utile dal punto di vista delle prestazioni, ad esempio compilare mappe una volta e trovare gli oggetti in modo molto efficiente

Answer 10

Se avete bisogno di cercare molte volte nella stessa lista, si può pagare per costruire un indice.

Scorrere una volta attraverso, e costruire un HashMap con l'uguale valore che si sta cercando, come la chiave e il nodo appropriato come valore. Se avete bisogno di tutti, invece di chiunque di un dato uguale valore, quindi lasciare che la mappa ha un tipo di valore di lista e costruire l'intera lista nell'iterazione iniziale.

Si prega di notare che si dovrebbe misurare prima di fare questo, come il sovraccarico di costruzione dell'indice può oscurare solo attraversamento fino a trovare il nodo previsto.

Answer 11

Ci sono tre opzioni di base:

1) Se le prestazioni di recupero è di primaria importanza ed è pratico di farlo, utilizzare una forma di tabella hash costruita una volta (e modificata come / se l'elenco viene modificato).

2) se la lista è convenientemente ordinato o è pratico di risolvere e O (log n) il recupero è sufficiente, ordinamento e ricerca.

3) Se O (n) il recupero è abbastanza veloce, o se non è pratico di manipolare / mantenere la struttura di dati o un supplente, iterare sopra la lista.

Prima di scrivere codice più complesso di una semplice iterazione su List, vale la pena di pensare attraverso alcune domande.

• Perché è necessario qualcosa di diverso? (Time) le prestazioni? Eleganza? Manutenibilità? Riutilizzo? Tutti questi sono motivi va bene, a parte o insieme, ma influenzano la soluzione.

• Quanto controllo si hanno a disposizione la struttura dei dati in questione? Si può influenzare come è fatto? Gestito tardi?

• Qual è il ciclo di vita della struttura dei dati (e oggetti sottostanti)? E 'costruito tutto in una volta e mai cambiato, o altamente dinamico? Può il monitor di codice (o anche modificare) il suo ciclo di vita?

• Ci sono altri vincoli importanti, come occupazione di memoria? Ha informazioni su duplicati importa? Ecc.

Answer 12

Direi che la soluzione più semplice sarebbe quella di avvolgere l'oggetto e delegare la contiene chiamata a una collezione di classe avvolto. Questo è simile al confronto, ma non ti costringe a ordinare l'insieme risultante, si può semplicemente utilizzare ArrayList.contains ().

public class Widget {
        private String name;
        private String desc;

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getDesc() {
            return desc;
        }

        public void setDesc(String desc) {
            this.desc = desc;
        }
    }



    public abstract class EqualsHashcodeEnforcer<T> {

        protected T wrapped;

        public T getWrappedObject() {
            return wrapped;
        }

        @Override
        public boolean equals(Object obj) {
            return equalsDelegate(obj);
        }

        @Override
        public int hashCode() {
            return hashCodeDelegate();
        }

        protected abstract boolean equalsDelegate(Object obj);

        protected abstract int hashCodeDelegate();
    }


    public class WrappedWidget extends EqualsHashcodeEnforcer<Widget> {

        @Override
        protected boolean equalsDelegate(Object obj) {
            if (obj == null) {
                return false;
            }
            if (obj == getWrappedObject()) {
                return true;
            }
            if (obj.getClass() != getWrappedObject().getClass()) {
                return false;
            }
            Widget rhs = (Widget) obj;

            return new EqualsBuilder().append(getWrappedObject().getName(),
                    rhs.getName()).append(getWrappedObject().getDesc(),
                    rhs.getDesc()).isEquals();
        }

        @Override
        protected int hashCodeDelegate() {

            return new HashCodeBuilder(121, 991).append(
                    getWrappedObject().getName()).append(
                    getWrappedObject().getDesc()).toHashCode();
        }

    }