Eliminar objetos de un ArrayList en Java

Question

Necesito eliminar algunos objetos de un ArrayList si cumplen una condición y me pregunto qué camino podría ser más eficiente.

Aquí está la situación: tengo una clase que contiene un ArrayList que contiene algunos otros objetos. Tengo que iterar sobre este ArrayList y eliminar todos los elementos que cumplan una condición determinada. Por lo que yo sé, los que serían mis opciones para eliminar:

1. Crear un nuevo ArrayList y añadir los elementos que no cumplen la condición. Después de la iteración, cambie de la lista de arrays anterior a la nueva sin los elementos.

2. Crea un nuevo ArrayList y agrega los elementos que cumplen la condición. Después de la iteración, use el método removeAll() pasando el ArrayList con los objetos que se eliminarán.

¿Hay una manera más eficiente de eliminar objetos de un ArrayList?

Answer 1

Otra forma: The Iterator tiene un método opcional remove(), implementado para ArrayList. Puedes usarlo mientras iteras.

No sé, sin embargo, qué variante es la más eficiente, debe medirla.

starblue comentó que la complejidad no es buena, y eso es cierto (para removeAll() también), porque ArrayList tiene que copiar todos los elementos, si en el medio se agrega o elimina un elemento. Para esos casos, una LinkedList debería funcionar mejor. Pero, como no todos conocemos los casos de uso reales, lo mejor es medir todas las variantes para elegir la mejor solución.

Answer 2

Tal vez Iterator 's método remove()? Las clases de recopilación predeterminadas de JDK deberían ser todas las iteradoras de creador que admitan este método.

Answer 3

Puedes repetir hacia atrás y eliminar a medida que avanzas en ArrayList. Esto tiene la ventaja de que los elementos posteriores no necesitan desplazarse y es más fácil de programar que avanzar.

Answer 4

En primer lugar, me aseguraría de que esto realmente sea un cuello de botella de rendimiento, de lo contrario iría con la solución más limpia y más expresiva.

Si se trata de un cuello de botella de rendimiento, simplemente pruebe las diferentes estrategias y vea cuál es la más rápida. Mi apuesta es crear una nueva ArrayList y colocar los objetos deseados en esa, descartando la antigua ArrayList.

Answer 5

Obviamente, de los dos métodos que menciona el número 1 es más eficiente, ya que solo necesita pasar por la lista una vez, mientras que con el método número 2 la lista debe atravesarse dos veces (primero para encontrar los elementos para eliminar , y ellos para eliminarlos).

En realidad, eliminar una lista de elementos de otra lista es probablemente un algoritmo que es peor que O (n), por lo que el método 2 es aún peor.

El método iterador:

List data = ...; 

for (Iterator i = data.iterator(); i.hasNext();) { 
    Object element = i.next(); 

    if (!(...)) { 
     i.remove(); 
    } 
} 

Answer 6

mas potente lo haría, supongo, a utilizar el método listIterator y hacer una iteración inversa:

for (ListIterator<E> iter = list.listIterator(list.size()); iter.hasPrevious();){ 
    if (weWantToDelete(iter.previous())) iter.remove(); 
} 

Editar: Mucho más tarde, también se podría desea agregar the Java 8 way of removing elements de una lista (¡o cualquier colección!) utilizando una referencia de lambda o método. Una actualización in situ filter para las colecciones, si se quiere:

list.removeIf(e -> e.isBad() && e.shouldGoAway()); 

Esta es probablemente la mejor manera de limpiar una colección. Como usa iteración interna, la implementación de la colección podría tomar atajos para hacerlo lo más rápido posible (para ArrayList s, podría minimizar la cantidad de copia necesaria).

Answer 7

A menos que estés seguro de que el problema que se plantea es de hecho un cuello de botella, me gustaría ir para la lectura

public ArrayList filterThings() { 

    ArrayList pileOfThings; 
    ArrayList filteredPileOfThings = new ArrayList(); 

    for (Thing thingy : pileOfThings) { 
     if (thingy.property != 1) { 
      filteredPileOfThings.add(thingy); 
     }    
    } 
    return filteredPileOfThings; 
} 

Answer 8

Soy bueno con recommentation de Mnementh.
Sólo una advertencia sin embargo,

ConcurrentModificationException 

mente que no tiene más de una ejecución hilo. Esta excepción podría aparecer si se ejecuta más de un hilo y los hilos no están bien sincronizados.

Answer 9

Hay un costo oculto en la eliminación de elementos de un ArrayList. Cada vez que elimina un elemento, necesita mover los elementos para llenar el "agujero". En promedio, esto tomará N/2 asignaciones para una lista con N elementos.

Eliminando elementos M de un elemento N ArrayList es O(M * N) en promedio. Una solución O (N) implica crear una nueva lista. Por ejemplo.

List data = ...; 
List newData = new ArrayList(data.size()); 

for (Iterator i = data.iterator(); i.hasNext();) { 
    Object element = i.next(); 

    if ((...)) { 
     newData.add(element); 
    } 
} 

Si N es grande, mi conjetura es que este enfoque será más rápido que el enfoque remove para valores de M tan pequeños como 3 o 4.

Pero es importante crear newList suficientemente grande como para mantenga todos los elementos en list para evitar copiar la matriz de respaldo cuando se expande.

Answer 10

He encontrado una solución alternativa más rápida:

int j = 0; 
    for (Iterator i = list.listIterator(); i.hasNext();) { 
    j++; 

    if (campo.getNome().equals(key)) { 
     i.remove(); 
     i = list.listIterator(j); 
    } 
    } 

Answer 11

int sizepuede= listaoptionVO.size(); 
for (int i = 0; i < sizepuede; i++) { 
    if(listaoptionVO.get(i).getDescripcionRuc()==null){ 
     listaoptionVO.remove(listaoptionVO.get(i)); 
     i--; 
     sizepuede--; 
    } 
} 

edición: añadido muesca

Answer 12

Con un iterador que puede manejar siempre el elemento que viene a la orden, no un índice especificado . Entonces, no deberías estar preocupado con el asunto anterior.

Iterator itr = list.iterator(); 
String strElement = ""; 
while(itr.hasNext()){ 

    strElement = (String)itr.next(); 
    if(strElement.equals("2")) 
    { 
    itr.remove(); 
    } 

Answer 13

Aunque esto es contrario a la intuición, esta es la forma en que aceleré esta operación en una gran cantidad.

exactamente lo que estaba haciendo:

ArrayList < HashMap < String , String >> results; // This has been filled with a whole bunch of results 

ArrayList < HashMap < String, String>> descarte = findResultsToDiscard (resultados);

results.removeall (descartar);

Sin embargo, eliminar todo el método tomó más de 6 segundos (NO incluye el método para obtener los resultados de descarte) para eliminar aproximadamente 800 resultados de una matriz de 2000 (ish).

Probé el método de iterador sugerido por Gustafc y otros en esta publicación.

Esto aceleró la operación un poco (hasta aproximadamente 4 segundos), pero esto aún no era lo suficientemente bueno. Así que he intentado algo arriesgado ...

ArrayList < HashMap < String, String>> results; 

    List <Integer> noIndex = getTheDiscardedIndexs(results); 

for (int j = noIndex.size()-1; j >= 0; j--){ 
    results.remove(noIndex.get(j).intValue()); 
} 

mientras que los getTheDiscardedIndexs ahorrar una gran variedad de de índice en lugar de una serie de HashMaps. Esto resulta en acelerar la eliminación de objetos mucho más rápido (alrededor de 0.1 segundo ahora) y será más eficiente en cuanto a la memoria, ya que no necesitamos crear una gran variedad de resultados para eliminar.

Espero que esto ayude a alguien.