[
https://issues.apache.org/jira/browse/COLLECTIONS-407?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13396990#comment-13396990
]
Hudson commented on COLLECTIONS-407:
------------------------------------
Integrated in commons-collections #21 (See
[https://builds.apache.org/job/commons-collections/21/])
[COLLECTIONS-407] improve performance of remove method by taking method
result from underlying collection into account. Thanks to Adrian Nistor for
reporting and providing a patch. (Revision 1351800)
Result = SUCCESS
tn : http://svn.apache.org/viewvc/?view=rev&rev=1351800
Files :
*
/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
> 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
> Fix For: 4.0
>
> 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
