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

Ho una lista di oggetti in Java. Gli oggetti hanno quattro campi, due dei quali utilizzerei per considerare l’object uguale ad un altro. Sto cercando il modo più efficiente, dato quei due campi, per vedere se l’array contiene quell’object.

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

Esiste un modo migliore del semplice ciclo di ricerca e confronto manuale tra i due campi per ciascun object e quindi interruzione al momento del rilevamento? Sembra solo così disordinato, alla ricerca di un modo migliore.

Modifica: ArrayList deriva da una risposta SOAP che non è riservata agli oggetti.

Dipende da quanto hai bisogno che le cose siano efficaci. Semplicemente scorrere l’elenco alla ricerca dell’elemento che soddisfa una determinata condizione è O (n), ma lo è anche ArrayList.Contains se è ansible implementare il metodo Equals. Se non lo fai nei loop o nei loop interni questo approccio probabilmente va bene.

Se hai davvero bisogno di velocità di ricerca molto efficienti a tutti i costi, dovrai fare due cose:

  1. Lavora sul fatto che la class è generata: scrivi una class adattatore che può avvolgere la class generata e quale implementa equals () in base a questi due campi (supponendo che siano pubblici). Non dimenticare di implementare anche hashCode () (*)
  2. Avvolgi ogni object con quell’adattatore e mettilo in un HashSet. HashSet.contains () ha un tempo di accesso costante, cioè O (1) invece di O (n).

Ovviamente, la costruzione di questo HashSet ha ancora un costo O (n). Otterrai solo qualcosa se il costo della creazione di HashSet è trascurabile rispetto al costo totale di tutti i controlli contains () che devi fare. Cercare di build una lista senza duplicati è un caso del genere.


* ( ) L’implementazione di hashCode () viene eseguita al meglio da XOR’ing (operatore ^) i nodes hash degli stessi campi che si stanno utilizzando per l’implementazione di uguali (ma moltiplicare per 31 per ridurre la possibilità che XOR produca 0)

È ansible utilizzare un comparatore con i metodi incorporati di Java per l’ordinamento e la ricerca binaria. Supponiamo di avere una class come questa, dove aeb sono i campi che vuoi usare per l’ordinamento:

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

Definiresti il ​​tuo comparatore:

 Comparator comparator = new Comparator() { 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); } }; 

Quindi ordina la tua lista:

 Collections.sort(list, comparator); 

E infine fai la ricerca binaria:

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

Dati i tuoi vincoli, sei bloccato con la ricerca della forza bruta (o la creazione di un indice se la ricerca verrà ripetuta). Puoi elaborare qualsiasi cosa su come viene generato l’ ArrayList – forse c’è qualche spazio di manovra lì.

Se tutto quello che stai cercando è un codice più carino, considera l’utilizzo delle classi Collections Apache Commons, in particolare CollectionUtils.find () , per lo zucchero sintattico pronto:

 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); } }); 

Se la lista è ordinata , puoi usare una ricerca binaria . Se no, allora non c’è modo migliore.

Se lo fai molto, quasi sicuramente vale la pena di ordinare la lista la prima volta. Poiché non è ansible modificare le classi, è necessario utilizzare un Comparator per eseguire l’ordinamento e la ricerca.

Anche se il metodo equals stesse confrontando questi due campi, quindi logicamente, sarebbe lo stesso codice di come lo si fa manualmente. OK, potrebbe essere “disordinato”, ma è sempre la risposta corretta

Se sei un utente della mia DSL ForEach , può essere fatto con una query Detect .

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

Esiste un modo migliore del semplice ciclo di ricerca e confronto manuale tra i due campi per ciascun object e quindi interruzione al momento del rilevamento? Sembra solo così disordinato, alla ricerca di un modo migliore.

Se la tua preoccupazione è la manutenibilità puoi fare quello che Fabian Steeg suggerisce (è quello che farei io) anche se probabilmente non è il “più efficiente” (perché devi prima ordinare l’array e poi eseguire la ricerca binaria) ma sicuramente il più pulito e migliore opzione.

Se si è veramente interessati all’efficienza, è ansible creare un’implementazione di Elenco personalizzata che utilizza il campo nell’object come hash e utilizza una HashMap come memoria. Ma probabilmente questo sarebbe troppo.

Quindi devi modificare il luogo in cui inserisci i dati da ArrayList a YourCustomList.

Piace:

  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 internalMap; public boolean add( YourObject o ) { internalMap.put( o.getThatFieldYouKnow(), o ); } public boolean contains( YourObject o ) { return internalMap.containsKey( o.getThatFieldYouKnow() ); } 

}

Praticamente come un HashSet, il problema qui è che HashSet si basa sulla buona implementazione del metodo hashCode, che probabilmente non hai. Invece si usa come hash “quel campo che conosci” che è quello che rende un object uguale all’altro.

Naturalmente implementando una lista da zero molto più difficile del mio frammento sopra, ecco perché dico che il suggerimento di Fabian Steeg sarebbe migliore e più facile da implementare (anche se qualcosa del genere sarebbe più efficiente)

Dicci cosa hai fatto alla fine.

Forse una lista non è ciò di cui hai bisogno.

Forse un TreeSet sarebbe un contenitore migliore. Ottiene l’inserimento e il recupero di O (log N) e l’iterazione ordinata (ma non consente duplicati).

LinkedHashMap potrebbe essere ancora migliore per il tuo caso d’uso, controlla anche quello.

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

Se devi cercare più volte nella stessa lista, può pagare per build un indice.

Eseguire una volta l’iterazione e creare una HashMap con il valore equals che si sta cercando come chiave e il nodo appropriato come valore. Se hai bisogno di tutti invece di qualcuno con un determinato valore di uguale, quindi lascia che la mappa abbia un tipo di valore di lista e costruisca l’intera lista nell’iterazione iniziale.

Si noti che è necessario misurare prima di eseguire questa operazione poiché il sovraccarico di creazione dell’indice potrebbe oscurare solo il movimento finché non viene trovato il nodo previsto.

Ci sono tre opzioni di base:

1) Se la prestazione di recupero è fondamentale ed è pratico farlo, usa una forma di tabella hash costruita una sola volta (e modificata come / se la lista cambia).

2) Se l’Elenco è ordinato in modo conveniente o è pratico ordinarlo e O (log n) il recupero è sufficiente, ordina e cerca.

3) Se O (n) il recupero è abbastanza veloce o se non è pratico manipolare / mantenere la struttura dei dati o un sostituto, scorrere sull’elenco.

Prima di scrivere un codice più complesso di una semplice iterazione sull’Elenco, vale la pena di riflettere su alcune domande.

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

  • Quanto controllo hai sulla struttura dati in questione? Puoi influenzare come è costruito? Gestito più tardi?

  • Qual è il ciclo di vita della struttura dei dati (e degli oggetti sottostanti)? È costruito tutto in una volta e non è mai cambiato, o altamente dinamico? Il tuo codice può monitorare (o addirittura alterare) il suo ciclo di vita?

  • Ci sono altri vincoli importanti, come l’impronta della memoria? Le informazioni sui duplicati sono importanti? Eccetera.

Direi che la soluzione più semplice sarebbe quella di avvolgere l’object e debind la chiamata contiene a una raccolta della class spostata. Questo è simile al comparatore, ma non ti obbliga a ordinare la raccolta risultante, puoi semplicemente usare 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 { 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 { @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(); } }