java: List.contains() performance difference with manual searching
contains, java, list
Solution
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!
Problem
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 how contains() function makes such a big difference? which search algorithm does it use? if list conatins the searched element, does it terminate searching at first element?