Making ArrayList.containsAll run faster

Question

Whenever using ArrayList, the method containsAll(collection) runs in time \$\mathcal{O}(mn)\$, where \$n\$ is the size of ArrayList and \$m\$ is the length of collection. However, it relies only on equals(Object)-method.

I have this subclass of ArrayList that does the same in time \$\mathcal{O}(n)\$, but relies on hashCode() as well.

My main question, should I do this optimization at expense of adding more requirements?

MyArrayList.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * This class provides a faster {@link #containsAll(java.util.Collection) } 
 * method.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <E> the actual element type.
 */
public class MyArrayList<E> extends ArrayList<E> {

    /**
     * Returns {@code true} if this list contains all elements in {@code coll}
     * and {@code false} otherwise.
     * 
     * @param  coll the collection to check for inclusion in this list.
     * @return {@code true} if this list contains all elements in 
     *         {@code coll}:
     */
    @Override
    public boolean containsAll(Collection<?> coll) {
        Set<?> set = new HashSet<>(coll);

        for (E element : this) {
            if (set.contains(element)) {
                set.remove(element);

                if (set.isEmpty()) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(final String... args) {
        List<Integer> jdkList = new ArrayList<>();
        List<Integer> myList  = new MyArrayList<>();

        for (int i = 0; i < 1000000; ++i) {
            jdkList.add(i);
            myList.add(i);
        }

        Random rnd = new Random();
        Collection<Integer> coll = new ArrayList<>();

        for (int i = 0; i < 1000; ++i) {
            coll.add(rnd.nextInt(myList.size()));
        }

        // Uncomment for failing test.
        //coll.add(-1);

        long ta = System.currentTimeMillis();

        boolean result = jdkList.containsAll(coll);

        long tb = System.currentTimeMillis();

        System.out.println("ArrayList.containsAll() in " + (tb - ta) + " ms. " +
                           "Result: " + result);

        ta = System.currentTimeMillis();

        result = myList.containsAll(coll);

        tb = System.currentTimeMillis();

        System.out.println("MyArrayList.containsAll() in " + (tb - ta) + 
                           " ms. Result: " + result);
    }
}

Answer 1

Relying on .hashCode() may or may not be faster and may or may not produce the same results as relying on .equals().

Do you already see where this is going? The problem begins when you stop obeying the contract of the interface you implement. I'll quote the javadoc for contains here:

Returns true if this collection contains the specified element. More formally, returns true if and only if this collection contains at least one element e such that (o==null ? e==null : o.equals(e)).

This is the formal definition for contains that also applies to containsAll.

Now considering that a programmer seeing a Collection expects the contains method to work based on equals and countering with the fact that yours doesn't you're violating the "Principle Of Least Surprise".

This also leads to code handling collections behaving differently depending on what implementation you pass in, which is never desirable.

In general I think that relying solely on hashCode for contains is a bad idea, even when it's best practice to override hashCode so the resulting hashes of equal objects are equal and those of nonequal objects aren't.

Answer 2

This implementation has a bug. Consider the following code:

List<Integer> jdkList = new ArrayList<>();
List<Integer> myList  = new MyArrayList<>();
List<Integer> empty = new ArrayList<>();

System.out.printf("%b\n", jdkList.containsAll(empty));
System.out.printf("%b\n", myList.containsAll(empty));

The output is

true
false

Answer 3

You are hitting a special case for your array as the hash function of Integer by default is just the integer value itself. As soon as you start having a non-trivial hash function your containsAll implementation begins to be slower.

See for example the following code which uses strings of 100 characters.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * This class provides a faster {@link #containsAll(java.util.Collection) }
 * method.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <E>
 *            the actual element type.
 */
@SuppressWarnings("serial")
public class MyArrayList<E> extends ArrayList<E> {

    static String randomString(int length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; ++i) {
            sb.append((char) (Math.random() * 27) + 'a');
        }
        return sb.toString();
    }

    /**
     * Returns {@code true} if this list contains all elements in {@code coll}
     * and {@code false} otherwise.
     * 
     * @param coll
     *            the collection to check for inclusion in this list.
     * @return {@code true} if this list contains all elements in {@code coll}:
     */
    @Override
    public boolean containsAll(Collection<?> coll) {
        Set<?> set = new HashSet<>(coll);

        for (E element : this) {
            if (set.contains(element)) {
                set.remove(element);

                if (set.isEmpty()) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(final String... args) {
        int n = 100;
        List<String> jdkList = new ArrayList<>();
        List<String> myList = new MyArrayList<>();      
        for (int i = 0; i < 1000000; ++i) {
            jdkList.add(randomString(n));
            myList.add(randomString(n));
        }

        Collection<String> coll = new ArrayList<>();
        for (int i = 0; i < 10000; ++i) {
            coll.add(randomString(n));
        }

        // Uncomment for failing test.
        // coll.add(-1);

        // Warm-up and let the JIT do its optimization thing.
        boolean r = false;
        for (int i = 0; i < 10; ++i) {
            r ^= jdkList.containsAll(coll);
            r ^= myList.containsAll(coll);
        }       
        System.out.println(r + " " + System.currentTimeMillis()); // First print and timing here to load classes.

        long ta = System.currentTimeMillis();
        boolean result = jdkList.containsAll(coll);
        long tb = System.currentTimeMillis();

        long ta1 = System.currentTimeMillis();
        result = myList.containsAll(coll);
        long tb1 = System.currentTimeMillis();


        System.out.println("ArrayList.containsAll() in " + (tb - ta) + " ms. "
                + "Result: " + result);

        System.out.println("MyArrayList.containsAll() in " + (tb1 - ta1)
                + " ms. Result: " + result);
    }
}

Output on my machine:

false 1436092158685
ArrayList.containsAll() in 15 ms. Result: false
MyArrayList.containsAll() in 45 ms. Result: false

Answer 4

You idea is good, but you've got it backwards and the implementation is not ideal.

@Override
public boolean containsAll(Collection<?> coll) {
    Set<?> set = new HashSet<>(coll);

In case of empty or single-element coll, it's wasting time, since the original implementation is optimal.

You should also handle the case of this.size() < new HashSet<>(coll).size(), as the answer is then trivially false.

    for (E element : this) {
        if (set.contains(element)) {
            set.remove(element);

            if (set.isEmpty()) {
                return true;
            }
        }
    }

You got it backwards: You're testing coll.containsAll(this).

Also note that the removal is usually more expensive than a test and you should try to avoid it.

---

Actually, you have to convert this to a HashSet, rather than the other way round. This may get very expensive if your list is huge. It never amortizes if the list is huge and the collection small.

/// Find yourself better names!!!
private static final int MAGIC_1 = 10;
private static final int MAGIC_2 = 4;

public boolean containsAll(Collection<?> coll) {
   if (this.size() < MAGIC_1 || coll.size() < MAGIC_2) {
       return super.containsAll(coll);
   }

   return new HashSet<>(this).containsAll(coll);
}

Answer 5

I think if you have a case in which you need an ArrayList which needs a faster containsAll() method, it is OK. But still it feels like being a hack. If you used, for example, a HashSet instead of an ArrayList, the containsAll() method would probably be more like \$\mathcal{O}(m)\$. A LinkedHashSet could preverse insertion order. If you need MultiSets, which are available on 3rd-pary libraries, using a LinkedHashMultiSet, you could also preserve insertion order. But it still does not provide random access.

So if you need random access and a faster containsAlls() and can provide a fast hashCode() method, it is certainly an easy method to get that functionality.