[
https://issues.apache.org/jira/browse/COLLECTIONS-534?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14174142#comment-14174142
]
Thomas Neidhart commented on COLLECTIONS-534:
---------------------------------------------
If we can update the algorithm to get a better performance I am very much in
favor of it, but just copying the input arguments to a different collection to
improve the runtime performance is not what we should do imho.
In similar cases we added something like that to the javadoc:
{noformat}
* This implementation iterates over the elements of this collection,
checking each element in
* turn to see if it's contained in <code>coll</code>. If it's not
contained, it's removed
* from this collection. As a consequence, it is advised to use a
collection type for
* <code>coll</code> that provides a fast (e.g. O(1)) implementation of
* {@link Collection#contains(Object)}.
{noformat}
The rationale behind it is that we can not be sure about the runtime complexity
of the provided collection and just copying it to another collection seems to
be a waste if the user already uses something like a set or another collection
that supports O(1) for contains.
> 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)
