commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Henri Yandell (JIRA)" <j...@apache.org>
Subject [jira] Commented: (COLLECTIONS-328) ListUtils.intersect is slow
Date Sat, 06 Jun 2009 04:53:07 GMT

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

Henri Yandell commented on COLLECTIONS-328:
-------------------------------------------

Need to look at performance numbers from small lists to big lists to work out if the HashSet
is ever not worth it.

I assume the point of the method is to maintain the duplicate entries.

> 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
>
> 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.


Mime
View raw message