[
https://issues.apache.org/jira/browse/COLLECTIONS-328?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Rogan updated COLLECTIONS-328:
-------------------------------------
Attachment: IntersectHashSet.patch
Attached is a patch to implement this improvement.
The elements from the smaller list are inserted into a HashSet, and the
intersection is then generated by checking whether the HashSet contains each
element from the larger list (if true, include that element in the
intersection).
> ListUtils.intersect is slow
> ---------------------------
>
> Key: COLLECTIONS-328
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-328
> Project: Commons Collections
> Issue Type: Improvement
> Reporter: Jilles van Gurp
> Fix For: 4.0
>
> Attachments: IntersectHashSet.patch
>
>
> ListUtils.intersect is quite slow and can be improved by using a HashSet for
> the contains operation which cuts the complexity from n^2 to n. I ran into
> this by intersecting two lists with a few hundred thousand elements.
> current:
> public static List intersection(final List list1, final List list2) {
> final ArrayList result = new ArrayList();
> final Iterator iterator = list2.iterator();
> while (iterator.hasNext()) {
> final Object o = iterator.next();
> if (list1.contains(o)) {
> result.add(o);
> }
> }
> return result;
> Basically would work by inserting list1 into a HashSet like this:
> Set objs = new HashSet();
> objs.addAll(list1);
> and then instead of list1.contains do a objs.contains
> Further performance can be gained by picking the smallest list for this with
> a simple size comparison.
> BTW what is this method supposed to do with duplicate entries in lists?
> Semantics are not really clear here as opposed to set intersection.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
