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

Question

Ho una lista array 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, dato quei due campi, per vedere se l'array contiene quell'oggetto.

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

Esiste un modo migliore rispetto al semplice ciclo di collegamento e al confronto manuale tra i due campi per ciascun oggetto 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.

Answer 1

Dipende dall'efficienza necessaria per le cose. Semplicemente scorrere l'elenco alla ricerca dell'elemento che soddisfa una determinata condizione è O (n), ma lo è anche ArrayList.Contains se è possibile implementare il metodo Equals. Se non lo fai nei loop o nei loop interni questo approccio probabilmente va bene.

Se davvero 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 è possibile racchiudere la classe generata e che implementa basata su in questi due campi (supponendo che siano pubblici) . Non dimenticare di anche attuare hashCode() (*)
2. Avvolgere ogni oggetto con quella scheda e metterlo in un HashSet. HashSet.contains() ha un tempo di accesso costante , ovvero O (1) anziché 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 costruire una lista senza duplicati è un caso del genere.

---

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

Answer 2

Se l'elenco è sorted, è possibile utilizzare uno binary search. Se no, allora non c'è modo migliore.

Se si sta facendo molto questo, quasi sicuramente vale la pena di ordinare la lista la prima volta. Poiché non è possibile modificare le classi, è necessario utilizzare un Comparator per eseguire l'ordinamento e la ricerca.

Answer 3

Anche se il metodo uguale era confrontando questi due campi, quindi logicamente, sarebbe lo stesso codice di come lo si esegue manualmente. OK, potrebbe essere "disordinato", ma è ancora la risposta corretta

Answer 4

Dato vostri vincoli, sei bloccato con la forza bruta di ricerca (o la creazione di un indice, se la ricerca sarà ripetuta). Puoi elaborare qualsiasi cosa su come viene generato il ArrayList - forse c'è qualche spazio di manovra lì.

Se tutto quello che stai cercando è il codice più bella, è possibile utilizzare le classi Apache Commons Collections, in particolare CollectionUtils.find(), per lo zucchero sintattico ready-made:

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 5

Costruire una HashMap di questi oggetti in base alla valore del campo come chiave potrebbe essere utile dal punto di vista delle prestazioni, ad es compila Maps una sola volta e trova gli oggetti in modo molto efficiente

Answer 6

Se hai bisogno di cercare più volte nella stessa lista, può pagare per costruire un indice.

Iterate una volta attraverso e create una HashMap con il valore uguale che state 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 prega di notare che è necessario misurare prima di fare ciò poiché il sovraccarico di costruzione dell'indice potrebbe oscurare solo attraversando fino a quando il nodo previsto non viene trovato.

Answer 7

È possibile utilizzare un comparatore con i metodi incorporati di Java per l'ordinamento e la 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; } 

definiresti il ​​tuo 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); 
    } 
}; 

quindi ordinare l'elenco:

Collections.sort(list, comparator); 

E finalmente fare la ricerca binaria:

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

Answer 8

Esistono tre opzioni di base:

1) Se la prestazione di recupero è fondamentale ed è pratico farlo, utilizzare una forma di tabella hash creata una sola volta (e modificata come/se l'Elenco cambia).

2) Se l'elenco è ordinato in modo conveniente o è pratico ordinarlo e O (log n) il recupero è sufficiente, ordinare e cercare.

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 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 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 di memoria? Le informazioni sui duplicati sono importanti? Ecc

Answer 9

C'è un modo migliore di solo scorrendo e confrontando manualmente i due campi per ogni oggetto e poi rompere quando si trova? Sembra solo 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 prima e quindi eseguire il file binario ricerca) ma certamente l'opzione più pulita e migliore.

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

Quindi è necessario modificare il luogo in cui si riempiono i dati da ArrayList a 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 ecco 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 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 suggerimento Fabian Steeg sarebbe meglio e più facile da implementare (anche se qualcosa di simile sarebbe più efficiente)

Contattaci cosa hai fatto alla fine

Answer 10

Direi che la soluzione più semplice sarebbe quella di avvolgere l'oggetto e delegare la chiamata contiene a una raccolta della classe 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<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(); 
     } 

    } 

Answer 11

Forse una lista non è quello che ti serve.

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 meglio per il tuo caso d'uso, controlla anche quello.

Answer 12

Se si è un utente del mio ForEach DSL, è possibile farlo 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();