Suppression d'objets d'une liste de tableaux en Java

Question

J'ai besoin de supprimer des objets d'un ArrayList si elles répondent à une condition, et je me demande de quelle manière pourrait être plus efficace.

Voici la situation: j'ai une classe qui contient un ArrayList contenant quelques autres objets. J'ai d'itérer sur cette ArrayList et de supprimer tous les éléments répondant à une certaine condition. Autant que je sache, ce seraient mes options pour la supprimer:

1. Créer un nouveau ArrayList et ajouter les éléments qui ne satisfait pas la condition. Après l'itération, swap de l'ancienne liste de tableaux à l'autre sans les éléments.

2. Créer un nouveau ArrayList et ajouter les éléments qui répondent à la condition. Après l'itération, l'utilisation de l' removeAll() méthode de passage de l' ArrayList avec les objets à supprimer.

Est-il un moyen plus efficace pour supprimer des objets d'un ArrayList?

Answer 1

Vous pouvez effectuer une itération en arrière et le supprimer au fur et à mesure que vous parcourez la liste de tableaux. Cela présente l'avantage que les éléments suivants ne nécessitent pas de décalage et est plus facile à programmer que de progresser.

Answer 2

D'une autre manière: L'Itérateur de l'option remove()-méthode, qui est mis en œuvre pour ArrayList. Vous pouvez l'utiliser pendant l'itération.

Je ne sais pas si, quelle variante est la plus performante, vous devez mesurer.

starblue commenté, que la complexité n'est pas bon, et c'est vrai (pour removeAll() trop), parce que ArrayList a copier tous les éléments, si dans le milieu est un élément ajouté ou supprimé. Pour ce cas, si une LinkedList mieux travailler. Mais, comme nous ne savons pas votre vrai cas d'utilisation le mieux est aussi de mesurer toutes les variantes, pour choisir la meilleure solution.

Answer 3

Je suppose que les plus performants utiliseraient la méthode listIterator et effectueraient une itération inverse:

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

Answer 4

De toute évidence, des deux méthodes que vous mentionnez numéro 1 est plus efficace, car il suffit de parcourir la liste une fois, alors que pour la méthode numéro 2, elle doit être parcourue deux fois (d’abord pour trouver les éléments à supprimer, puis pour les supprimer). retirez-les).

En fait, la suppression d'une liste d'éléments d'une autre liste est probablement un algorithme pire que O (n) et la méthode 2 est encore pire.

La méthode itérateur:

 List data = ...;

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

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

Answer 5

Premièrement, je m'assurerais qu'il s'agit vraiment d'un goulot d'étranglement en termes de performances, sinon j'opterais pour la solution la plus propre et la plus expressive.

S'il s'agit d'un goulot d'étranglement lié aux performances, essayez simplement les différentes stratégies et voyez ce qui est le plus rapide. Mon pari est de créer une nouvelle ArrayList et d'y placer les objets souhaités, en supprimant l'ancien ArrayList.