[
https://issues.apache.org/jira/browse/COLLECTIONS-534?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14173001#comment-14173001
]
Oswaldo Olivo commented on COLLECTIONS-534:
-------------------------------------------
Hi Sebb,
Here are some results I've gathered for different sizes:
Size Fixed Original
1000000 0m1.696s 27m35.343s
500000 0m1.392s 11m22.767s
100000 0m1.172s 0m1.136s
10000 0m1.068s 0m1.132s
1000 0m0.972s 0m0.988s
100 0m0.968s 0m0.936s
10 0m0.948s 0m0.908s
> Performance bug in CollectionBag::retainAll
> -------------------------------------------
>
> Key: COLLECTIONS-534
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-534
> Project: Commons Collections
> Issue Type: Bug
> Components: Bag, Collection
> Affects Versions: 4.0
> Environment: Ubuntu 12.04
> Reporter: Oswaldo Olivo
> Labels: perfomance
>
> Hi,
> There seems to be a performance bug in the method retainAll in the
> CollectionBag class.
> The problem is that the code is checking containment over the parameter
> collection, which could be expensive for some types of collections like
> ArrayLists.
> One solution could be to convert the Collection into a HashSet and check
> containment in the HashSet.
> If this is done, then running retainAll on a 1,000,000 collection would take
> less than 2 seconds instead of 27 mins, according to my experiments.
> ____________________________________________
> Here's a function to expose the bug:
> public static void collectionBagRetainAllTest() {
> ArrayList<Integer> coll=new ArrayList<Integer>();
> for(int i=0;i<=1000000;++i)
> coll.add(new Integer(i));
> TreeBag<Integer> treeBag=new TreeBag<Integer>(coll);
> CollectionBag<Integer> bag = new CollectionBag<Integer>(treeBag);
> bag.retainAll(coll);
> }
> _____________________________________
> Here's a proposed patch:
> public boolean retainAll(final Collection<?> coll) {
> if (coll != null) {
> boolean modified = false;
> final Iterator<E> e = iterator();
> HashSet<Object> set=new HashSet<Object>(coll);
> while (e.hasNext()) {
> if (!set.contains(e.next())) {
> e.remove();
> modified = true;
> }
> }
> return modified;
> } else {
> // let the decorated bag handle the case of null argument
> return decorated().retainAll(null);
> }
> }
> _____________________________________
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
