[
https://issues.apache.org/jira/browse/COLLECTIONS-545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart updated COLLECTIONS-545:
----------------------------------------
Affects Version/s: (was: 4.1)
4.0
> 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.0
> Environment: Ubuntu 14.04
> Reporter: Oswaldo Olivo
> Priority: Trivial
> Labels: Collections, documentaion, performance
>
> 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)
