metodos - imprimir arraylist java

La manera 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 inglesa es que estas clases se generan en base a objetos XSD, por lo que no puedo modificar las clases para sobrescribir los .equals .

¿Hay alguna otra manera mejor que simplemente recorrer y comparar manualmente los dos campos para cada objeto y luego romperlos cuando los encuentre? Eso parece tan sucio, buscando una mejor manera.

Editar: ArrayList proviene de una respuesta SOAP que no está clasificada en objetos.

Answer 1

¿Hay alguna otra manera mejor que simplemente recorrer y comparar manualmente los dos campos para cada objeto y luego romperlos cuando los encuentre? Eso parece tan sucio, buscando una mejor manera.

Si tu preocupación es la mantenibilidad, podrías hacer lo que Fabian Steeg sugiera (eso es lo que yo haría) aunque probablemente no sea "lo más eficiente" (porque primero tienes que ordenar la matriz y luego realizar la búsqueda binaria) pero sin duda la más limpia y mejor opción.

Si realmente le preocupa la eficiencia, puede crear una implementación de Lista personalizada que use el campo de su objeto como 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.

Me gusta:

 List list = new ArrayList();

 fillFromSoap( list );

A:

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

}

Como en HashSet, el problema aquí es que HashSet depende de 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 implementación de una lista desde cero es más complicada que mi fragmento anterior, por eso digo que la sugerencia de Fabian Steeg sería mejor y más fácil de implementar (aunque algo como esto sería más eficiente)

Cuéntanos lo que hiciste al final.

Answer 2

Construir un HashMap de estos objetos en función del valor del campo como clave podría valer la pena desde la perspectiva del rendimiento, por ejemplo, llenar una vez Mapas y encontrar objetos de manera muy eficiente.

Answer 3

Dadas tus limitaciones, estás atrapado en la búsqueda de fuerza bruta (o creando un índice si la búsqueda se repite). ¿Puede elaborar alguno sobre cómo se genera ArrayList ? Tal vez haya algún margen de maniobra allí.

Si todo lo que está buscando es un código más bonito, considere usar las clases de Colecciones de Apache Commons, en particular CollectionUtils.find() , para el azúcar sintáctico listo para usar:

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

Depende de qué tan eficiente necesita 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 de búsqueda muy eficientes a toda costa, tendrá que hacer dos cosas:

1. Evite el hecho de que se genere la clase: escriba una clase de adaptador que pueda envolver la clase generada y que implemente equals() función de esos dos campos (suponiendo que sean públicos). No olvides implementar también hashCode() (*)
2. Envuelva cada objeto con ese adaptador y colóquelo en un HashSet. HashSet.contains() tiene un tiempo de acceso constante, es decir, O (1) en lugar de O (n).

Por supuesto, construir 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 () se realiza mejor mediante XOR''ing (^ operator) los hashCodes de los mismos campos que se utilizan para la implementación igual (pero multiplicar por 31 para reducir la posibilidad de que XOR ceda 0)

Answer 5

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 alterada 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, ordene y busque.

3) Si la recuperación de 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é se necesita algo diferente? (Tiempo) rendimiento? ¿Elegancia? Mantenibilidad? ¿Reutilizar? Todos estos son motivos correctos, separados o juntos, pero influyen en la solución.

• ¿Cuánto control tienes 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 6

Incluso si el método equals estuviera 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 7

Puede usar un Comparador con los métodos integrados de Java para ordenar y buscar binarios. Supongamos que tiene una clase como esta, donde a y b son los campos que desea usar para clasificar:

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

Definirías tu 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);
  }
};

Luego ordena tu lista:

Collections.sort(list, comparator);

Y finalmente haz la búsqueda binaria:

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

Answer 8

Si la lista está sorted , puede usar una búsqueda binaria . Si no, entonces no hay mejor manera.

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

Answer 9

Si necesita buscar muchas veces en la misma lista, puede valer la pena construir un índice.

Iterate una vez, y construye un HashMap con el valor igual que estás buscando 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 debe medir antes de hacer esto ya que la sobrecarga de la construcción del índice puede eclipsar simplemente el desplazamiento hasta que se encuentre el nodo esperado.

Answer 10

Si usted es usuario de mi DSL de ForEach , puede hacerlo con una consulta de 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 11

Tal vez una lista no es lo que necesitas.

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 aún mejor para su caso de uso, échele un vistazo.

Answer 12

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

    }