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

StackOverflow https://stackoverflow.com/questions/558978

Pregunta

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

El problema es que estas clases se generan en función de objetos XSD, por lo que no puedo modificar las clases mismas para sobrescribir el .equals.

¿Hay alguna manera mejor que simplemente recorrer y comparar manualmente los dos campos para cada objeto y luego dividirlos cuando los encuentre?Parece tan complicado buscar una manera mejor.

Editar: ArrayList proviene de una respuesta SOAP que se descompone en objetos.

¿Fue útil?

Solución

Depende de qué tan eficiente que necesita ser las cosas. Simplemente iterar sobre la lista buscando el elemento que satisface una determinada condición es O (n), pero también lo es ArrayList.Contains si se puede poner en práctica el método Equals. Si usted no está haciendo esto en bucles o lazos internos de este enfoque es probablemente muy bien.

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

  1. Trabajo en torno al hecho de que la clase se genera: Escribir una clase adaptador cuales puede envolver la clase generada y que ponen en práctica iguales basada () en esos dos campos (suponiendo que son públicos). No se olvide también aplicar hashCode () (*)
  2. envolver cada objeto con ese adaptador y ponerlo en un HashSet. HashSet.contains ( ) tiene constantes tiempo de acceso, es decir, O (1) en lugar de O (n).

Por supuesto, la construcción de este HashSet todavía tiene un O (n) de coste. Sólo se le va a ganar nada si el costo de la construcción de la HashSet es insignificante en comparación con el costo total de todos los cheques contains () que tiene que hacer. Tratando de construir una lista sin duplicados es un caso así.

* () de aplicación hashCode () se hace mejor XOR'ing (^ operador) los hashcodes de los mismos campos que está utilizando para la ejecución iguales (pero multiplicar por 31 para reducir la posibilidad de que el rendimiento XOR 0)

Otros consejos

Se puede usar un comparador con 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 clasificar: 

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

Se podría definir 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);

Teniendo en cuenta sus limitaciones, le pegan con fuerza bruta de búsqueda (o la creación de un índice si la búsqueda se repite). ¿Nos puedes contar alguna sobre cómo se genera la ArrayList -. Tal vez hay un margen de maniobra existe

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

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

Si la lista es ordenados, se puede utilizar un búsqueda binaria . Si no, entonces no hay mejor manera.

Si usted está haciendo esto mucho, es casi seguro que valdría la pena su tiempo para ordenar la lista por primera vez. Puesto que no puede modificar las clases, que tendría que utilizar un Comparator para realizar la ordenación y búsqueda.

Incluso si el método es igual eran Al comparar esos dos campos, entonces, lógicamente, sería el mismo código que si lo hiciera manualmente.Vale, puede que sea "confuso", pero sigue siendo la respuesta correcta.

Si usted es un usuario de mi ParaCada 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();
  

¿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 sólo parece tan desordenado, en busca de una mejor manera.

Si su preocupación es la mantenibilidad que podría hacer lo que 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 la búsqueda binaria ) pero sin duda el más limpio y mejor opción.

Si usted está realmente preocupado con la eficiencia, se puede crear una aplicación de lista personalizada que utiliza el campo en su objeto como el hash y el uso de un HashMap como almacenamiento. Pero probablemente esto sería demasiado.

A continuación, usted tiene que cambiar el lugar donde surte los datos de ArrayList a YourCustomList.

Al igual que: 

 List list = new ArrayList();

 fillFromSoap( list );

Para: 

 List list = new MyCustomSpecialList();

 fillFromSoap( list );

La aplicación sería algo así 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, el problema aquí es la HashSet depende de la buena aplicación del método hashCode, que probablemente usted no tiene. En su lugar se utiliza como el hash "ese campo sabe" que es el que hace que un objeto es igual a la otra.

Por supuesto, la aplicación de una lista de la cantidad de cero más complicado que mi fragmento anterior, por eso digo que la 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 hizo al final.

Tal vez una lista no es lo que necesita.

Tal vez un TreeSet sería un recipiente mejor. Se obtiene O (log N) de inserción y recuperación, y ordenó iteración (pero no permitirá duplicados).

LinkedHashMap puede haber incluso mejor para su caso de uso, comprobar que fuera también.

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

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 todo en lugar de cualquiera de un determinado valor es igual, entonces que el mapa tiene un tipo de valor de la lista y construir 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.

Hay tres opciones básicas:

1) Si el rendimiento de recuperación es de suma importancia y es práctico hacerlo, utilice una forma de tabla hash una vez incorporado (y alterado como / si la lista de cambios).

2) Si la lista está convenientemente ordenadas o no es práctico para solucionar el problema y O (log n) de recuperación es suficiente, ordenar y búsqueda.

3) Si O (n) de recuperación es lo suficientemente rápido o si no es práctico para manipular / mantener la estructura de datos o un suplente, iterar sobre la Lista.

Antes de escribir código más complejo que una simple iteración sobre la lista, vale la pena realizar a través de algunas preguntas.

  • ¿Por qué se necesita algo diferente? (Tiempo) el rendimiento? ¿Elegancia? Mantenimiento? ¿Reutilizar? Todas estas son razones okay, separados o juntos, pero que influyen en la solución.

  • ¿Cuánto control que tiene sobre la estructura de datos en cuestión? ¿Puede influir en cómo se construye? Gestionado más adelante?

  • ¿Cuál es el ciclo de vida de la estructura de datos (y los objetos subyacentes)? Es construido de una sola vez y nunca ha cambiado, o altamente dinámico? Puede su monitor de código (o incluso alterar) su ciclo de vida?

  • ¿Hay otras limitaciones importantes, como la huella de la memoria? ¿Es importante la información sobre los duplicados? Etc.

Yo diría que la solución más sencilla sería la de envolver el objeto y delegar la llamada contiene una colección de la clase envueltos. Esto es similar al comparador pero no le obliga a ordenar la colección resultante, puede simplemente 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();
        }

    }
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top