Why does my search time get shorter the more searches I do?

Question

I'm doing an assignment that requires me to measure the time taken by two different search algorithms, sequential and binary (I suppose to make the point about efficiency). I have a target list of about 280 words to look for and a search pool list of about 1200 words. I've read both files in and stored the words in ArrayLists.

Here's the relevant bit for the sequential algorithm I've implemented so far:

long startTime = System.nanoTime();

//search sorted list for as long as end of list has not been reached and 
//current list item lexicographically precedes target String    
while((compareResult > 0)&&(position != searchPool.size()-1)){

    //update to current position
    position += 1;

    compareResult = target.compareTo(searchPool.get((int)position));

    comparisonCount += 1;

}//end while loop


long endTime = System.nanoTime();

timeElapsed = endTime - startTime; //timeElapsed also a long

After this, I display the number of comparisons made and the time elapsed (in milliseconds, so I'm dividing by a million first).

The time returned for the first few numbers is around 0.5 to 0.7 ms. This number wobbles downward to the 32nd word which takes 0.1 ms. The remaining 150 words all take 0.0 ms.

I was expecting a direct correlation between the number of comparisons and the elapsed time. Any idea what's going wrong?

Aside: It occurred to me that the number of comparisons made by the compareTo method (ie word length) might be affecting the time, however even long words that do not appear in the searched list (and therefore must be compared to all items before that conclusion is reached) take no time at all if they appear further down.

Answer 1

JVM optimizes the code paths that are frequently executed so they will become faster. Also depending on application first few iterations may involve establishing a connection, loading a resource etc.

So as general strategy you should discard first few samples. And take measurement as average over larger samples for more reliable results.