La façon la plus efficace (performance) de supprimer de nombreux éléments de la Liste en Java?

En supprimant un grand nombre d'éléments à partir d'un ArrayList est un O(n^2) opération. Je recommanderais tout simplement à l'aide d'un LinkedList c'est plus optimisé pour l'insertion et le retrait (mais pas pour l'accès aléatoire). LinkedList a un peu d'une surcharge de la mémoire.

Si vous avez besoin de garder ArrayList, alors vous êtes mieux de créer une nouvelle liste.

Mise à jour: la Comparaison avec la création d'une nouvelle liste:

La réutilisation de la même liste, le coût principal est à venir à partir de la suppression du nœud et la mise à jour appropriée des pointeurs dans LinkedList. C'est un fonctionnement constant pour tout nœud.

Lors de la construction d'une nouvelle liste, le coût principal est à venir à partir de la création de la liste, et l'initialisation de tableau entrées. Les deux sont bon marché des opérations. Vous pourriez incurre le coût de redimensionnement de la nouvelle liste backend tableau; en supposant que le tableau final est supérieur à la moitié de l'entrée de gamme.

Donc, si vous deviez supprimer un seul élément, puis LinkedList approche est probablement plus rapide. Si vous supprimez tous les nœuds sauf pour l'un, probablement à la liste nouvelle approche est plus rapide.

Il y a plus de complications lorsque vous apportez de la gestion de la mémoire et de la GC. Je voudrais laisser ces.

La meilleure option est de mettre en œuvre les solutions de rechange vous-même et à comparer les résultats lors de l'exécution de votre charge typique.

J'imagine que la construction d'une nouvelle liste, plutôt que de modifier la liste existante, serait plus performant - en particulier lorsque le nombre d'éléments est aussi grand que vous indiquez. Cela suppose, votre liste est une ArrayList, pas un LinkedList. Pour un non-circulaire LinkedList, de l'insertion est O(n), mais l'enlèvement de l'existant iterator position est O(1); dans ce cas, votre naïfs algorithme doit être suffisamment performant.

À moins que la liste est un LinkedList, le coût de déplacement de la liste à chaque fois que vous appelez remove() est probablement l'un des composants les plus chers de la mise en œuvre. Pour le tableau des listes, je voudrais envisager d'utiliser:

public static <T> List<T> removeMany(List<T> items) {
    List<T> newList = new ArrayList<T>(items.size());
    Iterator<T> iter = items.iterator();
    while (iter.hasNext()) {
        T item = iter.next();
        //<cond> goes here
        if (/*<cond>: */i++ % 2 != 0) {
            newList.add(item);
        }
    }
    return newList;
}

Une chose que vous pourriez faire est d'essayer d'utiliser un LinkedList au lieu d'une ArrayList, comme avec un ArrayList tous les autres éléments doivent être copiés si des éléments sont supprimés à partir de l'intérieur de la liste.

Car la vitesse est métriques les plus importantes, il y a la possibilité d'utiliser plus de mémoire et de faire moins de loisirs de listes (comme mentionné dans mon commentaire). Réel impact sur les performances doit être entièrement dépendante de la façon dont la fonctionnalité est utilisé, cependant.

L'algorithme suppose qu'au moins une des conditions suivantes est remplie:

• tous les éléments de la liste d'origine n'ont pas besoin d'être testé. Ce qui pourrait arriver si nous sommes vraiment à la recherche pour les N premiers éléments qui correspondent à notre état, plutôt que de tous les éléments qui correspondent à notre condition.
• c'est plus cher pour copier la liste dans la nouvelle mémoire. Cela pourrait se produire si la liste originale utilise plus de 50% de l'allocation de la mémoire, afin de travailler sur place pourrait être mieux ou si les opérations de mémoire à son tour d'être plus lent (ce qui serait un résultat inattendu).
• la vitesse de la peine de supprimer les éléments de la liste est trop grande pour accepter une fois pour toutes, mais une diffusion qui peine à travers de multiples opérations est acceptable, même si l'ensemble de la pénalité est plus que de prendre tout cela à la fois. C'est comme prendre un $200K hypothécaire: payer 1000 $par mois pour 30 ans, c'est abordable sur une base mensuelle, et a les avantages de posséder une maison et de l'équité, alors même que le paiement est 360K sur la durée de vie du prêt.

Avertissement: Il y a pro les erreurs de syntaxe, je ne l'ai pas essayer de compiler quoi que ce soit.

Tout d'abord, la sous-classe ArrayList

public class ConditionalArrayList extends ArrayList { 

public Iterator iterator(Condition) 
{ 
retour listIterator(condition); 
} 

public ListIterator listIterator(Condition) 
{ 
de retour de nouvelle ConditionalArrayListIterator(ce.iterator(),condition); 
} 

public ListIterator listIterator(){ return iterator(); } 
public iterator(){ 
throw new InvalidArgumentException("Vous devez spécifier une condition pour l'itérateur"); 
} 
} 

Alors nous avons besoin de l'aide des classes:

public class ConditionalArrayListIterator implémente ListIterator 
{ 
privé ListIterator listIterator; 
Condition de la Condition; 

//les deux indicateurs suivants sont utilisés comme une optimisation rapide de sorte que 
//nous n'avons pas répéter les tests sur les bonnes éléments unnecessarially. 
boolean nextKnownGood = false; 
boolean prevKnownGood = false; 

public ConditionalArrayListIterator(ListIterator listIterator, Condition de la Condition) 
{ 
c'.listIterator = listIterator; 
c'.état = état; 
} 

public void add(Object o){ listIterator.add(o); } 

/** 
* Notez que cela, il est extrêmement inefficace pour 
* appel hasNext() et hasPrev() sinon quand 
* il y a un tas de non-correspondance entre les éléments 
* deux éléments correspondants. 
*/
public boolean hasNext() 
{ 
si( nextKnownGood ) return true; 

/* trouver l'objet suivant dans la liste 
* correspond à notre condition, le cas échéant. 
*/
while( ! listIterator.hasNext() ) 
{ 
Objet next = listIterator.next(); 
si( condition.correspond à(suivant) ) { 
listIterator.set(suivant); 
nextKnownGood = true; 
return true; 
} 
} 

nextKnownGood = false; 
//pas d'élément correspondant n'a été trouvé. 
return false; 
} 

/** 
* Voir hasPrevious pour l'efficacité des notes. 
* Copie & pâte de hasNext(). 
*/
public boolean hasPrevious() 
{ 
si( prevKnownGood ) return true; 

/* trouver l'objet suivant dans la liste 
* correspond à notre condition, le cas échéant. 
*/
while( ! listIterator.hasPrevious() ) 
{ 
Objet prev = listIterator.next(); 
si( condition.correspond à(prev) ) { 
prevKnownGood = true; 
listIterator.set(prev); 
return true; 
} 
} 

//pas d'élément correspondant n'a été trouvé. 
prevKnwonGood = false; 
return false; 
} 

/** voir hasNext() pour plus d'efficacité remarque **/
public Object next() 
{ 
si( nextKnownGood || hasNext() ) 
{ 
prevKnownGood = nextKnownGood; 
nextKnownGood = false; 
retour listIterator.next(); 
} 

jeter NoSuchElementException("Pas plus d'éléments correspondants"); 
} 

/** voir hasNext() pour l'efficacité de la note; copie & pâte de next() **/
public Objet précédent() 
{ 
si( prevKnownGood || hasPrevious() ) 
{ 
nextKnownGood = prevKnownGood; 
prevKnownGood = false; 
retour listIterator.previous(); 
} 
jeter NoSuchElementException("Pas plus d'éléments correspondants"); 
} 

/** 
* Notez que nextIndex() et previousIndex() retourne l'index du tableau 
* de la valeur, pas le nombre de résultats que cette classe est de retour. 
* si ce n'est pas bon pour vous, il vous suffit de maintenir votre propre indice actuel et 
* incrémenter ou decriment dans next() et previous() 
*/
public int nextIndex(){ return listIterator.previousIndex(); } 
public int previousIndex(){ return listIterator.previousIndex(); } 

public remove(){ listIterator.remove(); } 
public set(Object o) { listIterator.set(o); } 
} 

et, bien sûr, nous avons besoin de l'état de l'interface:

/** tout comme un comparateur de... **/
interface publique d'État 
{ 
public boolean matches(Object obj); 
} 

Et une condition pour vérifier

public class IsEvenCondition { 
{ 
public boolean matches(Object obj){ return (Nombre(obj)).intValue() % 2 == 0; 
} 

et nous sommes enfin prêts pour quelque test code

 
Condition = new IsEvenCondition(); 

Système.out.println("préparation des articles"); 
startMillis = Système.currentTimeMillis(); 
Liste<Integer> articles = new ArrayList<Integer>(); //Entier est pour la démo 
for (int i = 0; i < 1000000; i++) { 
éléments.ajouter(i * 3); //juste pour la démo 
} 
endMillis = Système.currentTimeMillis(); 
Système.out.println("Il a fallu" + (endmillis-startmillis) + " pour la préparation de la liste. "); 

Système.out.println("supprimer des éléments"); 
startMillis = Système.currentTimeMillis(); 
//nous n'avons pas réellement jamais supprimer de cette liste, de sorte 
//removeMany est effectivement "instantanée" 
//articles = removeMany(articles); 
endMillis = Système.currentTimeMillis(); 
Système.out.println("après avoir supprimer: les articles.size=" + articles.size() + 
"et il a fallu" + (endMillis - startMillis) + " milli(s)"); 
Système.out.println("--> NOTE: Rien n'est réellement supprimé. Cet algorithme utilise extra" 
+ " de la mémoire pour éviter de modifier ou dupliquer la liste d'origine."); 

Système.out.println("a Propos de parcourir la liste"); 
startMillis = Système.currentTimeMillis(); 
int count = iterate(articles, condition); 
endMillis = Système.currentTimeMillis(); 
Système.out.println("après itération: les articles.size=" + articles.size() + 
le " compteur=" + compteur + "et il a fallu" + (endMillis - startMillis) + " milli(s)"); 
Système.out.println("--> NOTE: ce doit être quelque peu inefficace." 
+ " principalement en raison de surcharge de plusieurs classes." 
+ "Cet algorithme est conçu (espérer) à être plus rapide que l'" 
+ " un algorithme où tous les éléments de la liste sont utilisés."); 

Système.out.println("a Propos de parcourir la liste"); 
startMillis = Système.currentTimeMillis(); 
int total = addFirst(30, des éléments, de l'état); 
endMillis = Système.currentTimeMillis(); 
Système.out.println("après totalisant 30 premiers éléments: total=" + total + 
"et il a fallu" + (endMillis - startMillis) + " milli(s)"); 

... 

private int iterate(List<Integer> éléments, Condition de la Condition) 
{ 
//le i++ et la valeur de retour sont vraiment à éviter d'optimisation de la JVM 
//- juste pour être sûr. 
Iterator iter = éléments.listIterator(condition); 
for( int i=0; iter.hasNext()); i++){ iter.next(); } 
return i; 
} 

private int addFirst(int n, une Liste<Integer> éléments, Condition de la Condition) 
{ 
int total = 0; 
Iterator iter = éléments.listIterator(condition); 
for(int i=0; i<n;i++) 
{ 
total += ((Integer)iter.next()).intValue(); 
} 
} 

Plutôt que de troubler ma première réponse, qui est déjà assez long, voici une seconde, option: vous pouvez créer votre propre liste de tableaux, et le drapeau des choses comme "supprimé". Cet algorithme fait les hypothèses:

• il est préférable de perdre du temps (à faible vitesse) lors de la construction que de faire de même au cours de l'opération de suppression. En d'autres termes, il se déplace à la vitesse de la peine d'un endroit à un autre.
• c'est mieux de la mémoire des déchets maintenant, et le temps de nettoyage après le résultat est computeed plutôt que de passer du temps à l'avant (vous êtes toujours coincé avec le temps, la collecte des ordures...).
• une fois le retrait commence, les éléments ne seront jamais ajouté à la liste (sinon il y a des problèmes avec la ré-allocation de l'drapeaux objet)

Aussi, c'est, encore une fois, pas testé donc il n'y a prlolly les erreurs de syntaxe.

public class FlaggedList extends ArrayList { 
private Vector<Boolean> flags = new ArrayList(); 
private static final String EN = Booléen.TRUE; //pas supprimé 
private static final String OUT = Boolean.FALSE; //supprimer 
private int supprimé = 0; 

public MyArrayList(){ ce(1000000); } 
public MyArrayList(int estimation){ 
super(estimation); 
flags = new ArrayList(estimation); 
} 

public void supprimer(int idx){ 
les drapeaux.set(idx, OUT); 
retiré++; 
} 

public boolean isRemoved(int idx){ return drapeaux.get(idx); } 
} 

et l'itérateur - plus de travail peut être nécessaire pour le garder synchronisés, et de nombreuses méthodes sont laissés de côté, cette fois:

public class FlaggedListIterator implémente ListIterator 
{ 
int idx = 0; 

public FlaggedList liste; 
public FlaggedListIterator(FlaggedList liste) 
{ 
c'.liste = liste; 
} 
public boolean hasNext() { 
while(idx<liste.size() && liste.isRemoved(idx++)) ; 
retour idx < liste.size(); 
} 
}