commons-issues mailing list archives

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


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:
>             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 =;
>             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.

View raw message