List filtering : recreate from empty list, or copy and delete elements?

I have an ArrayList, and I need to filter it (only to remove some elements).

I can't modify the original list.

What is my best option regarding performances :

• Recreate another list from the original one, and remove items from it :

code :

List<Foo> newList = new ArrayList<Foo>(initialList);
for (Foo item : initialList) {
    if (...) {
      开发者_StackOverflow中文版  newList.remove(item);
    }
}

• Create an empty list, and add items :

code :

List<Foo> newList = new ArrayList<Foo>(initialList.size());
for (Foo item : initialList) {
    if (...) {
        newList.add(item);
    }
}

Which of these options is the best ? Should I use anything else than ArrayList ? (I can't change the type of the original list though)

As a side note, approximatively 80% of the items will be kept in the list. The list contains from 1 to around 20 elements.

Best option is to go with what is easiest to write and maintain.

If performance is problem, you should profile the application afterwards and not to optimize prematurely.

In addition, I'd use filtering from library like google-collections or commons collections to make the code more readable:

Collection<T> newCollection = Collections2.filter(new Predicate<T>() {
    public boolean apply(T item) {
        return (...); // apply your test here
    }
});

Anyway, as it seems you are optimizing for the performance, I'd go with System.arraycopy if you indeed want to keep most of the original items:

String[] arr = new String[initialList.size()];
String[] src = initialList.toArray(new String[initialList.size()]);
int dstIndex = 0, blockStartIdx=0, blockSize=0;
for (int currIdx=0; currIdx < initialList.size(); currIdx++) {
    String item = src[currIdx];
    if (item.length() <= 4) {
        if (blockSize > 0)
            System.arraycopy(src, blockStartIdx, arr, dstIndex, blockSize);
            dstIndex += blockSize;
            blockSize = 0;
        } else {
            if (blockSize == 0)
                blockStartIdx = currIdx;
            blockSize++;
        }
    }
    ArrayList newList = new ArrayList(arr.length + 1);
    newList.addAll(Arrays.asList(arr));
}

It seems to be about 20% faster than your option 3. Even more so (40%) if you can skip the new ArrayList creation at the end.

See: http://pastebin.com/sDhV8BUL

You might want to go with the creating a new list from the initial one and removing. They would be less method calls that way since you're keeping ~80% of the original items.

Other than that, I don't know of any way to filter the items.

Edit: Apparently Google Collections has something that might interest you?

As @Sanjay says, "when in doubt, measure". But creating an empty ArrayList and then adding items to it is the most natural implementation and your first goal should be to write clear, understandable code. And I'm 99.9% sure it will be the faster one too.

Update: By copying the old List to a new one and then striking out the elements you don't want, you incur the cost of element removal. The ArrayList.remove() method needs to iterate up to the end of the array on each removal, copying each reference down a position in the list. This almost certainly will be more expensive than simply creating a new ArrayList and adding elements to it.

Note: Be sure to allocate the new ArrayList to an initial capacity set to the size of the old List to avoid reallocation costs.

the second is faster (iterate and add to second as needed) and the code for the first will throw ConcurrentModificationException when you remove any items

and in terms of what result type will be depends on what you are going to need the filtered list for

I'd first follow the age old advice; when in doubt, measure.

Should I use anything else than ArrayList ?

That depends on what kind of operations would you be performing on the filtered list but ArrayList is usually is a good bet unless you are doing something which really shouldn't be backed by a contiguous list of elements (i.e. arrays).

List newList = new ArrayList(initialList.size());

I don't mean to nitpick, but if your new list won't exceed 80% of the initial size, why not fine tune the initial capacity to ((int)(initialList.size() * .8) + 1)?

Since I'm only get suggestions here, I decided to run my own bench to be sure.

Here are the conclusions (with an ArrayList of String).

• Solution 1, remove items from the copy : 2400 ms.

• Solution 2, create an empty list and fill it : 1600 ms. newList = new ArrayList<Foo>();

• Solution 3, same as 2, except you set the initial size of the List : 1530 ms. newList = new ArrayList<Foo>(initialList.size());

• Solution 4, same as 2, except you set the initial size of the List + 1 : 1500 ms. newList = new ArrayList<Foo>(initialList.size() + 1); (as explained by @Soronthar)

Source : http://pastebin.com/c2C5c9Ha