I've been fooling around with a bunch of different ways of searching collections, collections of collections, etc. Doing lots of stupid little tests to verify my understanding. Here is one which boggles me (source code further below).
In short, I am generating N random integers and adding them to a list. The list is NOT sorted. I then use Collections.contains() to look for a value in the list. I intentionally look for a value that I know won't be there, because I want to ensure that the entire list space is probed. I time this search.
I then do another linear search manually, iterating through each element of the list and checking if it matches my target. I also time this search.
On average, the second search takes 33% longer than the first one. By my logic, the first search must also be linear, because the list is unsorted. The only possibility I could think of (which I immediately discard) is that Java is making a sorted copy of my list just for the search, but (1) I did not authorize that usage of memory space and (2) I would think that would result in MUCH more significant time savings with such a large N.
So if both searches are linear, they should both take the same amount of time. Somehow the Collections class has optimized this search, but I can't figure out how. So... what am I missing?
import java.util.*;
public class ListSearch {
public static void main(String[] args) {
int N = 10000000; // number of ints to add to the list
int high = 100; // upper limit for random int generation
List<Integer> ints;
int target = -1; // target will not be found, forces search of entire list space
long start;
long end;
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 1)... ");
if (ints.contains(target)) {
// nothing
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
System.out.println();
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 2)... ");
for (Integer i : ints) {
// nothing
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
}
}
