Java: ¿Filtrado Eficiente ArrayList?

Question

Necesito filtrar una ArrayList y eliminar los elementos encontrados. Siendo relativamente nuevo en Java, me pregunto cuál es el método más eficiente para lograrlo (ya que se ejecuta en dispositivos móviles). Actualmente hago esto:

// We display only top-level dealers (parentId=-10) 
ArrayList<DealerProductCount> subDealers = new ArrayList<DealerProductCount>(); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId != -10) subDealers.add(dealer); 
} 
wsResponse.Dealers.removeAll(subDealers); 

¿Se puede hacer sin objetos temporales? ¿Tal vez manipulando directamente (eliminando) los elementos de la lista que se itera?

Answer 1

eliminar de manera eficiente un número de elementos de un ArrayList requiere algo de reflexión. El enfoque ingenuo es algo como esto:

Iterator<DealerProductCount> it = wsResponse.Dealers.iterator(); 
while (it.hasNext()) { 
    if (it.next().ParentId != -10) { 
     it.remove(); 
    } 
} 

El problema es que cada vez que se retire un elemento de copiar (en promedio) la mitad de los elementos restantes. Esto se debe a que eliminar un elemento de un ArrayList implica copiar todos los elementos después de eliminar el elemento una posición a la izquierda.

Su solución original que implica la lista de elementos que se eliminarán esencialmente hace lo mismo. Desafortunadamente, las propiedades de un ArrayList no permiten que removeAll lo haga mejor que el anterior.

Si va a eliminar una serie de elementos, el siguiente es más eficiente:

ArrayList<DealerProductCount> retain = 
     new ArrayList<DealerProductCount>(wsResponse.Dealers.size()); 
for (DealerProductCount dealer : wsResponse.Dealers) { 
    if (dealer.ParentId == -10) { 
     retain.add(dealer); 
    } 
} 
// either assign 'retain' to 'wsResponse.Dealers' or ... 
wsResponse.Dealers.clear(); 
wsResponse.Dealers.addAll(retain); 

estamos copiando (casi) toda la lista dos veces, por lo que este debe alcanzar el equilibrio (en promedio) si se quita tan solo 4 elementos

---

Es interesante observar que los lenguajes de programación funcionales/bibliotecas de soporte típico de un método de filtro, y que puede hacer esta tarea en una sola pasada a través de la lista; es decir, mucho más eficientemente. Creo que podemos esperar mejoras significativas si/cuando Java admite lambdas, y las API de recopilación se mejoran para usarlas.

Answer 2

Si usa un iterador, puede eliminar elementos de forma segura mientras itera.

Answer 3

Una forma sería utilizar el iterador en lugar de la de cada uno:

Iterator<DealerProductCount> iter = wsResponse.Dealers.iterator() 
while(iter.hasNext()) { 
    if (iter.next().ParentId != -10) iter.remove(); 
}