Return-Path: 
 <issues-return-45572-apmail-commons-issues-archive=commons.apache.org@commons.apache.org>
X-Original-To: apmail-commons-issues-archive@minotaur.apache.org
Delivered-To: apmail-commons-issues-archive@minotaur.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
	by minotaur.apache.org (Postfix) with SMTP id 951B117AEB
	for <apmail-commons-issues-archive@minotaur.apache.org>;
 Mon, 12 Jan 2015 06:04:33 +0000 (UTC)
Received: (qmail 44696 invoked by uid 500); 12 Jan 2015 06:04:35 -0000
Delivered-To: apmail-commons-issues-archive@commons.apache.org
Received: (qmail 44604 invoked by uid 500); 12 Jan 2015 06:04:34 -0000
Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:issues-help@commons.apache.org>
List-Unsubscribe: <mailto:issues-unsubscribe@commons.apache.org>
List-Post: <mailto:issues@commons.apache.org>
List-Id: <issues.commons.apache.org>
Reply-To: issues@commons.apache.org
Delivered-To: mailing list issues@commons.apache.org
Received: (qmail 44593 invoked by uid 99); 12 Jan 2015 06:04:34 -0000
Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28)
    by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 12 Jan 2015 06:04:34 +0000
Date: Mon, 12 Jan 2015 06:04:34 +0000 (UTC)
From: "Oswaldo Olivo (JIRA)" <jira@apache.org>
To: issues@commons.apache.org
Message-ID: <JIRA.12766770.1421042656000.58370.1421042674788@Atlassian.JIRA>
In-Reply-To: <JIRA.12766770.1421042656000@Atlassian.JIRA>
References: <JIRA.12766770.1421042656000@Atlassian.JIRA>
 <JIRA.12766770.1421042656564@arcas>
Subject: [jira] [Created] (COLLECTIONS-545) Undocumented performance issue
 in the removeAll method in CollectionUtils
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394

Oswaldo Olivo created COLLECTIONS-545:
-----------------------------------------

             Summary: Undocumented performance issue in the removeAll method in CollectionUtils
                 Key: COLLECTIONS-545
                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-545
             Project: Commons Collections
          Issue Type: Bug
          Components: Collection
    Affects Versions: 4.1
         Environment: Ubuntu 14.04
            Reporter: Oswaldo Olivo
            Priority: Trivial


This bug is analogous to https://issues.apache.org/jira/browse/COLLECTIONS-544

The method removeAll in CollectionUtils is inefficient when the second parameter collection has a slow containment method.

The following is the current implementation with its documentation:
============================
     /**
     * Removes the elements in <code>remove</code> from <code>collection</code>. That is, this
     * method returns a collection containing all the elements in <code>c</code>
     * that are not in <code>remove</code>. The cardinality of an element <code>e</code>
     * in the returned collection is the same as the cardinality of <code>e</code>
     * in <code>collection</code> unless <code>remove</code> contains <code>e</code>, in which
     * case the cardinality is zero. This method is useful if you do not wish to modify
     * the collection <code>c</code> and thus cannot call <code>collection.removeAll(remove);</code>.
     *
     * @param <E>  the type of object the {@link Collection} contains
     * @param collection  the collection from which items are removed (in the returned collection)
     * @param remove  the items to be removed from the returned <code>collection</code>
     * @return a <code>Collection</code> containing all the elements of <code>collection</code> except
     * any elements that also occur in <code>remove</code>.
     * @throws NullPointerException if either parameter is null
     * @since 4.0 (method existed in 3.2 but was completely broken)
     */
    public static <E> Collection<E> removeAll(final Collection<E> collection, final Collection<?> remove) {
        return ListUtils.removeAll(collection, remove);
    }


=======================================

We can notice the inefficiency by looking at the removeAll method in ListUtils.
The removeAll method from ListUtils is implemented and documented as follows:

=======================================

     /**
     * Removes the elements in <code>remove</code> from <code>collection</code>. That is, this
     * method returns a list containing all the elements in <code>collection</code>
     * that are not in <code>remove</code>. The cardinality of an element <code>e</code>
     * in the returned collection is the same as the cardinality of <code>e</code>
     * in <code>collection</code> unless <code>remove</code> contains <code>e</code>, in which
     * case the cardinality is zero. This method is useful if you do not wish to modify
     * <code>collection</code> and thus cannot call <code>collection.removeAll(remove);</code>.
     * <p>
     * This implementation iterates over <code>collection</code>, checking each element in
     * turn to see if it's contained in <code>remove</code>. If it's not contained, it's added
     * to the returned list. As a consequence, it is advised to use a collection type for
     * <code>remove</code> that provides a fast (e.g. O(1)) implementation of
     * {@link Collection#contains(Object)}.
     *
     * @param <E>  the element type
     * @param collection  the collection from which items are removed (in the returned collection)
     * @param remove  the items to be removed from the returned <code>collection</code>
     * @return a <code>List</code> containing all the elements of <code>c</code> except
     * any elements that also occur in <code>remove</code>.
     * @throws NullPointerException if either parameter is null
     * @since 3.2
     */
    public static <E> List<E> removeAll(final Collection<E> collection, final Collection<?> remove) {
        final List<E> list = new ArrayList<E>();
        for (final E obj : collection) {
            if (!remove.contains(obj)) {
                list.add(obj);
            }
        }
        return list;
    }

=======================================

In the case of ListUtils:removeAll, the inefficiency is properly documented.

Perhaps the disclaimer about potential inefficiencies depending on the type 
of the parameter collection in ListUtils:removeAll should also be included in CollectionUtils:removeAll.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)