You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Adrian Nistor (JIRA)" <ji...@apache.org> on 2012/06/01 19:56:23 UTC
[jira] [Updated] (COLLECTIONS-407) ListOrderedSet.removeAll() is
slow
[ https://issues.apache.org/jira/browse/COLLECTIONS-407?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrian Nistor updated COLLECTIONS-407:
--------------------------------------
Attachment: Test.java
patch.diff
> 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