java: List.contains() performance difference with manual searching

Question

I tried to demonstrate the difference between List.contains() and manually searching execution times the result is awesome. Here is the code,

public static void main(String argv[]) {
    List<String> list = new ArrayList<String>();
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("a");
    list.add("b");

    long startTime = System.nanoTime();

    list.contains("b");

    long endTime = System.nanoTime();
    long duration = endTime - startTime;

    System.out.println("First run: "+duration);

    startTime = System.nanoTime();
    for(String s: list){
        if(s.equals("b"))
            break;
    }
    endTime = System.nanoTime();

    duration = endTime - startTime;
    System.out.println("Second run: "+duration);

}

Output:

• First run: 7500

• Second run: 158685

  1. how contains() function makes such a big difference?

  2. which search algorithm does it use?

  3. if list conatins the searched element, does it terminate searching at first element?

Answer 1

First off, it is not wise to trust results coming from a singular test like that. There are too many variable factors, caching implications to consider, and other such things - you should rather consider writing a test that uses randomization over trials to some extent, and performs the different checks millions of times, not just once.

That said, I expect your results will remain the same; ArrayList implements contains() using its own indexOf() method, which loops directly over the underlying array it stores. You can see this for yourself here

The foreach loop, on the other hand, requires instantiating an Iterator, accessing the array through all of its methods, and just in general doing a lot more work than ArrayList's own direct implementation does. Again, though, you should benchmark it more thoroughly!