La forma más eficiente de ver si un ArrayList contiene un objeto en Java

Question

Tengo una ArrayList de objetos en Java. Los objetos tienen cuatro campos, dos de los cuales utilizaría para considerar el objeto igual a otro. Estoy buscando la manera más eficiente, dados esos dos campos, para ver si la matriz contiene ese objeto.

La llave es que estas clases se generan en base a objetos XSD, por lo que no puedo modificar las clases para sobrescribir el .equals.

¿Hay alguna forma mejor que sólo un bucle a través y comparar manualmente los dos campos para cada objeto y luego romper cuando se encuentran? Eso parece tan sucio, buscando una mejor manera.

Editar: ArrayList proviene de una respuesta SOAP que no se encuentra dentro de los objetos.

Answer 1

Depende de qué tan eficiente necesite que sean las cosas. Simplemente iterar sobre la lista buscando el elemento que satisfaga una determinada condición es O (n), pero también lo es ArrayList. Contiene si puede implementar el método Equals. Si no está haciendo esto en bucles o bucles internos, este enfoque probablemente esté bien.

Si realmente necesita velocidades muy eficientes de consulta a toda costa, que tendrá que hacer dos cosas:

1. evitar el hecho de que se genera la clase : Escribir una clase de adaptador que puede envolver la clase generada y que implementa equals() basado en en esos dos campos (suponiendo que son públicos). No olvide incluir también implementar hashCode() (*)
2. Envuelva cada objeto con ese adaptador y póngalo en un HashSet. HashSet.contains() tiene un tiempo de acceso constante, es decir, O (1) en lugar de O (n).

Por supuesto, la construcción de este HashSet todavía tiene un costo de O (n). Solo ganará algo si el costo de crear el HashSet es insignificante en comparación con el costo total de todos los controles() que debe realizar. Intentar construir una lista sin duplicados es un caso así.

---

* ( ) La implementación de hashCode() es el mejor hecho por XOR'ing (^ operador) los hashcodes de los mismos campos que está utilizando para la ejecución iguales (pero multiply by 31 para reducir la posibilidad de que el rendimiento XOR 0)

Answer 2

Si la lista es sorted, se puede utilizar un binary search. Si no, entonces no hay mejor manera.

Si estás haciendo esto mucho, es casi seguro que valdría la pena su tiempo para ordenar la lista por primera vez. Como no puede modificar las clases, deberá usar un Comparator para realizar la clasificación y la búsqueda.

Answer 3

Incluso si el método igual fuera comparando esos dos campos, entonces, lógicamente, sería exactamente el mismo código que el hacerlo manualmente. OK, podría ser "desordenado", pero sigue siendo la respuesta correcta

Answer 4

Dadas sus limitaciones, está atascado con la búsqueda de fuerza bruta (o creando un índice si la búsqueda se repetirá). ¿Puede elaborar alguno sobre cómo se genera el ArrayList? Quizás haya algún margen de maniobra allí.

Si todo lo que está buscando es el código más bonito, considerar el uso de las clases de Apache Commons Collections, en particular, CollectionUtils.find(), para el azúcar sintáctica ya hecha:

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

La construcción de un HashMap de estos objetos en base a la el valor del campo como clave podría valer la pena desde la perspectiva del rendimiento, por ejemplo Mapas poblar una vez y encontrar objetos muy eficiente

Answer 6

Si es necesario buscar muchas veces en la misma lista, puede pagar para construir un índice.

Iterar una vez a través, y construir un HashMap con los iguales valoran que busca como la clave y el nodo apropiado como el valor. Si necesita todos en lugar de cualquiera de un valor igual dado, deje que el mapa tenga un tipo de valor de lista y cree toda la lista en la iteración inicial.

Tenga en cuenta que se debe medir antes de hacer esto como la sobrecarga de la construcción del índice que puede restar simplemente recorrer hasta que se encuentre el nodo espera.

Answer 7

Puede utilizar un Comparador con los métodos incorporados de Java para la clasificación y la búsqueda binaria. Suponga que tiene una clase como esta, donde a y b son los campos que desea utilizar para la clasificación:

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

definiría su Comparador:

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

A continuación, ordenar la lista:

Collections.sort(list, comparator); 

Y, por último hacer la búsqueda binaria:

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

Answer 8

Hay tres opciones básicas:

1) Si el rendimiento de recuperación es primordial y es práctico hacerlo, utilice una forma de tabla hash construida una vez (y modificada como/si la Lista cambia).

2) Si la lista está ordenada convenientemente o es práctico ordenarla y la recuperación O (log n) es suficiente, ordenar y buscar.

3) Si la recuperación O (n) es lo suficientemente rápida o si no es práctico manipular/mantener la estructura de datos o una alternativa, itere sobre la Lista.

Antes de escribir un código más complejo que una simple iteración sobre la Lista, vale la pena pensar en algunas preguntas.

• ¿Por qué es necesario algo diferente? (Tiempo) rendimiento? ¿Elegancia? Mantenibilidad? ¿Reutilizar? Todos estos son motivos correctos, separados o juntos, pero influyen en la solución.

• ¿Cuánto control tiene sobre la estructura de datos en cuestión?¿Puedes influenciar cómo está construido? ¿Administrado más tarde?

• ¿Cuál es el ciclo de vida de la estructura de datos (y los objetos subyacentes)? ¿Se construye todo de una vez y nunca cambia, o es altamente dinámico? ¿Puede su código monitorear (o incluso alterar) su ciclo de vida?

• ¿Existen otras limitaciones importantes, como la huella de memoria? ¿Importa la información sobre duplicados? Etc.

Answer 9

¿Hay alguna forma mejor que sólo un bucle a través y comparar manualmente los dos campos para cada objeto y luego romper cuando se encuentran? Eso parece tan sucio, buscando una mejor manera.

Si su preocupación es la mantenibilidad que podría hacer lo Fabian Steeg sugieren (que es lo que haría) aunque probablemente no es el "más eficiente" (porque hay que ordenar la matriz primero y luego realizar el binario búsqueda) pero ciertamente la opción más limpia y mejor.

Si realmente le preocupa la eficiencia, puede crear una implementación de Lista personalizada que use el campo de su objeto como el hash y use un HashMap como almacenamiento. Pero probablemente esto sería demasiado.

Luego debe cambiar el lugar donde completa los datos de ArrayList a YourCustomList.

igual:

List list = new ArrayList(); 

fillFromSoap(list); 

Para:

List list = new MyCustomSpecialList(); 

fillFromSoap(list); 

La implementación sería algo como lo siguiente:

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

}

Más o menos como un HashSet, la problema aquí está el HashSet confía en la buena implementación del método hashCode, que probablemente no tenga. En su lugar, utiliza como hash "ese campo que conoce", que es el que hace que un objeto sea igual al otro.

Por supuesto, la aplicación de una lista de la cantidad de cero más complicado que mi fragmento anterior, por eso digo que el Fabian Steeg sugerencia sería mejor y más fácil de implementar (aunque algo como esto sería más eficiente)

Díganos lo que hiciste al final

Answer 10

Diría que la solución más simple sería envolver el objeto y delegar la llamada contiene a una colección de la clase envuelta. Esto es similar al comparador pero no lo obliga a ordenar la colección resultante, simplemente puede usar 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

Tal vez una lista no es lo que necesita.

Tal vez un TreeSet sería un mejor contenedor. Obtiene la inserción y recuperación de O (log N) y la iteración ordenada (pero no permite duplicados).

LinkedHashMap podría ser incluso mejor para su caso de uso, échele un vistazo.

Answer 12

Si usted es un usuario de mi ForEach DSL, se puede hacer con una consulta 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();