How to efficiently (performance) remove many items from List in Java?

Question

I have quite large List named items (>= 1,000,000 items) and some condition denoted by <cond> that selects items to be deleted and <cond> is true for many (maybe half) of items on my list.

My goal is to efficiently remove items selected by <cond> and retain all other items, source list may be modified, new list may be created - best way to do it should be chosen considering performance.

Here is my testing code:

    System.out.println("preparing items");
    List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
    for (int i = 0; i < 1000000; i++) {
        items.add(i * 3); // just for demo
    }

    System.out.println("deleting items");
    long startMillis = System.currentTimeMillis();
    items = removeMany(items);
    long endMillis = System.currentTimeMillis();

    System.out.println("after remove: items.size=" + items.size() + 
            " and it took " + (endMillis - startMillis) + " milli(s)");

and naive implementation:

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

As you can see I used item index modulo 2 == 0 as remove condition (<cond>) - just for demonstation purposes.

What better version of removeMany may be provided and why this better version is actually better?

Answer 1

As others have said, your first inclination should be to just build up a second list.

But, if you'd like to also try out editing the list in-place, the efficient way to do that is to use Iterables.removeIf() from Guava. If its argument is a list, it coalesces the retained elements toward the front then simply chops off the end -- much faster than removing() interior elements one by one.

Answer 2

Rather than muddying my first answer, which is already rather long, here's a second, related option: you can create your own ArrayList, and flag things as "removed". This algoritm makes the assumptions:

• it's better to waste time (lower speed) during construction than to do the same during the removal operation. In other words, it moves the speed penalty from one location to another.
• it's better to waste memory now, and time garbage collecting after the result is computeed rather than spend the time up front (you're always stuck with time garbage collecting...).
• once removal begins, elements will never be added to the list (otherwise there are issues with re-allocating the flags object)

Also, this is, again, not tested so there's prlolly syntax errors.

public class FlaggedList extends ArrayList {
  private Vector<Boolean> flags = new ArrayList();
  private static final String IN = Boolean.TRUE;  // not removed
  private static final String OUT = Boolean.FALSE; // removed
  private int removed = 0;

  public MyArrayList(){ this(1000000); }
  public MyArrayList(int estimate){
    super(estimate);
    flags = new ArrayList(estimate);
  }

  public void remove(int idx){
    flags.set(idx, OUT);
    removed++;
  }

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

and the iterator - more work may be needed to keep it synchronized, and many methods are left out, this time:

public class FlaggedListIterator implements ListIterator
{
  int idx = 0;

  public FlaggedList list;
  public FlaggedListIterator(FlaggedList list)
  {
    this.list = list;
  }
  public boolean hasNext() {
    while(idx<list.size() && list.isRemoved(idx++)) ;
    return idx < list.size();
  }
}

Answer 3

Since speed is the most important metric, there's the possibility of using more memory and doing less recreation of lists (as mentioned in my comment). Actual performance impact would be fully dependent on how the functionality is used, though.

The algorithm assumes that at least one of the following is true:

• all elements of the original list do not need to be tested. This could happen if we're really looking for the first N elements that match our condition, rather than all elements that match our condition.
• it's more expensive to copy the list into new memory. This could happen if the original list uses more than 50% of allocated memory, so working in-place could be better or if memory operations turn out to be slower (that would be an unexpected result).
• the speed penalty of removing elements from the list is too large to accept all at once, but spreading that penalty across multiple operations is acceptable, even if the overall penalty is larger than taking it all at once. This is like taking out a $200K mortgage: paying $1000 per month for 30 years is affordable on a monthly basis and has the benefits of owning a home and equity, even though the overall payment is 360K over the life of the loan.

Disclaimer: There's prolly syntax errors - I didn't try compiling anything.

First, subclass the ArrayList

public class ConditionalArrayList extends ArrayList {

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

  public ListIterator listIterator(Condition condition)
  {
    return new ConditionalArrayListIterator(this.iterator(),condition); 
  }

  public ListIterator listIterator(){ return iterator(); }
  public iterator(){ 
    throw new InvalidArgumentException("You must specify a condition for the iterator"); 
  }
}

Then we need the helper classes:

public class ConditionalArrayListIterator implements ListIterator
{
  private ListIterator listIterator;
  Condition condition;

  // the two following flags are used as a quick optimization so that 
  // we don't repeat tests on known-good elements unnecessarially.
  boolean nextKnownGood = false;
  boolean prevKnownGood = false;

  public ConditionalArrayListIterator(ListIterator listIterator, Condition condition)
  {
    this.listIterator = listIterator;
    this.condition = condition;
  }

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

  /**
   * Note that this it is extremely inefficient to 
   * call hasNext() and hasPrev() alternatively when
   * there's a bunch of non-matching elements between
   * two matching elements.
   */
  public boolean hasNext()
  { 
     if( nextKnownGood ) return true;

     /* find the next object in the list that 
      * matches our condition, if any.
      */
     while( ! listIterator.hasNext() )
     {
       Object next = listIterator.next();
       if( condition.matches(next) ) {
         listIterator.set(next);
         nextKnownGood = true;
         return true;
       }
     }

     nextKnownGood = false;
     // no matching element was found.
     return false;
  }

  /**
   *  See hasPrevious for efficiency notes.
   *  Copy & paste of hasNext().
   */
  public boolean hasPrevious()
  { 
     if( prevKnownGood ) return true;

     /* find the next object in the list that 
      * matches our condition, if any.
      */
     while( ! listIterator.hasPrevious() )
     {
       Object prev = listIterator.next();
       if( condition.matches(prev) ) {
         prevKnownGood = true;
         listIterator.set(prev);
         return true;
       }
     }

     // no matching element was found.
     prevKnwonGood = false;
     return false;
  }

  /** see hasNext() for efficiency note **/
  public Object next()
  {
     if( nextKnownGood || hasNext() ) 
     { 
       prevKnownGood = nextKnownGood;
       nextKnownGood = false;
       return listIterator.next();
     }

     throw NoSuchElementException("No more matching elements");
  }

  /** see hasNext() for efficiency note; copy & paste of next() **/
  public Object previous()
  {
     if( prevKnownGood || hasPrevious() ) 
     { 
       nextKnownGood = prevKnownGood;
       prevKnownGood = false;
       return listIterator.previous();                        
     }
     throw NoSuchElementException("No more matching elements");
  }

  /** 
   * Note that nextIndex() and previousIndex() return the array index
   * of the value, not the number of results that this class has returned.
   * if this isn't good for you, just maintain your own current index and
   * increment or decriment in next() and previous()
   */
  public int nextIndex(){ return listIterator.previousIndex(); }
  public int previousIndex(){ return listIterator.previousIndex(); }

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

and, of course, we need the condition interface:

/** much like a comparator... **/
public interface Condition
{
  public boolean matches(Object obj);
}

And a condition with which to test

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

and we're finally ready for some test code

    Condition condition = new IsEvenCondition();

    System.out.println("preparing items");
    startMillis = System.currentTimeMillis();
    List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
    for (int i = 0; i < 1000000; i++) {
        items.add(i * 3); // just for demo
    }
    endMillis = System.currentTimeMillis();
    System.out.println("It took " + (endmillis-startmillis) + " to prepare the list. ");

    System.out.println("deleting items");
    startMillis = System.currentTimeMillis();
    // we don't actually ever remove from this list, so 
    // removeMany is effectively "instantaneous"
    // items = removeMany(items);
    endMillis = System.currentTimeMillis();
    System.out.println("after remove: items.size=" + items.size() + 
            " and it took " + (endMillis - startMillis) + " milli(s)");
    System.out.println("--> NOTE: Nothing is actually removed.  This algorithm uses extra"
                       + " memory to avoid modifying or duplicating the original list.");

    System.out.println("About to iterate through the list");
    startMillis = System.currentTimeMillis();
    int count = iterate(items, condition);
    endMillis = System.currentTimeMillis();
    System.out.println("after iteration: items.size=" + items.size() + 
            " count=" + count + " and it took " + (endMillis - startMillis) + " milli(s)");
    System.out.println("--> NOTE: this should be somewhat inefficient."
                       + " mostly due to overhead of multiple classes."
                       + " This algorithm is designed (hoped) to be faster than "
                       + " an algorithm where all elements of the list are used.");

    System.out.println("About to iterate through the list");
    startMillis = System.currentTimeMillis();
    int total = addFirst(30, items, condition);
    endMillis = System.currentTimeMillis();
    System.out.println("after totalling first 30 elements: total=" + total + 
            " and it took " + (endMillis - startMillis) + " milli(s)");

...

private int iterate(List<Integer> items, Condition condition)
{
  // the i++ and return value are really to prevent JVM optimization
  // - just to be safe.
  Iterator iter = items.listIterator(condition);
  for( int i=0; iter.hasNext()); i++){ iter.next(); }
  return i;
}

private int addFirst(int n, List<Integer> items, Condition condition)
{
  int total = 0;
  Iterator iter = items.listIterator(condition);
  for(int i=0; i<n;i++)
  {
    total += ((Integer)iter.next()).intValue();
  }
}

Answer 4

OK, it's time for test results of proposed approaches. Here what approaches I have tested (name of each approach is also class name in my sources):

1. NaiveRemoveManyPerformer - ArrayList with iterator and remove - first and naive implementation given in my question.
2. BetterNaiveRemoveManyPerformer - ArrayList with backward iteration and removal from end to front.
3. LinkedRemoveManyPerformer - naive iterator and remove but working on LinkedList. Disadventage: works only for LinkedList.
4. CreateNewRemoveManyPerformer - ArrayList is made as a copy (only retained elements are added), iterator is used to traverse input ArrayList.
5. SmartCreateNewRemoveManyPerformer - better CreateNewRemoveManyPerformer - initial size (capacity) of result ArrayList is set to final list size. Disadvantage: you must know final size of list when starting.
6. FasterSmartCreateNewRemoveManyPerformer - even better (?) SmartCreateNewRemoveManyPerformer - use item index (items.get(idx)) instead of iterator.
7. MagicRemoveManyPerformer - works in place (no list copy) for ArrayList and compacts holes (removed items) from beginning with items from end of the list. Disadventage: this approach changes order of items in list.
8. ForwardInPlaceRemoveManyPerformer - works in place for ArrayList - move retaining items to fill holes, finally subList is returned (no final removal or clear).
9. GuavaArrayListRemoveManyPerformer - Google Guava Iterables.removeIf used for ArrayList - almost the same as ForwardInPlaceRemoveManyPerformer but does final removal of items at the end of list.

Full source code is given at the end of this answer.

Tests where performed with different list sizes (from 10,000 items to 10,000,000 items) and different remove factors (specifying how many items must be removed from list).

As I posted here in comments for other answers - I have thought that copying items from ArrayList to second ArrayList will be faster than iterating LinkedList and just removing items. Sun's Java Documentation says that constant factor of ArrayList is low compared to that for the LinkedList implementation, but surprisingly this is not the case in my problem.

In practice LinkedList with simple iteration and removal has best performance in most cases (this approach is implemented in LinkedRemoveManyPerformer). Usually only MagicRemoveManyPerformer performance is comparable to LinkedRemoveManyPerformer, other approaches are significantly slower. Google Guava GuavaArrayListRemoveManyPerformer is slower than hand made similar code (because my code does not remove unnecessary items at end of list).

Example results for removing 500,000 items from 1,000,000 source items:

1. NaiveRemoveManyPerformer: test not performed - I'm not that patient, but it performs worse than BetterNaiveRemoveManyPerformer.
2. BetterNaiveRemoveManyPerformer: 226080 milli(s)
3. LinkedRemoveManyPerformer: 69 milli(s)
4. CreateNewRemoveManyPerformer: 246 milli(s)
5. SmartCreateNewRemoveManyPerformer: 112 milli(s)
6. FasterSmartCreateNewRemoveManyPerformer: 202 milli(s)
7. MagicRemoveManyPerformer: 74 milli(s)
8. ForwardInPlaceRemoveManyPerformer: 69 milli(s)
9. GuavaArrayListRemoveManyPerformer: 118 milli(s)

Example results for removing 1 item from 1,000,000 source items (first item is removed):

1. BetterNaiveRemoveManyPerformer: 34 milli(s)
2. LinkedRemoveManyPerformer: 41 milli(s)
3. CreateNewRemoveManyPerformer: 253 milli(s)
4. SmartCreateNewRemoveManyPerformer: 108 milli(s)
5. FasterSmartCreateNewRemoveManyPerformer: 71 milli(s)
6. MagicRemoveManyPerformer: 43 milli(s)
7. ForwardInPlaceRemoveManyPerformer: 73 milli(s)
8. GuavaArrayListRemoveManyPerformer: 78 milli(s)

Example results for removing 333,334 items from 1,000,000 source items:

1. BetterNaiveRemoveManyPerformer: 253206 milli(s)
2. LinkedRemoveManyPerformer: 69 milli(s)
3. CreateNewRemoveManyPerformer: 245 milli(s)
4. SmartCreateNewRemoveManyPerformer: 111 milli(s)
5. FasterSmartCreateNewRemoveManyPerformer: 203 milli(s)
6. MagicRemoveManyPerformer: 69 milli(s)
7. ForwardInPlaceRemoveManyPerformer: 72 milli(s)
8. GuavaArrayListRemoveManyPerformer: 102 milli(s)

Example results for removing 1,000,000 (all) items from 1,000,000 source items (all items are removed but with one-by-one processing, if you know a priori that all items are to be removed, list should be simply cleared):

1. BetterNaiveRemoveManyPerformer: 58 milli(s)
2. LinkedRemoveManyPerformer: 88 milli(s)
3. CreateNewRemoveManyPerformer: 95 milli(s)
4. SmartCreateNewRemoveManyPerformer: 91 milli(s)
5. FasterSmartCreateNewRemoveManyPerformer: 48 milli(s)
6. MagicRemoveManyPerformer: 61 milli(s)
7. ForwardInPlaceRemoveManyPerformer: 49 milli(s)
8. GuavaArrayListRemoveManyPerformer: 133 milli(s)

My final conclusions: use hybrid approach - if dealing with LinkedList - simple iteration and removal is best, if dealing with ArrayList - it depends if item order is important - use ForwardInPlaceRemoveManyPerformer then, if item order may be changed - best choice is MagicRemoveManyPerformer. If remove factor is known a priori (you know how many items will be removed vs retained) then some more conditionals may be put to select approach performing even better in particular situation. But known remove factor is not usual case... Google Guava Iterables.removeIf is such a hybrid solution but with slightly different assumption (original list must be changed, new one cannot be created and item order always matters) - these are most common assumptions so removeIf is best choice in most real-life cases.

Notice also that all good approaches (naive is not good!) are good enough - any one of them shold do just fine in real application, but naive approach must be avoided.

At last - my source code for testing.

package WildWezyrListRemovalTesting;

import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class RemoveManyFromList {

    public static abstract class BaseRemoveManyPerformer {

        protected String performerName() {
            return getClass().getSimpleName();
        }

        protected void info(String msg) {
            System.out.println(performerName() + ": " + msg);
        }

        protected void populateList(List<Integer> items, int itemCnt) {
            for (int i = 0; i < itemCnt; i++) {
                items.add(i);
            }
        }

        protected boolean mustRemoveItem(Integer itemVal, int itemIdx, int removeFactor) {
            if (removeFactor == 0) {
                return false;
            }
            return itemIdx % removeFactor == 0;
        }

        protected abstract List<Integer> removeItems(List<Integer> items, int removeFactor);

        protected abstract List<Integer> createInitialList();

        public void testMe(int itemCnt, int removeFactor) {
            List<Integer> items = createInitialList();
            populateList(items, itemCnt);
            long startMillis = System.currentTimeMillis();
            items = removeItems(items, removeFactor);
            long endMillis = System.currentTimeMillis();
            int chksum = 0;
            for (Integer item : items) {
                chksum += item;
            }
            info("removing took " + (endMillis - startMillis)
                    + " milli(s), itemCnt=" + itemCnt
                    + ", removed items: " + (itemCnt - items.size())
                    + ", remaining items: " + items.size()
                    + ", checksum: " + chksum);
        }
    }
    private List<BaseRemoveManyPerformer> rmps =
            new ArrayList<BaseRemoveManyPerformer>();

    public void addPerformer(BaseRemoveManyPerformer rmp) {
        rmps.add(rmp);
    }
    private Runtime runtime = Runtime.getRuntime();

    private void runGc() {
        for (int i = 0; i < 5; i++) {
            runtime.gc();
        }
    }

    public void testAll(int itemCnt, int removeFactor) {
        runGc();
        for (BaseRemoveManyPerformer rmp : rmps) {
            rmp.testMe(itemCnt, removeFactor);
        }
        runGc();
        System.out.println("\n--------------------------\n");
    }

    public static class NaiveRemoveManyPerformer
            extends BaseRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            if (items.size() > 300000 && items instanceof ArrayList) {
                info("this removeItems is too slow, returning without processing");
                return items;
            }
            int i = 0;
            Iterator<Integer> iter = items.iterator();
            while (iter.hasNext()) {
                Integer item = iter.next();
                if (mustRemoveItem(item, i, removeFactor)) {
                    iter.remove();
                }
                i++;
            }
            return items;
        }

        @Override
        public List<Integer> createInitialList() {
            return new ArrayList<Integer>();
        }
    }

    public static class BetterNaiveRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
//            if (items.size() > 300000 && items instanceof ArrayList) {
//                info("this removeItems is too slow, returning without processing");
//                return items;
//            }

            for (int i = items.size(); --i >= 0;) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    items.remove(i);
                }
            }
            return items;
        }
    }

    public static class LinkedRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> createInitialList() {
            return new LinkedList<Integer>();
        }
    }

    public static class CreateNewRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            List<Integer> res = createResultList(items, removeFactor);
            int i = 0;

            for (Integer item : items) {
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    res.add(item);
                }
                i++;
            }

            return res;
        }

        protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
            return new ArrayList<Integer>();
        }
    }

    public static class SmartCreateNewRemoveManyPerformer
            extends CreateNewRemoveManyPerformer {

        @Override
        protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
            int newCapacity = removeFactor == 0 ? items.size()
                    : (int) (items.size() * (removeFactor - 1L) / removeFactor + 1);
            //System.out.println("newCapacity=" + newCapacity);
            return new ArrayList<Integer>(newCapacity);
        }
    }

    public static class FasterSmartCreateNewRemoveManyPerformer
            extends SmartCreateNewRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            List<Integer> res = createResultList(items, removeFactor);

            for (int i = 0; i < items.size(); i++) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    res.add(item);
                }
            }

            return res;
        }
    }

    public static class ForwardInPlaceRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            int j = 0; // destination idx
            for (int i = 0; i < items.size(); i++) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    if (j < i) {
                        items.set(j, item);
                    }
                    j++;
                }
            }

            return items.subList(0, j);
        }
    }

    public static class MagicRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            for (int i = 0; i < items.size(); i++) {
                if (mustRemoveItem(items.get(i), i, removeFactor)) {
                    Integer retainedItem = removeSomeFromEnd(items, removeFactor, i);
                    if (retainedItem == null) {
                        items.remove(i);
                        break;
                    }
                    items.set(i, retainedItem);
                }
            }

            return items;
        }

        private Integer removeSomeFromEnd(List<Integer> items, int removeFactor, int lowerBound) {
            for (int i = items.size(); --i > lowerBound;) {
                Integer item = items.get(i);
                items.remove(i);
                if (!mustRemoveItem(item, i, removeFactor)) {
                    return item;
                }
            }
            return null;
        }
    }

    public static class GuavaArrayListRemoveManyPerformer
            extends BaseRemoveManyPerformer {

        @Override
        protected List<Integer> removeItems(List<Integer> items, final int removeFactor) {
            Iterables.removeIf(items, new Predicate<Integer>() {

                public boolean apply(Integer input) {
                    return mustRemoveItem(input, input, removeFactor);
                }
            });

            return items;
        }

        @Override
        protected List<Integer> createInitialList() {
            return new ArrayList<Integer>();
        }
    }

    public void testForOneItemCnt(int itemCnt) {
        testAll(itemCnt, 0);
        testAll(itemCnt, itemCnt);
        testAll(itemCnt, itemCnt - 1);
        testAll(itemCnt, 3);
        testAll(itemCnt, 2);
        testAll(itemCnt, 1);
    }

    public static void main(String[] args) {
        RemoveManyFromList t = new RemoveManyFromList();
        t.addPerformer(new NaiveRemoveManyPerformer());
        t.addPerformer(new BetterNaiveRemoveManyPerformer());
        t.addPerformer(new LinkedRemoveManyPerformer());
        t.addPerformer(new CreateNewRemoveManyPerformer());
        t.addPerformer(new SmartCreateNewRemoveManyPerformer());
        t.addPerformer(new FasterSmartCreateNewRemoveManyPerformer());
        t.addPerformer(new MagicRemoveManyPerformer());
        t.addPerformer(new ForwardInPlaceRemoveManyPerformer());
        t.addPerformer(new GuavaArrayListRemoveManyPerformer());

        t.testForOneItemCnt(1000);
        t.testForOneItemCnt(10000);
        t.testForOneItemCnt(100000);
        t.testForOneItemCnt(200000);
        t.testForOneItemCnt(300000);
        t.testForOneItemCnt(500000);
        t.testForOneItemCnt(1000000);
        t.testForOneItemCnt(10000000);
    }
}

Answer 5

I'm sorry, but all these answers are missing the point, I think: You probably don't have to, and probably shouldn't, use a List.

If this kind of "query" is common, why not build an ordered data structure that eliminates the need to traverse all the data nodes? You don't tell us enough about the problem, but given the example you provide a simple tree could do the trick. There's an insertion overhead per item, but you can very quickly find the subtree containing nodes that match , and you therefore avoid most of the comparisons you're doing now.

Furthermore:

• Depending on the exact problem, and the exact data structure you set up, you can speed up deletion -- if the nodes you want to kill do reduce to a subtree or something of the sort, you just drop that subtree, rather than updating a whole slew of list nodes.

• Each time you remove a list item, you are updating pointers -- eg lastNode.next and nextNode.prev or something -- but if it turns out you also want to remove the nextNode, then the pointer update you just caused is thrown away by a new update.)

Answer 6

Use Apache Commons Collections. Specifically this function. This is implemented in essentially the same way that people are suggesting that you implement it (i.e. create a new list and then add to it).

Answer 7

Maybe a List isn't the optimal data structure for you? Can you change it? Perhaps you can use a tree where the items are sorted into in a way that deleting one node removes all items that meet the condition? Or that at least speed up your operations?

In your simplistic example using two lists (one with the items where i % 2 != 0 is true and one with the items where i % 2 != 0 is false) could serve well. But this is of course very domain dependent.

Answer 8

I would make a new List to add the items to, since removing an item from the middle of a List is quite expensive.

public static List<T> removeMany(List<T> items) {
    List<T> tempList = new ArrayList<T>(items.size()/2); //if about half the elements are going to be removed
    Iterator<T> iter = items.iterator();
    while (item : items) {
        // <cond> goes here
        if (/*<cond>: */i % 2 != 0) {
            tempList.add(item);
        }
    }
    return tempList;
}

EDIT: I haven't tested this, so there may very well be small syntax errors.

Second EDIT: Using a LinkedList is better when you don't need random access but fast add times.

BUT...

The constant factor for ArrayList is smaller than that for LinkedList (Ref). Since you can make a reasonable guess of how many elements will be removed (you said "about half" in your question), adding an element to the end of an ArrayList is O(1) as long as you don't have to re-allocate it. So, if you can make a reasonable guess, I would expect the ArrayList to be marginally faster than the LinkedList in most cases. (This applies to the code I have posted. In your naive implementatation, I think LinkedList will be faster).

Answer 9

Removing a lot of elements from an ArrayList is an O(n^2) operation. I would recommend simply using a LinkedList that's more optimized for insertion and removal (but not for random access). LinkedList has a bit of a memory overhead.

If you do need to keep ArrayList, then you are better off creating a new list.

Update: Comparing with creating a new list:

Reusing the same list, the main cost is coming from deleting the node and updating the appropriate pointers in LinkedList. This is a constant operation for any node.

When constructing a new list, the main cost is coming from creating the list, and initializing array entries. Both are cheap operations. You might incurre the cost of resizing the new list backend array as well; assuming that the final array is larger than half of the incoming array.

So if you were to remove only one element, then LinkedList approach is probably faster. If you were to delete all nodes except for one, probably the new list approach is faster.

There are more complications when you bring memory management and GC. I'd like to leave these out.

The best option is to implement the alternatives yourself and benchmark the results when running your typical load.

Answer 10

Try implementing recursion into your algorithm.

Answer 11

I would imagine that building a new list, rather than modifying the existing list, would be more performant - especially when the number of items is as large as you indicate. This assumes, your list is an ArrayList, not a LinkedList. For a non-circular LinkedList, insertion is O(n), but removal at an existing iterator position is O(1); in which case your naive algorithm should be sufficiently performant.

Unless the list is a LinkedList, the cost of shifting the list each time you call remove() is likely one of the most expensive parts of the implementation. For array lists, I would consider using:

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

Answer 12

One thing you could try is to use a LinkedList instead of an ArrayList, as with an ArrayList all other elements need to be copied if elements are removed from within the list.