commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrian Nistor (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (COLLECTIONS-416) ListUtils.removeAll() is very slow
Date Tue, 03 Jul 2012 23:12:34 GMT

    [ https://issues.apache.org/jira/browse/COLLECTIONS-416?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13406156#comment-13406156
] 

Adrian Nistor commented on COLLECTIONS-416:
-------------------------------------------

Hi Thomas,

Yes, you are absolutely right, my patch:

"if (!(remove instanceof java.util.Set<?>)) remove = new HashSet<Object>(remove);"

assumes that anything else except Set has slow contains(), which is
false.

Maybe the best tradeoff is to document this problem, just like you
said, and handle the most common case of slow contains(), i.e., when
the collection is a list:

"if (remove instanceof java.util.List) remove = new HashSet<Object>(remove);"

The scalable solution would be to have a helper method, presumably in
CollectionUtils:

public static <E> Collection<E> createFastContainsCollection(Collection<E>
c) {
   return (c instanceof List<E>) ? new HashSet<E>(c) : c;
}

and use it when the complexity of contains() affects the complexity of
the algorithm.  This is similar with choosing your algorithm based on
if a collection implements java.util.RandomAccess or not.

Best,

Adrian


                
> ListUtils.removeAll() is very slow
> ----------------------------------
>
>                 Key: COLLECTIONS-416
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-416
>             Project: Commons Collections
>          Issue Type: Bug
>    Affects Versions: 3.2.1
>         Environment: java 1.6.0_24
> Ubuntu 11.10
>            Reporter: Adrian Nistor
>         Attachments: Test.java, patch.diff
>
>
> Hi,
> I am encountering a performance problem in ListUtils.removeAll().  It
> appears in version 3.2.1 and also in revision 1355448.  I attached a
> test that exposes this problem and a one-line patch that fixes it.  On
> my machine, for this test, the patch provides a 217X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 5430
> The output for the patched version is:
> Time is 25
> As the patch shows, the problem is that
> "ListUtils.removeAll(Collection<E> collection, Collection<?> remove)"
> performs "remove.contains(obj)" for each element in "collection",
> which can be very expensive if "remove.contains(obj)" is expensive,
> e.g., when "remove" is a list.
> The one-line patch I attached puts the elements of "remove" in a
> HashSet (which has very fast "contains()"), if "remove" is not already
> a set:
> "if (!(remove instanceof java.util.Set<?>)) remove = new HashSet<Object>(remove);"
> Is this a bug, or am I misunderstanding the intended behavior? If so,
> can you please confirm that the patch is correct?
> Thanks,
> Adrian

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message