[jira] [Commented] (COLLECTIONS-407) ListOrderedSet.removeAll() is slow

["Thomas Neidhart (JIRA)" <ji...@apache.org>]

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

Thomas Neidhart commented on COLLECTIONS-407:
---------------------------------------------

The patch looks correct. The only thing that comes to my mind is that there may be collections which wrongly implement the methods in question and do not correctly return the change status.

So the way it is implemented right now is a bit slower but will work in all cases.
                
> ListOrderedSet.removeAll() is slow
> ----------------------------------
>
>                 Key: COLLECTIONS-407
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-407
>             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 ListOrderedSet.removeAll().
> It appears in version 3.2.1 and also in revision 1344775 (31 May
> 2012).  I have 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 317X speedup.
> To run the test, just do:
> $ java Test
> The output for the un-patched version is:
> Time is 3812
> The output for the patched version is:
> Time is 12
> As the patch shows, the problem is in 
> ListOrderedSet.remove(Object object).  The code for this method is:
> boolean result = collection.remove(object);
> setOrder.remove(object);
> return result;
> The patch changes it to :
> boolean result = collection.remove(object);
> if (result) setOrder.remove(object);
> return result;
> The "setOrder.remove(object)" is not necessary if 
> "collection.remove(object)" did not find the object.
> This small change speeds up
> ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) because
> ListOrderedSet.ListOrderedSet.removeAll(Collection<?> coll) iterates
> over all the elements in "coll" and calls 
> ListOrderedSet.remove(Object object).  So the un-patched code has
> quadratic complexity, while the patched code has linear complexity.
> Is this truly a bug, or am I missing something here?  If so, can you
> please confirm if 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